ポリオミノの敷き詰め問題を解くプログラムを書いた。効率的に解くためにDancing Linksというデータ構造を実装し、Knuth's Algorithm Xを使用した。
ポリオミノの敷き詰め問題とは
こういうパズルがAmazonで売っている。結構難しい。
このポリオミノの敷き詰めパズルをプログラムで解くために下記の順番で話を進めていく。
- exact cover problem
- Knuth's Algorithm X
- Dancing Links
- ポリオミノの敷き詰め問題をexact cover problemとして考える
- 実装
exact cover problemとは
要素の集合X
、X
の部分集合の集合S
、S
の部分集合S*
について、
X
のそれぞれ要素がS*
の要素のうち1つにだけ含まれるとき、S*
をX
のexact coverという。
X
, S
が与えられるのでexact coverであるS*
を列挙したい。
例を示す。
要素の集合 X = {0, 1, 2} Xの部分集合の集合 S = { A: {0}, B: {1}, C: {0, 1}, D: {2}, E: {0, 2}, } exact cover S* = {A, B, D}, {B, E}, {C, D}
exact cover problemはNP-completeで全探索するしかないらしい。Karp's 21 NP-complete problems - Wikipedia
Knuth's Algorithm Xの分かりやすい解説
exact cover problemを効率よく全探索するアルゴリズムとして、Knuth's Algorithm Xがある。 アルゴリズムの説明は下記が詳しい。
Knuth's Algorithm Xの要点
どの部分集合を使うか深さ優先探索でBackTrackingして解く。
- すべての要素が集まっていれば、それが解。
- その要素を持っている部分集合が存在しなければ、1段階戻る。
- その要素を持っている部分集合が少ないものを選択する。
- 選択された部分集合といずれかの要素が重複している部分集合を候補から外す。
- 1に戻る。
実装の一部
def algorithm_x(self): """solves exact cover problem algorithm_x() -> List[List[int]] Exact Coverの部分集合のインデックス列を返す。 """ result = [] def _algorithm_x(sss): if self.is_empty(): result.append(set(sss)) else: # 列の選択 min_header = self.head.right header = min_header while header is not self.head: # 埋めることができない要素がある場合はpopする if header.size == 0: return None if header.size < min_header.size: min_header = header header = header.right column_node = min_header.down while column_node is not min_header: self.cover(column_node) sss.append(column_node.row_index) _algorithm_x(sss) sss.pop() self.uncover(column_node) column_node = column_node.down _algorithm_x([]) return result
Dancing Linksとは
上記のKnuth's Algorithm Xを効率よく実行するためのデータ構造。2次元で十字方向にリンクを張った双方向リスト。 Dancing Linksの(1), (2)にある通り、あるノードのをリストから切り離すこと、リストに戻すことは簡単に行える。 特に戻す処理でリンクから切り離された側のノードにどこに戻すべきかの情報が残っているところに感動した。
class Node: def __init__(self, row_index, column_index): self.row_index = row_index self.column_index = column_index self.head = self self.up = self self.down = self self.left = self self.right = self class Header(Node): """ columnのheader """ def __init__(self, row_index, column_index): super().__init__(row_index, column_index) self.size = 0 class DancingLinks: """ 上下左右にNodeが連なったデータ構造 行数: |subsets| 列数: |collection_size| """ def __init__(self, collection_size, subsets): self.n = collection_size self.m = len(subsets) self.head = Header(-1, -1) self.headers = [] for column_index in range(collection_size): header = Header(-1, column_index) self.insert_header(header) self.headers.append(header) for row_index, row in enumerate(subsets): if not row: continue row_header = Node(row_index, row[0]) column_header = self.headers[row[0]] self.insert_to_column(column_header, row_header) for column_index in row[1:]: node = Node(row_index, column_index) column_header = self.headers[column_index] self.insert_to_column(column_header, node) self.insert_to_row(row_header, node) def insert_header(self, header): """headerをheadの行に追加する。 """ header.right = self.head header.left = self.head.left self.head.left.right = header self.head.left = header def insert_to_row(self, row_header, node): """行にノードを追加する。 """ node.right = row_header node.left = row_header.left row_header.left.right = node row_header.left = node def insert_to_column(self, column_header, node): """列にノードを追加する。 """ column_header.size += 1 node.head = column_header node.up = column_header.up node.down = column_header column_header.up.down = node column_header.up = node def cover(self, selected_node): """ selected_nodeを含む行を選択する。 """ node = selected_node while True: # column_headerをheadから外す header = node.head header.left.right = header.right header.right.left = header.left column_node = header.down while column_node is not header: # 選べなくなる要素を列から外していく row_node = column_node.right while row_node is not column_node: row_node.up.down = row_node.down row_node.down.up = row_node.up row_node.head.size -= 1 row_node = row_node.right column_node = column_node.down node = node.right if node is selected_node: break def uncover(self, selected_node): """ selected_nodeを含む行を選択解除する。 """ node = selected_node while True: # column_headerをheadつなげる header = node.head header.left.right = header header.right.left = header column_node = header.down while column_node is not header: row_node = column_node.right while row_node is not column_node: row_node.up.down = row_node row_node.down.up = row_node row_node.head.size += 1 row_node = row_node.right column_node = column_node.down node = node.right if node is selected_node: break
ポリオミノの敷き詰め問題への適用
ポリオミノの敷き詰め問題(=すべてのポリオミノを1回ずつ使って、すべての領域を敷き詰める問題)をexact cover problemとして解釈したい。
ポイント: 「敷き詰める領域」と「使用したポリオミノ」をXの要素とする。
例として3x3の領域にA,B,Cの3種類のポリオミノを敷き詰めるケースを考える。
... ... ... A ooo o.. B oo o. C oo
各ポリオミノPi
について、回転・裏返しで作ることができるバリエーションパターン(8通り以下)を列挙しVi
とする。
バリエーションパターンを得る実装は下記。
class Polyomino: def __init__(self, form, name='-'): self.name = name self.form = copy.deepcopy(form) self.y_size = len(self.form) self.x_size = len(self.form[0]) def rotate(self, times=1): if times == 1: self.form = [[self.form[self.y_size - 1 - x][y] for x in range(self.y_size)] for y in range(self.x_size)] elif times == 2: self.form = [[self.form[self.y_size - 1 - y][self.x_size - 1 - x] for x in range(self.x_size)] for y in range(self.y_size)] elif times == 3: self.form = [[self.form[x][self.x_size - 1 - y] for x in range(self.y_size)] for y in range(self.x_size)] self.y_size = len(self.form) self.x_size = len(self.form[0]) def reverse(self): reversed_form = [[False for j in range( self.x_size)] for i in range(self.y_size)] for y in range(self.y_size): for x in range(self.x_size): reversed_form[y][self.x_size - 1 - x] = self.form[y][x] self.form = reversed_form def generate_variations(self): """ () -> List[Polyomino] """ variations = set() p = copy.deepcopy(self) for _rev in range(2): p.reverse() for _rot in range(4): p.rotate() f = copy.deepcopy(p.form) variations.add(json.dumps(f)) return list(map(lambda f: Polyomino(f, self.name), sorted(list([json.loads(f) for f in variations]))))
各バリエーションパターンVi
について3x3の敷き詰め領域のどこに置くことができるか列挙する。
3x3の領域に下記のように付番し、Vij
をおける位置を探す。
012 345 678
ooo o--
置ける位置は下記の2通りになる。
(0, 1, 2, 3)
(3, 4, 5, 6)
同様に他のバリエーションパターンについても列挙する。
これらのバリエーションパターンは1つの同じポリオミノが置かれる可能性のある位置を示している。
1つのポリオミノは一箇所にしか置けないため、(A,B,C)
もX
の要素(9,10,11)
として扱う。
上記の(0, 1, 2, 3)
, (3, 4, 5, 6)
はA=9
のポリオミノを置くため、(9, 0, 1, 2, 3)
, (9, 3, 4, 5, 6)
と変換し、これらを部分集合S
の要素として扱う。
これですべてのポリオミノを1回ずつ使って、すべての領域を敷き詰める問題がexact cover problemとして扱うことができるようになった。
結果
... ... ... A ooo o.. B oo o. C oo
[[10, 4, 5, 8], [9, 0, 3, 6, 7], [11, 1, 2]] ACC ABB AAB [[10, 1, 2, 4], [9, 0, 3, 6, 7], [11, 5, 8]] ABB ABC AAC [[9, 0, 1, 3, 6], [11, 2, 5], [10, 4, 7, 8]] AAC ABC ABB [[10, 2, 4, 5], [9, 0, 1, 3, 6], [11, 7, 8]] AAB ABB ACC [[11, 7, 8], [9, 0, 1, 2, 5], [10, 3, 4, 6]] AAA BBA BCC [[11, 3, 6], [9, 0, 1, 2, 5], [10, 4, 7, 8]] AAA CBA CBB [[10, 4, 6, 7], [11, 5, 8], [9, 0, 1, 2, 3]] AAA ABC BBC [[11, 6, 7], [10, 4, 5, 8], [9, 0, 1, 2, 3]] AAA ABB CCB [[9, 5, 6, 7, 8], [10, 0, 3, 4], [11, 1, 2]] BCC BBA AAA [[9, 1, 2, 5, 8], [11, 6, 7], [10, 0, 3, 4]] BAA BBA CCA [[10, 0, 1, 4], [11, 3, 6], [9, 2, 5, 7, 8]] BBA CBA CAA [[10, 0, 1, 4], [11, 2, 5], [9, 3, 6, 7, 8]] BBC ABC AAA [[11, 0, 3], [9, 1, 2, 5, 8], [10, 4, 6, 7]] CAA CBA BBA [[11, 0, 3], [9, 5, 6, 7, 8], [10, 1, 2, 4]] CBB CBA AAA [[10, 2, 4, 5], [11, 0, 1], [9, 3, 6, 7, 8]] CCB ABB AAA [[9, 2, 5, 7, 8], [11, 0, 1], [10, 3, 4, 6]] CCA BBA BAA
16通りの敷き詰め方法が出力されている。Aの置き方8通り×それぞれのAの置き方についてBの置き方2通り×CはAとBを置くと一意に決まる=16通りなのでこれは正しい。
実装
実装はGitHub/matsu7874/polyomino: ポリオミノの敷き詰め問題を解くプログラムに置いてある。
パズル紹介
チョコレートパズル(easy)とプラパズル(hard)は2次元でソーマキューブは3次元(very hard)。