Homeに戻る  一覧に戻る 

Solusion of L-Puzzle


Lパズルの解[2001.06.24]


Lパズルとは、一辺が1の正方形を4個または5個結合してできる(長辺が3または4の)大小2種類のL型のピースを一辺が奇数n(>=5)の正方形の盤に詰め込む問題である。ただし、大きいL型ピースは1枚だけ使用する。n \in [5..21]について、この解を全て求めるCプログラムを紹介する。

ここでは、正方形4個の小さいL型ピースをL4,正方形5個の大きいL型ピースをL5と呼ぶ。よって、詰め込むピースの枚数は、L4が{(n2-5)/4}枚,L5が1枚である。盤とピースL4,L5を市松模様で白黒(角を黒とする)に塗り分けると、盤では黒が白より1個多いので、L5の角は白でなければならない。また、解の重複を避けるために、L5は常に裏返しでΓの向きとする。L4は回転・裏返して置いて良い(8通りの向き)。L5の角を置く位置[・]は(例えば、n=7の場合には)以下のように制限される。例えば、L5は(X,Y)=(1,0)の位置に置けないことに注意する。

+ X 0 1 2 3 4 5 6
0
1
Y 2
3
4
5
6

盤に最初のL5ピース(1枚のみ)を置いて、L4ピースを8通りの向きを試しながら順に置いていき、飛び地ができたり、新たなL4ピースを置けない状態になったら、1つ前の段階に戻ってやり直す(backtrack)。全部のピースを配置できたら、その配列を表示し、解の個数を1つ増加させる。n=5,7の場合は、ほぼ瞬時に全部の解を得ることができるが、n>=9の場合は、かなり時間がかかるので、実用的ではない。

Lパズルの解は、n=5のとき、5個である。n=7のとき、62個である。n=9のとき、2243292個である。

[参考文献]


Last Update: 2005.06.12
H.Nakao

Homeに戻る[Homeに戻る]  一覧に戻る[一覧2001に戻る]