ドミノタイリングの数え上げ（その３）ー 畳タイリング＃１

ドミノタイリングの数え上げ（その２） ドミノタイリングをタイル張り問題として扱い、その他の格子グラフの問題にも適用できることを投稿しました。

今回は最初のドミノタイリングで以下の畳の敷き方のルールに沿ったものを考えます。これを以下では「畳タイリング」と呼びます

畳には4枚の角が1点で交わらないように敷き詰める「祝儀敷き（しゅうぎじき）」という決まりがあります。

4 x 4のドミノタイリング16通りのうち、畳タイリングは以下の２通りです（90度回転で同じになる）。これは8畳間の畳の敷き方ですね。

畳タイリングが$X \times Y$の長方形で何通りあるかを数えるプログラムを作ります。その１で作ったコードに以下の変更を加えます。

• ROWSの上の辺から下の辺のデータだけでしたが、各タイルのパターンも記録する
• カウントだけではなくて、実際のタイルのパターンをすべて記録する
• タイルのパターンをチェックして4枚の角が1点に交わっている場合があったらそこでやめる

build1rowを各タイルのパターンも記録するように変更

# directions U R D L
TILES = [(0,0,1,0),(0,1,0,0),(1,0,0,0),(0,0,0,1)]
X, Y = 2, 2

from copy import deepcopy
from collections import defaultdict
ROWS = defaultdict(list)
def build1row(i, lborder, ulist, dlist, tiles):
	if i == X:
		if lborder == 0:  # right edge
			ROWS[tuple(ulist)].append((tuple(dlist), tuple(tiles)))  # store both down-list and tile-list
		return
	for tn, (U, R, D, L) in enumerate(TILES):
		if L == lborder:  # Left matches left border value
			build1row(i+1, R, ulist + [U], dlist + [D], tiles+[tn])

build1row(0, 0, [], [], [])
for i, (k, v) in enumerate(ROWS.items(),1):
	print("# ", i, ":", k, v)
#  1 : (0, 0) [((1, 1), (0, 0)), ((0, 0), (1, 3))]
#  2 : (0, 1) [((1, 0), (0, 2))]
#  3 : (1, 0) [((0, 1), (2, 0))]
#  4 : (1, 1) [((0, 0), (2, 2))]

実際のタイルのパターンをすべて記録する（畳ルールチェック）

def NotTatami(r1, r2):
  for x in range(len(r1)-1):
    if r1[x] == 1 or r1[x] == 0 or r2[x] == 1 or r1[x+1] == 0: continue
    return True # Violate to Tatami rule
  return False

tb_edge = tuple([0]*X)  # top or bottom edg
dtilesT = []  # Store the answers
def dominotile(i, ulist, dtile):  # row,upper list, down list, tiles
  if i == Y:
    if ulist == tb_edge:
      dtilesT.append(dtile) 
    return 
  for dl, tl in ROWS[ulist]:
    if i > 0 and NotTatami(dtile[-1], tl):  # skip if violate to Tatami rule 
      continue
    tatami = dominotile(i+1, dl, dtile+[tl])

dominotile(0, tb_edge, [])
for i, dt in enumerate(dtilesT, 1):
	print("# ", i, dt)
#  1 [(0, 0), (2, 2)]
#  2 [(1, 3), (1, 3)]

これで以下の２つが求まります。ただし２ｘ２では畳ルールのあるなしで結果は同じです。

正方形の場合の畳タイリング

6 x 6 : ２通り

8 x 8 : ２通り

10 x 10 : ２通り

となり正方形の場合は大きさに関係なく２通りのように見えます。あと気になるのは畳タイリングが出来ないサイズとかがあるかです。

ということで、$2\le X \le Y \le 16$で畳タイリングが何通りあるかを求めてみました。気がついたことは、

• X＝Yのときはいつも２通り
• 7 x 10のときにはじめて畳タイリングできなくなる。そのあとY = X+3の場合はすべてできない

Y\X	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
2	2
3	3	-
4	4	4	2
5	6	-	3	-
6	9	6	3	2	2
7	13	-	3	-	2	-
8	19	10	5	2	1	2	2
9	28	-	5	-	1	-	2	-
10	41	16	6	4	2	0	1	2	2
11	60	-	8	-	3	-	0	-	2	-
12	88	26	8	4	4	2	0	0	1	2	2
13	129	-	11	-	3	-	1	-	0	-	2	-
14	189	42	13	6	3	4	2	0	0	0	1	2	2
15	277	-	14	-	3	-	3	-	0	-	0	-	2	-
16	406	68	19	8	4	2	4	2	0	0	0	0	1	2	2

何か規則性がありそうですね。（その４）では畳タイリングの場合の数だけを求める方法でもっと大きなサイズの値を求め、その規則性を探してみたいと思います。