テトリスのポリオミノについて。

　テトリスに出てくる形は全部で５個。それは全て正方形4つで構成されている。なら正方形の数によって何個の形が作れるのか。

　これは一般的にポリオミノと呼ばれている。一般解は存在しないらしいがもしかしたらめちゃくちゃ考えたら出てくるかもしれないのでぜひ考えてみてほしい。

　一個や二個の正方形なら、それを用いてできる形は一通り。三個なら二通り。N個なら？

import sys
import itertools

sys.setrecursionlimit(100000)

def normalize(polyomino):
    min_x = min(x for x, y in polyomino)
    min_y = min(y for x, y in polyomino)
    return frozenset((x - min_x, y - min_y) for x, y in polyomino)

def rotations_and_reflections(polyomino):
    shapes = []
    for k in range(4):
        rotated = frozenset((y, -x) for x, y in polyomino)
        shapes.append(normalize(rotated))
        reflected = frozenset((-x, y) for x, y in rotated)
        shapes.append(normalize(reflected))
        polyomino = rotated
    return set(shapes)

def add_square(polyomino, squares):
    neighbors = set()
    for x, y in polyomino:
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            neighbor = (x + dx, y + dy)
            if neighbor not in polyomino:
                neighbors.add(neighbor)
    new_polys = []
    for neighbor in neighbors:
        new_poly = polyomino | {neighbor}
        new_polys.append(new_poly)
    return new_polys

def generate_polyominoes(n):
    unique_polys = set()
    polys = [frozenset({(0,0)})]
    for i in range(1, n):
        new_polys = []
        for poly in polys:
            for new_poly in add_square(poly, polys):
                normalized = normalize(new_poly)
                min_shape = min(rotations_and_reflections(normalized))
                if min_shape not in unique_polys:
                    unique_polys.add(min_shape)
                    new_polys.append(new_poly)
        polys = new_polys
    return unique_polys

N = int(input("正方形の数 N を入力してください: "))
polyominoes = generate_polyominoes(N)
print(f"正方形が {N} 個のポリオミノの総数: {len(polyominoes)}")

• 注意点
  　プログラムは、自由ポリオミノ（回転や鏡映で同一視した場合）を生成する。しかし、N  が大きくなると計算時間とメモリ使用量が急激に増加するので、実用的には  N = 6程度までが現実的。また、再帰の深さを増やすためにsys.setrecursionlimit(100000) を設定しているが、環境によってはスタックオーバーフローが発生する可能性がある。