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()
上記をenumerate_n_omino.pyとして、python -m unittest enumerate_n_omino.pyで列挙個数を検証する。
__main__での実行結果は3-omino（トロミノ・トリオミノ）６種類を列挙する。
#- ## # # # ## #- -# ## ## -# ###
max_y, max_x, min_xは必要のない領域を切り落とすために再帰前後で値を保持している。（このあたりもう少しスッキリかけると嬉しい。）
前回の記事（ポリオミノの敷き詰め問題をDancingLinksとKnuth's Algorithm Xを使って解く）の内容と合わせて、matsu7874/polyominoにライブラリ化したものを置いている。興味があれば使ってみて欲しい。
参考
- ポリオミノの列挙 - phyllo’s algorithm note | 日本語で書かれた唯一のブログ？
- chap14.pdf | 遷移図が非常に分かりやすい
- Submission #1141849 - RCO presents 日本橋ハーフマラソン 予選 | AtCoder | antaさんの実装
