ポリオミノのピースの数を求める

ポリイアモンドのピースの数を求めるでは正三角形を組み合わせたポリイアモンドがそれぞれいくつあるのかを求めましたが、今回はより簡単な正方形を組み合わせたポリオミノ (Wikipedia)のピースの数と種類を求めます。

ポリオミノの種類を求めるアルゴリズム

前回と同様に$n-1$のポリオミノに正方形を一つ加えて回転・鏡映で同じにならないものをリストするという力技です。

• $n=1$は正方形一つ
• $n-1$のポリオミノの一つの辺に連結した正方形を一つ足す
• それらを8通りに回転・鏡映したものが既になければ集合に加える
• それをすべての辺について行う

コーディング

データ構造はペントミノをExact cover問題として解く（その１）で作ったものを使い、8通りに回転・鏡映は（その３）で作った generate_variants をそのまま使います。

• ゲーム板に$n-1$のポリオミノを置く
• 空エリアに十字型を置いてこれと$n-1$のポリオミノの重なりがあれば、十字型の中心は$n-1$のポリオミノに連結した正方形なので、これを足したピースを newpとする
• 8通りに回転・鏡映を作ってどれもすでに作ったものと同じでなければ集合 newpolyに加える

def cross(xy):
  x, y = xy
  return {(x,y), (x+1,y), (x-1,y), (x,y-1), (x,y+1)}   # self + 4 neibers

N = 6
for i in range(2, N+1):
  X, Y = 15, 15
  free = {(x,y) for y in range(-Y, Y) for x in range(-X, X)}   # free area
  newpoly = set()
  for pl in poly:
    pls = set(pl)
    free1 = free - pls
    for f in free1:    # for all free area
      if (pls & cross(f)) != set():           # if connected cell
        newp = normalize(list(pls|set([f])))  # normalize new piece
        if newpoly == set() or (newpoly & generate_variants(newp) == set()):
          newpoly.add(tuple(newp))
  print(f"| {i} | {len(newpoly)} |")
  poly = newpoly
#| 2 | 1 |
#| 3 | 2 |
#| 4 | 5 |
#| 5 | 12 |
#| 6 | 35 |

n=6 ヘキソミノのピース35個

このコードで作ったn=6 ヘキソミノのピースを表示します。

（開発環境：Google Colab）