ポリオミノを列挙する（アニメーション Gif つき） - Qiita

ポリオミノの数を算出する式を見つけるため、研究者らによりかなりの努力が行われてきたが、現状ではまだ発見に至ってはいない。 ポリオミノを列挙するアルゴリズムとして Redelmeier's algorithm というものがある。数え上げるので必然的に指数時間かかってしまうが、空間計算量は O(N) となるアルゴリズムである。 この記事では実際に JavaScript でアルゴリズムを実装し、これを視覚的に確認する。 Redelmeier's algorithm y > 0 or (y == 0 and x >= 0) となるようなセル空間を考える [0, 0] に番号を振り境界セルとする 境界セルを選択した際は以下作業を行う。 選択したセルの隣接セルの空いている箇所に辞書順（下左右上）に番号を振る 番号を振ったセルから１つずつ選択し境界セルとする ただし、既に境界セルである最大番号より小さい