長方形の隣接パターン

長方形を隣接させてポリオミノを作る方法について考える(図1)。

図1 長方形を隣接させてポリオミノを作る例

いつものように、長方形の境界線の間の接触関係が壊れないように変形して移り変われるものは同一とみなして、長方形の数に対して数え上げる。

なお、変形について、十字路は十字路、丁字路は丁字路を保つことを要求する。境界線をカーブデータ的に見ている、といえば伝わるだろうか。境界線で囲まれている面の部分は気にしない。

今回は長方形の数(箱数) n=1, 2, 3について列挙する。n=4については、途中までの結果を書いておく。

n=1とn=2

図2 箱数1と箱数2の列挙

n=3

箱が多くなると難しくなる。今回は、まず隣接に関するグラフを列挙して、そのグラフに向きの情報を与える方法を列挙して、最後に箱の形で列挙する。

箱数3については、図3に示すA~Dの4つに分類される。

図3 箱数3の分類方針

次に、A~Dの4つについて、それぞれ箱の配置をゴリゴリ列挙していく。

図4 箱数3のパターンAの列挙

図5 箱数3のパターンBの列挙

図6 箱数3のパターンCの列挙

図7 箱数3のパターンDの列挙

これで全て列挙できているはずであるが、見逃しが怖いところである。見逃し等を見つけられた方にはご連絡いただきたい。

n=4(途中まで)

箱数4はもう少し大変になるので、今回は途中までの結果を書く。具体的には、向きを与える分類までを行う。

向きまで含めた分類は、図8~図12に示すパターンA~Xの24通りとなった。ただ、やはり見逃し等が怖い。

※追記(2022/7/20):パターンXが抜けていたため追加。

図8 箱数4の分類(1)

図9 箱数4の分類(2)

図10 箱数4の分類(3)

図11 箱数4の分類(4)

図12 箱数4の分類(5)

この勢いで具体的な箱の配置の列挙を進めてもよいだろうが、なんとなく、数100通りくらいはありそうである。今日はこれくらいにしておく。