Christopher StracheyのGPM

クィーンパズル生成マクロ

前回は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;

が得られた. 結構大騒ぎだが, もう何クィーンでも対応できるようになった. もっとも引数の個数の制限は別である.