009 - 立方体表面パズル

立方体表面パズルとは，6 つのピースを適切に組み合わせて表面に欠けのない中空の立方体を作るパズルである． パズルの各ピースは，単位小立方体を平面上に格子状に並べてできている． 1 辺の長さ n の立方体を作るピースは以下の 2 領域からなる．

• 中央領域 (青): 1 辺の長さ n−2 の正方形領域．単位立方体で埋め尽くされている．
• 周辺領域 (赤): 中央部分の外縁の幅 1 の領域． この領域の単位正方形の上には何もないか，単位立方体があるかである．

各ピースの単位立方体は面でつながっている． 各ピースは自由に回転して使ってよく， 表裏のどちらが組み立てた立方体の内側・外側になってもよい． 各ピースの中央領域上の単位立方体は組み立てた立方体の各面の中央に来なくてはならない．

たとえば，図 E-1 の 6 つのピース (Sample Input の最初のデータセットである) が与えられたとする． このとき，図 E-2 のように組み立てることで立方体を作れる．

Hadrian Hex 氏はたくさんの立方体表面パズルを収集していた．あるとき，それらのピースが混ざってしまい，どのピースを組み合わせれば立方体を作れるか分からなくなってしまった． そこで，与えられたピースの組合せによって立方体ができるかを判定するプログラムを作って Hex 氏を助けて欲しい．

入力は最大 200 データセットからなり，各データセットは次の形式で表される．

n
x_1,1x_1,2 … x_1,n
x_2,1x_2,2 … x_2,n
…
x_6n,1x_6n,2 … x_6n,n

各データセットの 1 行目には作る立方体の 1 辺の長さ n (3 ≤ n ≤ 9, n は奇数) が与えられる． 続く 6n 行に，6 つのピースが与えられる． 各ピースは n 行で表される． 各行は格子の 1 行に対応し，その行の各文字 (‘X’ または ‘.’) は対応する単位正方形上の単位立方体の有無を意味する． ‘X’ なら単位立方体があり，‘.’ なら空である．

各ピースの中央領域は各ピースのデータの中央に位置する．

入力の終わりは，ゼロだけからなる行で表される．

各データセットについて，立方体ができる場合には “Yes”，できない場合には “No” を出力せよ．

5
..XX.
.XXX.
XXXXX
XXXXX
X....
....X
XXXXX
.XXX.
.XXX.
.....
..XXX
XXXX.
.XXXX
.XXXX
...X.
...X.
.XXXX
XXXX.
XXXX.
.X.X.
XXX.X
.XXXX
XXXXX
.XXXX
.XXXX
XX...
.XXXX
XXXXX
XXXXX
XX...
5
..XX.
.XXX.
XXXXX
XXXX.
X....
....X
XXXXX
.XXX.
.XXX.
.....
.XXXX
XXXX.
.XXXX
.XXXX
...X.
...X.
.XXXX
XXXX.
XXXX.
.X.X.
XXX.X
.XXXX
XXXXX
.XXXX
.XXXX
XX...
XXXXX
XXXXX
.XXXX
XX...
0

Yes
No