n-ominoの列挙（Redelmeier's algorithm）

n-ominoとはn個の正方形で構成されるポリオミノ(Wikipedia)。

n-ominoの列挙を行うRedelmeier's algorithmをPythonで実装した。

速度検証

反転・回転を考慮しないn-ominoを列挙し、個数を数えた。所要時間は下記の通りだった。

n	n-omino	elapsed[s]
1	1	0.000000
2	2	0.000000
3	6	0.000000
4	19	0.000000
5	63	0.000000
6	216	0.001007
7	760	0.004043
8	2725	0.015034
9	9910	0.060160
10	36446	0.271756
11	135268	1.160055
12	505861	4.801800
13	1903890	19.925538
14	7204874	83.391903

検証環境

Python 3.6.2
Windows 10
Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz

Redelmeier's algorithm

Counting polyominoes: Yet another attack - ScienceDirectにPDFがある。

アルゴリズムを３行で説明するとこんな感じ。

monominoから深さ優先探索的に成長させていくことでn-ominoを全列挙する
探索範囲はmonomino(0, 0)から開始としてy>0 or (y==0 and x>=0)の範囲に限定する
候補点に付番しながら探索を進め、既に選択したいずれかのマスより若いマスを選択しないようにすることで重複を防ぐ

実装

import time
import unittest


def enumerate_n_omino(n: int):
    """
    Redelmeier's algorithm
    fixed（回転・反転を考慮しない）なポリオミノを列挙する。
    """
    if n < 1:
        return []

    UNORDER = -1
    MAX_Y = n
    MAX_X = 2 * n - 1
    X_CENTER = n - 1
    DYDX = ((1, 0), (0, 1), (-1, 0), (0, -1))

    ominos = []

    visited = [[False] * MAX_X for i in range(MAX_Y)]
    visited_queue = []
    order = [[UNORDER] * MAX_X for i in range(MAX_Y)]
    ordered_queue = []
    border = set()

    # (0,0)から探索を始める
    visited_queue.append((0, X_CENTER))
    visited[0][X_CENTER] = True
    order[0][X_CENTER] = 0

    max_visited = 0
    next_order = 1
    max_x = X_CENTER
    min_x = X_CENTER
    max_y = 0

    def dfs(y: int, x: int, last: int) -> None:
        nonlocal next_order, max_visited, ominos, max_x, min_x, max_y

        if last == 0:
            ominos.append(
                [row[min_x:max_x + 1] for row in visited[:max_y + 1]])
            return

        # (y, x)に隣接セルに付番する
        for dy, dx in DYDX:
            ny = y + dy
            nx = x + dx
            if (ny == 0 and nx < n) or not (0 <= ny < MAX_Y and 0 <= nx < MAX_X):
                continue
            if order[ny][nx] == UNORDER:
                order[ny][nx] = next_order
                next_order += 1
                border.add((ny, nx))
                ordered_queue.append((y, x, ny, nx))

        # セルを追加可能な箇所を列挙する
        for ny, nx in list(border):
            # if (ny == 0 and nx < n) or not (0 <= ny < MAX_Y and 0 <= nx < MAX_X):
            #     continue
            if order[ny][nx] > max_visited:
                # 深さ+1
                visited[ny][nx] = True
                visited_queue.append((ny, nx))
                pre_max_visited = max_visited
                max_visited = order[ny][nx]
                border.remove((ny, nx))

                pre_max_y = max_y
                pre_max_x = max_x
                pre_min_x = min_x
                max_y = max(max_y, ny)
                max_x = max(max_x, nx)
                min_x = min(min_x, nx)

                # 再帰
                dfs(ny, nx, last - 1)

                # 深さ-1
                # 遷移先で付番したものをキャンセルする
                while ordered_queue and (ny, nx) == (ordered_queue[-1][0], ordered_queue[-1][1]):
                    _y, _x, py, px = ordered_queue.pop()
                    order[py][px] = UNORDER
                max_y = pre_max_y
                max_x = pre_max_x
                min_x = pre_min_x
                border.add((ny, nx))
                max_visited = pre_max_visited
                visited_queue.pop()
                visited[ny][nx] = False

    dfs(0, X_CENTER, X_CENTER)

    return ominos


class TestEnumerateNOmino(unittest.TestCase):
    def test_enumerate_n_polyomino(self):
        cases = ((1, 1), (2, 2), (3, 6), (4, 19), (5, 63), (6, 216),
                 (7, 760), (8, 2725), (9, 9910), (10, 36446))
        for i, expect in cases:
            with self.subTest(i=i, expect=expect):
                ominos = enumerate_n_omino(i)
                self.assertEqual(len(ominos), expect)


def main():
    ominos = enumerate_n_omino(3)
    for omino in ominos:
        for row in omino:
            print(''.join(['#' if c else '-' for c in row]))
        print()
    print()
    print('|n|n-omino|elapsed[s]|')
    print('|---:|---:|---:|')
    for i in range(1, 15):
        start = time.time()
        ominos = enumerate_n_omino(i)
        elapsed = time.time() - start
        print('|{}|{}|{:04f}|'.format(i, len(ominos), elapsed))


if __name__ == '__main__':
    main()