ペントミノをExact cover問題として解く（その１）ではペントミノ・パズルをExact cover問題としてPyPIのDLX packageを用いて解く方法を紹介しました。
今回は応用問題としてヘキサモンド・パズル（テンヨー(Tenyo) ヘキサモンド 脳ブロック 永久に遊べるパズル 総数4,968通り）を解いて行きたいと思います。
ボードの構造
まず考える必要があるのはボードの構造ですが、なるべくペントミノの考えをそのまま使いたいので同じような構造にしました。正三角形の上下が交互にあるのでそこだけ考慮が必要です。
ヘキサモンドのピース
ピースの形はAn Introduction to Polyiamondsを参考にしました。
12個のピースに各々名前がついているようです。
ピースの変形（回転・鏡映）
問題なのはその変形（回転・鏡映）がいくつあるかです
- 回転は(0,120,240)の3通り
- 鏡映はなし・上下・左右・上下左右の4通り
の最大12通りが考えられます。10-hookの例を示します。
この場合は12通りとも違うものになりますが同じになるものを除くとピースごとの数は以下になります。
計94種類の形をDLXに渡すデータとします。
| ピース名 | 画像 | 種類（回転・鏡映） |
|---|---|---|
| bar |  |
6 |
| crook |  |
12 |
| crown |  |
6 |
| sphinx |  |
12 |
| snake |  |
6 |
| yacht |  |
12 |
| chevron |  |
6 |
| signpos |  |
12 |
| lobster |  |
6 |
| hook |  |
12 |
| hexagon |  |
1 |
| butterfly |  |
3 |
| Total | 94 |
ピースをデータ化するときに重要なのが(0,0)を逆三角形ではないところに置くことです。これによってボードに各ピースを置く時に正しい位置にセットできます。
例えば3-crownの場合なら左から2番目のセルを(0,0)にします。
[(-1, 0), (0, 0), (1, 0), (1, 1), (2, 0), (3, 0)] # crown
DLXを用いて回転・鏡映ありで6x6ひし形を解く
ボード+ピースIDの列データを作る
これはペントミノの時と全く同じです
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行追加しました。
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
解答を取り出す
これは全く同じです
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個です。
答えの一つを表示します。
テンヨー ヘキサモンド を解く
それではテンヨーのパズルを解きます。といってもボードのデータを変更するだけです。
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
Number of answers = 9936
対称なものを除いて4968通りで見事に一致しました。
最初の25個の解答を表示します
（開発環境：Google Colab）