先日のブログは15パズルを手で解く方法であった. 今回は計算機でやる話だ. 計算機による解法もいろいろあるが, とりあえずはプログラムを簡単にするという方針でいく.
下に14枚の図がある. これらはどれも4×4の15パズルの盤面の右下の3×3の部分を表している. その証拠はますの左上に斜体の数字で示す番地だ. まず図Aを見てほしい. 数字の代りに文字の変数でこまを示す. 空白のますには文字も書かない. 図Aの下にあるuldrはこれからこまを移動する方向である. 従ってまずgを上げる. hを左へ寄せる. eを下げる. gを右に寄せる. その結果が図Bだ. その矢印が示すように,
10,11,14,15の中でg,e,hが右回転したことになる. ほかのこまには影響しない.
この手順を右回転,
10,11,14,15の4ますを主戰場ということにする.
さて主戰場以外の場所のpを
14に移動し(この時ほかのこまに影響があってもよい), 右回転し,
14のこまをpにもどすと(影響はもとに戻って),
15にあったものがpに, pが
11に,
11が
15に移動したことになる.
p→11,11→15;15→p
どこかのこまを14に移動するには, 図C,Dに見るように, Cでurddluを実行する. するとDのように, 14,13,9,5,6のこまが左大回転する. gが2度のuで2段上に登るのは, 10に空白を残すためである.
ここで主戰場の右回転すると, Eになり, 先程の左大回転を逆回転するとFになって, f,e,hが回転する.
Gからの図では左大回転を2回実行し, 右回転, 右大回転2回で, d,e,hが回転することが分る. Kからの図は先に右大回転をすると, b,e,hが回転することを表す. ここには図がないが, Kの大回転を2回ずつ実行すると, a,e,hが回転することは容易に分る.
以上で5,6,9,13との交換はできたが, ほかの場所との交換は, 大回転の道順を工夫すればよいのも明らかだ. それが次の図である. 上の道順はルート0のつもりで, 左上のrt0である. 6のますに1, 7のますに2とあるのは, それぞれ右大回転を1回, 2回行うという意味だ. 9と13の2と1は左大回転の2回と1回を示す.
これを見れば, 主戰場の外のすべてのますを14へ移動する方法が分る.
これをまとめたのが以下で, 最初のrotは右回転, 続くrt0+, rt0-などはrt0の左大回転と右大回転である.
rot uldr
rt0+ urddlu
rt0- duuuld
rt1+ urrddllu
rt1- drrulld
rt2+ urrddluu
rt2- ddruuuld
rt3+ urdddlluru
rt3- dldrruuuld
rt4+ urrdddlluu
rt4- ddrruuulld
以下はpを11,15と交換する手順を, rtpで示したもので, 例えば左上の
0との交換には, 上の図のrt4を4回転するから, rt4-が4回, その後, 右回転, 更にrt4+を4回を示している. rt10,11,14,15がないのは, そこが主戰場だからだ.
rt0 rt4- rt4- rt4- rt4- rot rt4+ rt4+ rt4+ rt4+
rt1 rt2- rt2- rt2- rot rt2+ rt2+ rt2+
rt2 rt2- rt2- rot rt2+ rt2+
rt3 rt3- rt3- rt3- rot rt3+ rt3+ rt3+
rt4 rt1- rt1- rt1- rot rt1+ rt1+ rt1+
rt5 rt0- rt0- rot rt0+ rt0+
rt6 rt0- rot rt0+
rt7 rt3- rt3- rot rt3+ rt3+
rt8 rt1+ rt1+ rt1+ rot rt1- rt1- rt1-
rt9 rt0+ rt0+ rot rt0- rt0-
rt12 rt1+ rt1+ rot rt1- rt10
rt13 rt0+ rot rt0-
この準備が出来ると, ランダムな配置から元へ戻すことが可能になる. 前回のブログのランダムの例から戻す手順をやってみたのが以下だ.
まず左上0の直ぐ下がランダムな状態で, その下へ進んで(sp10)は空白を
10へもっていく命令を実行したところである. 命令の後の1は時間順を表す.
この状態の右下
15をみると9のこまがあり, これを
8に戻したいから(rt8)を行う. (rt8)2の後のように, こま9は場所
8へ移動している. そして10が
15に来たから, 次は(rt9)を行う. そして10は
9へ入る. 次は13だから(rt12), 次は12だから行先は主戰場の中だ. 従って(rot)をして主戰場の中を回転する. すると8が
15に来る. そこで(rt7)を実行して8を
7に入れた. これで左端の列は終り, 2列目へ.
2列目は順調に進行する. 3列目の中程, (rt0)で1を左上へ移動すると, 主戰場は11, 12, 15になり, rotしても様子は変らない. この場合はこまの並びで自分の場所にいないものを探す. するとこま4が
1にいるから(rt1)を行い, 4を主戰場へ取込み, 1拍おいた後に
3へ送る準備をする. それが時間番号でいうと, 18,19,20になる.
このように進んで, 22までくると, 主戰場以外はすべて揃ったので, 後は適当な回数の(rot)を実行し, 右下隅に12が来たら(l)(u)を行い, 最後を揃えて終わる. これをプログラムに書き直すのは簡単だ.
0 (rt2)7 (rot)14 (rot)21
7 4 11 2 7 4 3 2 11 4 3 2 1 15 3 4
15 1 14 __ 15 1 14 8 5 1 7 8 5 6 7 8
13 12 10 5 9 10 __ 11 9 10 __ 12 9 10 __ 11
8 6 3 9 13 6 12 5 13 14 15 6 13 14 12 2
(sp10)1 (rt4)8 (rt5)15 (rt1)22
7 4 11 2 7 4 3 2 11 4 3 2 1 2 3 4
15 1 14 5 5 1 14 8 5 6 7 8 5 6 7 8
13 12 __ 10 9 10 __ 15 9 10 __ 1 9 10 __ 15
8 6 3 9 13 6 12 11 13 14 15 12 13 14 12 11
(rt8)2 (rt0)9 (rot)16 (rot)23
7 4 11 2 11 4 3 2 11 4 3 2 1 2 3 4
15 1 14 5 5 1 14 8 5 6 7 8 5 6 7 8
9 12 __ 13 9 10 __ 7 9 10 __ 15 9 10 __ 12
8 6 3 10 13 6 12 15 13 14 12 1 13 14 11 15
(rt9)3 (rot)10 (rt0)17 (rot)24
7 4 11 2 11 4 3 2 1 4 3 2 1 2 3 4
15 1 14 5 5 1 14 8 5 6 7 8 5 6 7 8
9 10 __ 12 9 10 __ 12 9 10 __ 11 9 10 __ 11
8 6 3 13 13 6 15 7 13 14 12 15 13 14 15 12
(rt12)4 (rt6)11 (rt1)18 (l) (u)25
7 4 11 2 11 4 3 2 1 15 3 2 1 2 3 4
15 1 14 5 5 1 7 8 5 6 7 8 5 6 7 8
9 10 __ 8 9 10 __ 14 9 10 __ 4 9 10 11 12
13 6 3 12 13 6 15 12 13 14 12 11 13 14 15 __
(rot)5 (rot)12 (rot)19
7 4 11 2 11 4 3 2 1 15 3 2
15 1 14 5 5 1 7 8 5 6 7 8
9 10 __ 3 9 10 __ 15 9 10 __ 12
13 6 12 8 13 6 12 14 13 14 11 4
(rt7)6 (rt13)13 (rt3)20
7 4 11 2 11 4 3 2 1 15 3 4
15 1 14 8 5 1 7 8 5 6 7 8
9 10 __ 5 9 10 __ 6 9 10 __ 2
13 6 12 3 13 14 12 15 13 14 11 12
最後に一言. これはプログラムをさぼるという方針のため, 実際にこまを動かす回数は膨大になっている. 人手向きではないことに注意が必要だ.
