Solusion of L-Puzzle
Ｌパズルの解[2001.06.24]
Ｌパズルとは、一辺が1の正方形を4個または5個結合してできる(長辺が3または4の)大小２種類のＬ型のピースを一辺が奇数n(>=5)の正方形の盤に詰め込む問題である。ただし、大きいＬ型ピースは１枚だけ使用する。n \in [5..21]について、この解を全て求めるCプログラムを紹介する。
ここでは、正方形4個の小さいＬ型ピースをL4,正方形5個の大きいＬ型ピースを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ピースを置けない状態になったら、１つ前の段階に戻ってやり直す(backtrack)。全部のピースを配置できたら、その配列を表示し、解の個数を1つ増加させる。n=5,7の場合は、ほぼ瞬時に全部の解を得ることができるが、n>=9の場合は、かなり時間がかかるので、実用的ではない。
Ｌパズルの解は、n=5のとき、5個である。n=7のとき、62個である。n=9のとき、2243292個である。
[参考文献]
- [1]数学セミナー, 1994年10月号, 日本評論社.
- [2]米田 信夫(編), 斉藤 信男, 武市 正人, 石畑 清(著),"C-言語とプログラム",産業図書, p165-177, 1982, {1900円}.
| Last Update: 2005.06.12 |
| H.Nakao |