ヘキサモンド・パズルを解く（DLX package 使用）

[ペントミノをExact cover問題として解く（その１）](https://qiita.com/masa0599/items/7d5aa1318149f4ad9edf)ではペントミノ・パズルをExact cover問題としてPyPIのDLX packageを用いて解く方法を紹介しました。
今回は応用問題として[ヘキサモンド・パズル（テンヨー(Tenyo) ヘキサモンド 脳ブロック 永久に遊べるパズル 総数4,968通り）](https://www.amazon.co.jp/%E3%83%86%E3%83%B3%E3%83%A8%E3%83%BC-Tenyo-TBB-03-%E3%83%98%E3%82%AD%E3%82%B5%E3%83%A2%E3%83%B3%E3%83%89-%E8%84%B3%E3%83%96%E3%83%AD%E3%83%83%E3%82%AF/dp/B07SQPJGK3?th=1)を解いて行きたいと思います。


### ボードの構造

まず考える必要があるのはボードの構造ですが、なるべくペントミノの考えをそのまま使いたいので同じような構造にしました。正三角形の上下が交互にあるのでそこだけ考慮が必要です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/77b7b6fc-9a2e-4180-938a-320b27e48c2c.png)


### ヘキサモンドのピース

ピースの形は[An Introduction to Polyiamonds](https://puzzler.sourceforge.net/docs/polyiamonds-intro.html)を参考にしました。
12個のピースに各々名前がついているようです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/d2269e47-40ce-4664-b54c-80762e73d944.png)

### ピースの変形（回転・鏡映）

問題なのはその変形（回転・鏡映）がいくつあるかです

* 回転は(0,120,240)の3通り
* 鏡映はなし・上下・左右・上下左右の4通り

の最大12通りが考えられます。**10-hook**の例を示します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/f85d9ad8-169d-433a-af43-5f31a4c5803c.png)

この場合は12通りとも違うものになりますが同じになるものを除くとピースごとの数は以下になります。

**計94種類**の形をDLXに渡すデータとします。


|ピース名 | 画像| 種類（回転・鏡映）|
|:---:|:---:|:---:|
|bar| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/0f14a2f2-0bc9-4ba1-b977-e5e2ce044b60.png" width=30%>|6|
|crook|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/cb4e55f0-5d3d-4a8c-8a3f-15390dbbd66a.png" width=30%>|12|
|crown|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/e258be28-2edc-43cc-931e-85e64173a9af.png" width=30%>|6|
|sphinx|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/a5ca230e-41c7-4113-82c9-d7efd0414dcc.png" width=30%>|12|
|snake|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/bd8136d6-69c2-41de-be5c-6dc864a439df.png" width=30%>|6|
|yacht|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/dc4511d1-f85f-4cf8-a31e-5a3d25a4c11b.png" width=30%>|12|
|chevron|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/645333f5-aa6d-4770-b2f5-80611870372e.png" width=30%>|6|
|signpos|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/111b5093-1daa-4f36-84c1-695b3944ae8a.png" width=30%>|12|
|lobster|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/00d7199f-7a0a-48ff-8d0f-23ec8c35f107.png" width=30%>|6|
|hook|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/81cfb74b-b486-474e-a206-be124f94f4bb.png" width=30%>|12|
|hexagon|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/418d0a5c-2f5f-4fc4-84c7-51cc09ab2faa.png" width=30%>|1|
|butterfly|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/1b938a35-19fa-43c1-b4be-1235af770e80.png" width=30%>|3|
|**Total** || **94** |

ピースをデータ化するときに重要なのが(0,0)を逆三角形ではないところに置くことです。これによってボードに各ピースを置く時に正しい位置にセットできます。

例えば**3-crown**の場合なら左から2番目のセルを(0,0)にします。

```python 
[(-1, 0), (0, 0), (1, 0), (1, 1), (2, 0), (3, 0)]  # crown
```

### DLXを用いて回転・鏡映ありで6x6ひし形を解く

#### ボード+ピースIDの列データを作る

これはペントミノの時と全く同じです

```python 
boardset = {(x+y, y) for x in range(bx) for y in range(by)}
from dlx import DLX
columns = [(bn, 0) for bn in boardset]+[((pn+100,0),0) for pn in range(len(hexiamond))]
colidx = {cname[0]: i for i, cname in enumerate(columns)}    # column index
print(len(colidx), colidx)
dlx = DLX(columns)
# 84 {(0, 0): 0, (1, 0): 1, (1, 1): 2, , ...(100, 0): 72, (101, 0): 73, 
```

#### 各ピースをボードに置いた行データを入力

これもほぼ同じですが。ピースの(0,0)のセルは逆三角形のところには置けないので(x+y)が偶数の位置にだけ置くように2行追加しました。

```python 
for i, [pn, pc] in enumerate(pieces):
  for bn in boardset:  # move all over the board
    bx, by = bn                         #***********************************************
    if (bx+by)%2 != 0: continue         #***** (0,0) must be placed on (x+y)%2 == 0 ****
    cells = {addxy(bn,p) for p in pc}   # get moved piece
    if cells <= boardset:               # if piece in the board
      row = sorted([colidx[c] for c in cells]+[len(boardset)+pn])
      dlx.appendRow(row)   # add row
```
#### 解答を取り出す
これは全く同じです

```python 
ans = []
for k, solution in enumerate(dlx.solve()):
  ans += [[sorted(dlx.getRowList(i))for i in solution]]
print(f"Number of answers = {k+1}")

Number of answers = 624
```
解答数は624となりましたが対称のものを除くと312個です。

答えの一つを表示します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/d736e5e5-9107-43eb-8215-58b96a1d25d1.png)

### テンヨー ヘキサモンド を解く

それではテンヨーのパズルを解きます。といってもボードのデータを変更するだけです。

```python 
bx, by = 7*2, 7
boardset = {(x+y, y) for x in range(bx) for y in range(by)}
tr1 = {(0,0),(1,1),(1,0),(2,0),(2,2),(2,1),(3,1),(3,0),(4,0)}
tr2 = {addxy((19,6), t1, -1) for t1 in tr1 }
diff1 = {(6,6),(7,6)}
diff2 = {(10,0),(11,0),(12,0),(13,0),(13,1),(14,1)}
boardset -= tr1 | tr2 | diff1 | diff2
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/f9305678-cbce-41e8-803a-b70582b2f710.png)

```python
 Number of answers = 9936
```
対称なものを除いて**4968通り**で見事に一致しました。

最初の25個の解答を表示します

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/f7967b35-8def-4491-b993-388d0a9ecaeb.png)


（開発環境：Google Colab）