有名なパズルのペントミノ (Wikipedia)を解くコードを紹介します。なるべく分かりやすく、以下のステップでコードを作っていきます。
- ペントミノのピースのデータ構造
- ボードのデータ構造
- まず回転・鏡映はしないで10x6の長方形を作るコードを総当りで作る
- Exact cover (Wikipedia)の考え方
- Exact cover問題を解くdancing linksのpackage、PyPIのDLXの説明
- 回転・鏡映をしたピースのデータを作る
- ペントミノをExact Cover問題として考える
- DLXを用いて回転・鏡映ありで10x6の長方形を解く
1. ペントミノのピースのデータ構造
このペントミノの12個のピースを構成する5個の正方形のセルの相対座標を$(x,y)$のリストで定義します。どこを原点にするかで変わってきますがそれは気にしなくても大丈夫です。まずは回転等しなくても答えが出るように上の図形と同じ向きしました。
pentomino = [
[(2,0),(0,1),(1,1),(2,1),(1,2)], # F/0
[(0,0),(0,1),(0,2),(0,3),(0,4)], # I/1
[(0,1),(1,1),(2,1),(3,1),(3,0)], # L/2
[(1,0),(2,0),(3,0),(0,1),(1,1)], # N/3
[(0,0),(0,1),(0,2),(1,1),(1,2)], # P/4
[(0,0),(1,0),(2,0),(1,1),(1,2)], # T/5
[(0,0),(1,0),(1,1),(0,2),(1,2)], # U/6
[(2,0),(2,1),(0,2),(1,2),(2,2)], # V/7
[(1,0),(2,0),(0,1),(1,1),(0,2)], # W/8
[(1,0),(0,1),(1,1),(2,1),(1,2)], # X/9
[(1,0),(0,1),(1,1),(2,1),(3,1)], # Y10
[(1,0),(2,0),(1,1),(0,2),(1,2)]] # Z/11
2. ボードのデータ構造
10x6の長方形を(x,y)の1次元リストで表します。
X, Y = 10, 6
board = [(x,y) for y in range(Y) for x in range(X)]
3. 回転・鏡映はしないで10x6の長方形を作るコードを総当りで作る
この準備として以下の2点を行います。
ピース上の最初のセルを原点に変換する
これによってピースの原点をボードの空きセルに合わせれば移動したピースの位置の候補が列挙できるようになります。
def addxy(xy1, xy2, s=1):
(x1, y1), (x2, y2) = xy1, xy2
return (x1+s*x2, y1+s*y2)
# Normalize (no rotate/reflect)
pieces = []
for pn, pc in enumerate(pentomino):
pc1 = [(pn,0), [addxy(c,pc[0],-1) for c in pc]]
print(pc1)
pieces += [pc1]
# [(0, 0), [(0, 0), (-2, 1), (-1, 1), (0, 1), (-1, 2)]]
# [(1, 0), [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]]
# [(2, 0), [(0, 0), (1, 0), (2, 0), (3, 0), (3, -1)]]
# [(3, 0), [(0, 0), (1, 0), (2, 0), (-1, 1), (0, 1)]]
# [(4, 0), [(0, 0), (0, 1), (0, 2), (1, 1), (1, 2)]]
# [(5, 0), [(0, 0), (1, 0), (2, 0), (1, 1), (1, 2)]]
# [(6, 0), [(0, 0), (1, 0), (1, 1), (0, 2), (1, 2)]]
# [(7, 0), [(0, 0), (0, 1), (-2, 2), (-1, 2), (0, 2)]]
# [(8, 0), [(0, 0), (1, 0), (-1, 1), (0, 1), (-1, 2)]]
# [(9, 0), [(0, 0), (-1, 1), (0, 1), (1, 1), (0, 2)]]
# [(10, 0), [(0, 0), (-1, 1), (0, 1), (1, 1), (2, 1)]]
# [(11, 0), [(0, 0), (1, 0), (0, 1), (-1, 2), (0, 2)]]
ボードの空きエリアをsetで表す
こうすることによってピースが空きエリアに収まるかどうかを簡単に表現できます。
freearea = set(board)
総当たりのコード
stackには(ピース番号、置いた座標のリスト、空きエリア)が入ります。次のピース入るかをチェックして入れば、その分空きエリアを狭めて行き、空きエリアが０になればゴールです。
stack = [(0, [], freearea)] # piece number, position list, free area
while stack:
pn, st, freearea = stack.pop()
if len(freearea) == 0: break # Answer found
for fcell in freearea:
cells = {addxy(fcell,p) for p in pieces[pn][1]} # move pieces all over the free area
if cells <= freearea: # if cells fits in free area
stack += [(pn+1, st+[fcell], freearea - cells)] # decrease free area
print("***** Goal : ", st, freearea)
# ***** Goal : [(6, 1), (0, 1), (5, 4), (5, 0), (1, 3), (0, 0), (8, 0), (9, 3), (3, 0), (3, 2), (4, 4), (7, 1)] set()
このコードでピースが入るかどうかの判定はこの1行で書けることに注目して下さい。
if cells <= free: # if cells fits in free area
出た答えはピース０の原点が$(6,1)$, ピース1の原点が$(0,1)$, ...となることを示しています。この回答を図示して最初の図形と一致しているのを確認しました。
ただこの全探索だと回転・鏡映なしでも約４分かかるので、画期的な高速化が必要をなります。そのためにこの問題をExact cover問題に置き換えて考える方法を次回のその２で説明したいと思います。
（開発環境：Google Colab）