ポリオミノの敷き詰め問題をDancing LinksとKnuth's Algorithm Xを使って解く

ポリオミノの敷き詰め問題を解くプログラムを書いた。効率的に解くためにDancing Linksというデータ構造を実装し、Knuth's Algorithm Xを使用した。

ポリオミノの敷き詰め問題とは

こういうパズルがAmazonで売っている。結構難しい。

このポリオミノの敷き詰めパズルをプログラムで解くために下記の順番で話を進めていく。

  1. exact cover problem
  2. Knuth's Algorithm X
  3. Dancing Links
  4. ポリオミノの敷き詰め問題をexact cover problemとして考える
  5. 実装

exact cover problemとは

要素の集合XXの部分集合の集合SSの部分集合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. すべての要素が集まっていれば、それが解。
  2. その要素を持っている部分集合が存在しなければ、1段階戻る。
  3. その要素を持っている部分集合が少ないものを選択する。
  4. 選択された部分集合といずれかの要素が重複している部分集合を候補から外す。
  5. 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)。