ところで, 最近知った15パズルの面白い解き方は, 福岡教育大学の藤本さんの提案する「回転型操作」によるものだ.
2件の論文がある.
情報処理学会研究報告にある「スライドパズルにおける回転型操作とアクセスビリティ」と, 近着の数式処理にある「Loop generatorによる15パズルの最適アルゴリズムとGod's numberについて」.
私は明解な手順には関心があるが, 最短手順には興味がないので, 後の論文は眺めた程度であった. 前の論文も解法は数式処理しシステムGAPを使って記述してあるので, GAPに馴染まぬ凡人にはとんと理解し得ぬ. 以下では私がSchemeで書いたプログラムの考え方を述べる.
この回転操作(英語ではloop generatorというらしい)は, 前回の15パズルのブログと似たやり方だが, 経路の単純なのが取り柄だ. 回転操作の前と後では, 空白は右下隅(15)に置くことにする. (イタリックの数字は場所の番地である.) 回転操作にはa, b, cがあり, それぞれ下の図の赤, 緑, 青の線のようにこまを回す. もちろん反対方向にも回す(回転数にマイナスを付けて示す). 例えばaを1回というと, 0にあったこまは4へ移動, 2回というと8へ移動する. bを1回では, 5のこまは9へ, 2回では13へ進む. 逆回転はは回数を負にする. aを-2回というと, 0が2へ行く.
回転経路が重なるのは, 図の7, 11, 13, 14の場所で, ここを経由して回転だけを使い, こまを任意の場所から他の任意の場所へ移すのである.
例えば5にあるこまを0へ移すには, aを4回して移動先0を13へ移動し, bを2回で移動元を13へ移し, aを-4回して最終目的地0へ動かす.
移動元と移動先が同じループに属しているといささか面倒だ. 例えば4から1へ移動するには,どちらもaのループにあるから, あらかじめ4を内側のループ, bかcのaと重ならない場所へ移動しておく. つまりaを3回で, 4のものを13へ; 次にbを-1回で9へ; 移動先の1は, a3回で8へ来ているから, 後2回で13へ進める. そこでbを1回行い, 4にあったものを13へ移す. それからaを-5回行うと, I1の位置へ行くわけである.
こういう手順が判明したから, aのループにある, 上端と左端にあるべき7個(4,3,2,1,,5,9,13)のこまを目的位置へ移す. この時はb, cのループの場所は自由に使ってよい. その後, bのループの5個(8,7,6,10,14)を揃える. この作業場所はcの10である. bが揃うと残りはcのループの10, 11, 14の番地に11, 12, 15のこまが残るだけになり, もとの配置のパリティが合っていれば, c1回かc-1回で完成する.
プログラムは後で示すことにし, 実際に走ったところを見よう. 下の図の左上(A)が最初の状態で, 空白はすでに右下15にある.
こま4はbのループにあるから, (a 7)(b 2)(a -7)を行うと, (a 7)で4の目的地3が13へ行き, (b 2)で4が13へ行き, (a -7)で4が3へ移る. (B)になる.
こま3は元々は目的地2にあったのだが, 4の移動のとばっちりで0にいる. そこで(a 4)(b -1)(a -4)(a 6)(b 1)(a -6)を実行する. (a 4)で3を13へ, (b -1)で9へ, (a -4)でaループを一旦元へ戻す. 改めて2の位置を(a 6)で13へ運び, (b 1)で3をそこに置き, (a -6)で(C)のように3が収まる. (a -4) (a 6)と続けるのは無駄だが, プログラムが明瞭になるからこのままにしてある.
こま2は3に連られて目的地に来ていたからなにもしない. (D).
次は1の番だ. またaのループにあるから, (a 3)(b -1)(a -3)(a 4)(b 1)(a -4)の前半で9の位置に置き, 後半で0へ移す. (E).
5はaループだが同時にbループでもある. この場合は, bの中へ入れればよいが, 私のプログラムでは(b 2)で5へ入れることにしている. それから(a 3)(b 2)(a -3)で(F).
9は(a 1)(b -1)(a -1)(a 2)(b 1)(a -2)とする. (G).
次の13もa, cループだから, 一旦10へ移す. (c 1). その後(a 2)(c 1)(a -2) で(H). ここまででaループの7個が終わる. 以後はaループの7個には影響しないように注意.
(H)を見ると8はb, cループにあるから, (c -1)で10へ避難. それから(b 5)(c 1)(b -5). (I)になる.
7はcループにあるから簡単だ. 6の場所を(b 4)で14へ. それから(c 1)(b -4)で(J). 幸運にもついでに6, 10も揃うから(K),(L)も同じ図だ.
14はb, cループ上にいるから(c -1)で10へ引上げ, (b 1)(c 1)(b -1).
最後は11, 12, 15のcループ. 11が10にあれば何もしない. 11にあれば(c 1), 14にあれば(c -1)だ. (N).
全体の手は
(a 7)(b 2)(a -7);4 (a 4)(b -1)(a -4)(a 6)(b 1)(a -6);3 2 (a 3)(b -1)(a -3)(a 4)(b 1)(a -4);1 (b 2)(a 3)(b 2)(a -3);5 (a 1)(b -1)(a -1)(a 2)(b 1)(a -2);9 (c 1)(a 2)(c 1)(a -2);13 (c -1)(b 5)(c 1)(b -5);8 (b 4)(c 1)(b -4);7 6 10 (c -1)(b 1)(c 1)(b -1);14 (c -1);11 12 15
であった.
一方, Schemeによるプログラムはこんな具合いだ.
(define bs (range 0 16))
は盤面のこまのリスト.
(define atab '( (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14) (4 0 1 2 8 5 6 3 12 9 10 7 13 14 11) (8 4 0 1 12 5 6 2 13 9 10 3 14 11 7) (12 8 4 0 13 5 6 1 14 9 10 2 11 7 3) (13 12 8 4 14 5 6 0 11 9 10 1 7 3 2) (14 13 12 8 11 5 6 4 7 9 10 0 3 2 1) (11 14 13 12 7 5 6 8 3 9 10 4 2 1 0) (7 11 14 13 3 5 6 12 2 9 10 8 1 0 4) (3 7 11 14 2 5 6 13 1 9 10 12 0 4 8) (2 3 7 11 1 5 6 14 0 9 10 13 4 8 12) (1 2 3 7 0 5 6 11 4 9 10 14 8 12 13))) (define btab '( (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14) (0 1 2 3 4 9 5 6 8 13 10 7 12 14 11) (0 1 2 3 4 13 9 5 8 14 10 6 12 11 7) (0 1 2 3 4 14 13 9 8 11 10 5 12 7 6) (0 1 2 3 4 11 14 13 8 7 10 9 12 6 5) (0 1 2 3 4 7 11 14 8 6 10 13 12 5 9) (0 1 2 3 4 6 7 11 8 5 10 14 12 9 13))) (define ctab'( (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14) (0 1 2 3 4 5 6 7 8 9 14 10 12 13 11) (0 1 2 3 4 5 6 7 8 9 11 14 12 13 10)))
はa, b, cそれぞれの回転で, 0,...のこまがどこへ行くかを示す. atab, つまりaの表は, 最初の行が(a 0)に対応. 同じ場所に留まる. 次の行(4 0 1...)はaの1回転で, 0は4へ, 1は0へ移ることを示す. 最後の行(atab[10])は-1回のものだ. b, cについても同様.
(define (rotate tab) (let ((b (make-list 16 0))) (do ((i 0 (+ i 1))) ((= i 15)) (list-set! b (list-ref tab i) (list-ref bs i))) (set! bs (list-copy b)) 'ok)) (define (a n) (rotate (list-ref atab (modulo n 11)))) (define (b n) (rotate (list-ref btab (modulo n 7)))) (define (c n) (rotate (list-ref ctab (modulo n 3))))
(a n)がaのループをn回実行する. aの表から使うべき行をとりだし, rotateへ. rotateは16個のリストbを用意し, bs内のこまの番号をbへ移して最後にbをbsへ戻す.
(define ps0 '(4 3 2 1 5 9 13)) (define qs0 '(3 2 1 0 4 8 12)) (define ps1 '(8 7 6 10 14)) (define qs1 '(7 6 5 9 13))
ps0はaループのこまの番号, qs0はその目的地. ps1とqs1はbループのものである. 次がいよいよ解くプログラムである.
(define (solve2) (do ((i 0 (+ i 1))) ((= i 7)) (let* ((p (list-ref ps0 i)) (q (list-ref qs0 i)) (r (elemindex p bs)) ) (if (not (= r q)) (begin (set! r (case r ((7) (b 2) 5) ((11) (c 1) 10) ((14) (c -1) 10) ((13) (b -2) 5) ((0 1 2 3 4 8 12) (let ((l (length (member r qs0)))) (a l) (b -1) (a (- l)) 9)) (else r))) (if (= r 10) (let ((l (- 8 i))) (a l) (c 1) (a (- l))) (let ((l (- 7 i))) (a l) (b (length (member r '(6 5 9)))) (a (- l))))))))
ここまでがaループのプログラムで, 7個についてdoループを回す. letへ来て, pはこまの番号, qは目的地, rは現在地である. r=qなら何もしない. そうでないならcase式へ来て, r=7なら(b 2)を実行, こまを5へ, という風に読む. rが0,1,2,3,4,8,12なら, rがqs0にある位置から後方の長さlを知り, (a l) (b -1) (a (- l))を行ない, こまを9へ移す. 上のいずれでもなければelseへ来て, 回転はせず, rはそのまま. 上のbeginの次の(set! r ...)でrを更新する.
結局移動するこまはcの10かbの5,6,9のどこかにいるから, それらの情報を使い, 目的地へ移動する.
bループのプログラムが以下だが, 説明は同様だ.
(do ((i 0 (+ i 1))) ((= i 5)) (let* ((p (list-ref ps1 i)) (q (list-ref qs1 i)) (r (elemindex p bs))) (if (not (= r q)) (begin (case r ((11) (c 1)) ((14) (c -1)) ((7 6 5 9 13) (let ((l (length (member r qs1)))) (b l) (c -1) (b (- l))))) (let ((l (- 5 i))) (b l) (c 1) (b (- l))))))) (case (elemindex 11 bs) ((11) (c 1)) ((14) (c -1))) (drawbs))
という次第で無事に並べ替られる. なかなか楽しい.
