8めくりパズル


藤原博文さんのHPの中の「パズル生活つれづれノート」のコーナーで掲記のパズルの紹介があり、ルールや解法のヒントが説明されています。そして、「やさしい問題なので解いてみてください」というコメントがありました。
この甘い言葉に乗せられて、軽い気持ちで、32x32の解を得ようと手を染めてみましたが、大分苦労を余儀なくされ、最後は、じっと我慢の3日間でした。

□ ソース& 実行ファイル

ソース本体: unit1.cpp(14KB)
ヘッダファイル:unit1.h(3KB)

説明書:readme.txt(2KB)
実行ファイル:turnover.exe(258KB)
サンプルログ:log.txt(4KB)

□ 結果

測定環境:Pentuim 150MHz,メモリ40MB

大きさ
(mxn)
最小手数 探索時間
(秒)
(参考)
4x4 6
6x6 16*
8x8 32*
10x10 60*
12x12 84*
14x14 72 0.4 1.5
16x16 92 1.1 12
18x18 148* 4.4 66
20x20 180* 33.7 238
22x22 248* 112 1949
24x24 276 487 9436
26x26 396* 2834
28x28 428* 11256
30x30 384* 48871
(13.5h)
32x32 448* 272857
(76h)

* : 唯一の解しか存在しない(Ex.14x14には*がないので複数の解が存在する)
参考に示した時間は、「1マス毎にチェックする方式」を採用した場合の探索時間


<<解の存在しないパターン>>

どのような大きさのパネルでも解が存在する訳ではなく、以下のようなパターンでは解が存在しません。このパターンには規則性があるのでその理由を考察すると面白い結果が得られるかもしれません。

(1x1)系列 (1x5)系列 (1x9)系列 (1x13)系列 (1x17)系列
(1) 1x1 1x5 1x9 1x13 1x17
(2) 3x3 3x11 3x19
(3) 5x5 5x9 5x13 3x17 5x21
(4) 7x7 7x23
(5) 9x9 9x13 9x17 9x21 9x25
(6) 11x11 11x19 11x17
(7) 13x13 13x17 13x21 13x25 13x19
(8) 15x15
(9) 17x17 17x21 17x25 17x29 17x33

注: − の部分は解が存在する

(1x5)系列と(1x13)系列は1つおきに解が存在する。
(1x9)系列は3つおきに解が存在する。
(1x17)系列は7つおきに解が存在するかも(15x31は解がある)

<<32x32の解>>

■がpushする位置です。
==== (32,32) 448 pushes ====
□■■□□■■□□■■□□■■□□■■□□■■□□■■□□■■□
■■□■■□■■□■■□■■□■■□■■□■■□■■□■■□■■
■□■□□■□■□■■□■□■□□■□■□■■□■□■□□■□■
□■□□□□■□□■■□□■□□□□■□□■■□□■□□□□■□
□■□□□□■□□□□□□■□□□□■□□□□□□■□□□□■□
■□■□□■□■□■□□□■■■■■■□□□■□■□■□□■□■
■■□■■□■■□□■■■■■□□■■■■■□□■■□■■□■■
□■■□□■■□□□■□□□■□□■□□□■□□□■■□□■■□
□□□□□□□□□□■□□□■□□■□□□■□□□□□□□□□□
■■■■□■□□□■□■□□■■■■□□■□■□□□■□■■■■
■■■■□□■■■□■■□■□□□□■□■■□■■■□□■■■■
□□□□□□■□□■■□□□□□□□□□□■■□□■□□□□□□
□■■□□□■□□□□□□■■□□■■□□□□□□■□□□■■□
■■□■■■■□□□■□■■□■■□■■□■□□□■■■■□■■
■□■□□■■■■■□□■□■□□■□■□□■■■■■□□■□■
□■□□□■□□□■□□□■□□□□■□□□■□□□■□□□■□
□■□□□■□□□■□□□■□□□□■□□□■□□□■□□□■□
■□■□□■■■■■□□■□■□□■□■□□■■■■■□□■□■
■■□■■■■□□□■□■■□■■□■■□■□□□■■■■□■■
□■■□□□■□□□□□□■■□□■■□□□□□□■□□□■■□
□□□□□□■□□■■□□□□□□□□□□■■□□■□□□□□□
■■■■□□■■■□■■□■□□□□■□■■□■■■□□■■■■
■■■■□■□□□■□■□□■■■■□□■□■□□□■□■■■■
□□□□□□□□□□■□□□■□□■□□□■□□□□□□□□□□
□■■□□■■□□□■□□□■□□■□□□■□□□■■□□■■□
■■□■■□■■□□■■■■■□□■■■■■□□■■□■■□■■
■□■□□■□■□■□□□■■■■■■□□□■□■□■□□■□■
□■□□□□■□□□□□□■□□□□■□□□□□□■□□□□■□
□■□□□□■□□■■□□■□□□□■□□■■□□■□□□□■□
■□■□□■□■□■■□■□■□□■□■□■■□■□■□□■□■
■■□■■□■■□■■□■■□■■□■■□■■□■■□■■□■■
□■■□□■■□□■■□□■■□□■■□□■■□□■■□□■■□

他の大きさの解は、こちらです。


Home
Up
Back
Next