クィーンパズル生成マクロ
前回は4クィーン問題をGPMで解いてみたが, そもそもは8クィーンを解きたい.
すこし時間が経ったのでおさらいするとして, q2とq3を並べて見る.
$def,q3,<$z,0, $def,q2,<$y,0,
$def,z,<$~1, $def,y,<$~1,
$def,~1,<$ $def,~1,<$
$|,$?,>>~1<<,>~1<,0;, $|,$?,>>~1<<,>~1<,0;,
$|,$?,>>~1<<,>~1<,3;, $|,$?,>>~1<<,>~1<,2;,
$|,$?,>>~2<<,>~1<,0;, $|,$?,>>~2<<,>~1<,0;,
$|,$?,>>~2<<,>~1<,2;, $?,>>~2<<,>~1<,1;;;;,
$|,$?,>>~3<<,>~1<,0;,
$?,>>~3<<,>~1<,1;;;;;;,
$def,f,<$q4,>>>~1<<<,>>>~2<<<, $def,f,<$q3,>>>~1<<<,>>>~2<<<,
>>>~3<<<,>>~1<<,>>>~4<<<; >>~1<<,>>>~3<<<;
$z,$1+,>>~1<<;;>;, $y,$1+,>>~1<<;;>;,
$def,t,<$z,$1+,>>~1<<;;>;;>;, $def,t,<$y,$1+,>>~1<<;;>;;>;,
$def,>~4<,;;>;;>; $def,>~3<,;;>;;>;
q2は$q2,0,2,4; $q2,0,3,4; のように既に2個のクィーンが無事に置けたとしてそれらのクィーンの位置と4クィーンであるという4をもって呼ばれる. 3個めを0,1,2,3と置いてみて, うまく置ければそれを次の引数に追加してq3を呼ぶ仕掛である.
3個めを置くマクロはyで, $y,0;と呼ぶ. 続けてyの定義がある. まず引数が~3, つまりnクィーンのnなら終りのチェックをするが, 例によってelseから書いてある. else節はor(|)で$?をいくつも呼んで, 引数で持ち込まれたクィーンと当るかを調べる.
$?,>>~1<<,>~1<,0;は最初のクィーンと今度のクィーンが横並びか見る. (>>~1<<が最初のクィーン, >~1<がyが作った新しいクィーン.) 次の?はクィーンが横方向に2ずれているから, 高さ方向の差が2であるか見る.
次は2番目のクィーンと今度のクィーンが横並びか高さの差が1かを見る.
orが偽をいうことは, 無事に置けたのだから, 受け取った引数と, 今回テスト中のクィーンとnの値4をもってq3を呼び, 今回のクィーンの位置をひとつ増してyを呼ぶ.
新しい位置が当っていれば, $def,t,にあるように, 位置を増してyを呼ぶ.
新しいクィーンの位置がnまで来ると最後の方の$def,>~3<,で, そのまま脱出してしまう.
これが別れば一般のクィーンの個数のqマクロが書ける.
しかしマクロを生成するマクロには宿命がある. 評価を阻止する<と>について, 出力マクロに入れるものか, 現状の評価中に評価を阻止するためのものか, 区別が必要なことである.
今回は出力に書き出すものは, [と]を使うことにした. 出来上がったマクロをエディタで処理し, [,]を<,>に置き換える.
$def,g0,<$~1,
$def,~1,<
< $|,$?,]]~>$-,>~2<,>~1<;<[[,]~1[,0;,>
< $|,$?,]]~>$-,>~2<,>~1<;<[[,]~1[,>>~1<<;,>
$g0,$1-,>~1<;,>~2<;>;,
$def,1,<
< $|,$?,]]~>$-,>~2<,>~1<;<[[,]~1[,0;,>
< $?,]]~>$-,>~2<,>~1<;<[[,]~1[,>>~1;;>;
$def,g1,<$~1,
$def,~1,<;;$g1,$1-,>~1<;;>;,
$def,0,;;>;
$def,g2,<$~1,
$def,~1,<<]]]~>$-,>~2<,>~1<;<[[[,>
$g2,$1-,>~1<;,>~2<;>;,
$def,0,;;>;
$def,gen,<
<$def,q>~1<,[$>~2<,0,>
< $def,>~2<,[$~1,>
< $def,~1,[$>$g0,~1,$1+,~1;;$g1,~1;<,>
< $def,f,[$q>$1+,~1;<,>
$g2,~1,$1+,~1;;<]]~1[[,]]]~>$1+,~1;<[[[;>
< $>~2<,$1+,]]~1[[;;];,>
< $def,t,[
$>~2<,$1+,]]~1[[;;];;];,>
< $def,]~>$1+,~1;<[,;;];;];>
>;
この$genが生成マクロである. $gen,3,z;のように呼ぶ. するとq3が出力される. zは上のq2の例にあったyの働きのものである.
真中より少し下のgenの定義を見ると,
<$def,q>~1<,[$>~2<,0,>
< $def,>~2<,[$~1,>
< $def,~1,[$>
とあって, これで
$def,q3,[$z,0,
$def,z,[$~1,
$def,~1,[$
までが出来る.
次のg0はorの連続を出力, g1はその後のセミコロンの列を出力する. さらに先のg2はq4の呼出し列を生成する. そういう次第で出力されたq3は
$def,q3,[$z,0,
$def,z,[$~1,
$def,~1,[$
$|,$?,]]~1[[,]~1[,0;,
$|,$?,]]~1[[,]~1[,3;,
$|,$?,]]~2[[,]~1[,0;,
$|,$?,]]~2[[,]~1[,2;,
$|,$?,]]~3[[,]~1[,0;,
$?,]]~3[[,]~1[,1;;;;;;,
$def,f,[$q4,]]]~1[[[,]]]~2[[[,]]]~3[[[,]]~1[[,]]]~4[[[;
$z,$1+,]]~1[[;;];,
$def,t,[$z,$1+,]]~1[[;;];;];,
$def,]~4[,;;];;];
ほかのq1,q2,...,q7も以下の呼出しで生成される.
$gen,7,d;
$gen,6,c;
$gen,5,b;
$gen,4,a;
$gen,3,z;
$gen,2,y;
$gen,1,x;
その出力のかっこを変換し, 両端の
$def,q8,<~1,~2,~3,~4,~5,~6,~7,~8;>;
$def,q0,<$w,0,
$def,w,<$~1,
$def,~1,<$q1,>~1<,>>~1<<;
$w,$1+,>~1<;;>;,
$def,>~1<,;;>;;>;
を追加し, $q0,8; で呼ぶと, 約28分の実行の後
0,4,7,5,2,6,1,3;0,5,7,2,6,3,1,4;
0,6,3,5,7,1,4,2;0,6,4,7,1,3,5,2;
1,3,5,7,2,0,6,4;...
...
7,2,0,5,1,4,6,3;7,3,0,2,5,1,6,4;
が得られた. 結構大騒ぎだが, もう何クィーンでも対応できるようになった. もっとも引数の個数の制限は別である.