その書き直した方のN-BASICによるn-queensのプログラムを示します。手で打ち込んだのでは無く、PC80 mimi (PasocomMini PC-8001。来春発売予定の88SR miniではない方)のmicro SDカードからファイルを移し、PC上の自作C言語で書き出せた最初のプログラムです。かなり強引な手段ですし、説明するとなると、さまざまな当時の事情やらを延々と綴らないといけなくなりそうなので、全部省略させていただきます。ご了承のほどを。
100 REM N-QUEENS: 241118
110 DIMB%(27):DIMC%(27)
120 J%=0:Y%=0:X%=0
200 TIME$="00:00:00"
210 M#=0:N%=8-1:REM n-1 -> N%
300 Y%=0:X%=0
400 IFC%(X%)=0THEN450
410 X%=X%+1
420 IFX%<=N%THEN400
430 IFY%=0THEN900
440 Y%=Y%-1:X%=B%(Y%):C%(X%)=0:GOTO410
450 IFY%=0THEN500
460 FORJ%=Y%-1TO0STEP-1
470 IFABS(X%-B%(J%))=Y%-J%THEN410
480 NEXTJ%
500 B%(Y%)=X%
510 IFY%>=N%THEN550
520 FORJ%=0TOY%:PRINTB%(J%);:NEXTJ%:PRINT
530 C%(X%)=1:Y%=Y%+1:X%=0:GOTO400
550 M#=M#+1:PRINTM#;":";
560 FORJ%=0TOY%:PRINTB%(J%);:NEXTJ%:PRINT
570 GOTO440
900 PRINT"end. n=";M#;" time=";TIME$
見た瞬間に本ブログを閉じかけた方もいらっしゃるでしょうが、最初の説明は見て欲しいです。
つまりこれはBASICのような再帰が無いプログラム言語で探索プログラムを書くとこうなる、の典型と思います。今は再帰無し言語は珍しいかもしれませんが、普通のアセンブラには再帰はありませんから、こちらが電子計算機の原風景です。あとで追加説明します。
メインループの入り口は行400なのですが、適当に場合分けを省略しているので、ループへのエントリは行410と行440にもあります。メインループの最後は行570です。
それよりも、現代的なプログラミング言語に慣れた方には当時風のベタ打ちBASICは奇怪に見えるかもしれません。行110にいきなり出てくるDIMB%()関数って何だ、の印象を持たれた方は今では不思議ではないです。これは分かち書きすると、
110 DIM B%(27): DIM C%(27)
ということであり、つまり配列変数名B%とC%の宣言文であり、その要素数はどちらも28個を要求する(配列の添字は0から始まるので)、です。%は整数(16bit。-32768~+32767)の型を示します。少し下にあるM#は64bitの倍精度浮動小数点数です。解の数を計数する変数で、nが大きくなるとたちまち32767は超えてしまうので、こうしています。
TIME$は本来は現在時刻を保持するシステム変数(文字列型)で、しかしここではストップウォッチとして使っています。行900で計算時間を表示するためです。
配列B%が盤面で、8×8のチェス盤面(N%=7)だと8要素(B%(0)~B%(7))で十分です。というのは各行には1個のqueenしか置けないからです。盤面の左下を(0, 0)とし、各行のどの列にqueenがいるかを保持します。配列は最初には0クリアされています。
行300でY%=0、X%=0は最初の検討位置の指示です。
探索は座標(X%, Y%)にqueenが置けるかどうかから始まります。
行400でいきなりチェック対象になっている配列C%は列の占拠状態を保持しています。(先行する行の)同じ列にqueenがいたら(C%(X%)>0)置けない、のチェックです。置けそう(C%(X%)=0)なら追加のチェック、行450に飛びます。
(X%, Y%)に置けないことが分かっている行410では同じ行の次の列に検討を移します。行420では検討位置が盤面内にある場合はループの先頭、行400に戻ります。
行430は検討位置が盤面の右外に出てしまった場合で、最下行(Y%=0)の時は可能性が尽きたことを示しますから最終報告、行900に飛びます。
行440は検討位置を一行戻す処理です。しかし後退するということは、そこはすでに検討済みなので、次の列への検討位置の移動の行410に制御が飛びます。
行450は斜め線上にqueenがいるかどうかの検討の前に、最下行だったら探す場所が無いので置ける場合の処理の行500に飛びます。
行460~行480のFOR/NEXTループが斜め方向にqueenがいるかどうかのチェックです。queenが見つかったら、ただちに置けない場合の処理の行410に飛びます。ループ外へのGOTO脱出です。チェックが終了したら、次は行500の置ける場合の処理に移ります。
行500は盤面にqueenを置いています。行510は途中の行か最上行に置けたのかのチェックで、最上行の場合はパズルの解ですから報告の行550に飛びます。
途中の行の場合は行520で中間報告し、行530で次の行に移る準備をします。新たな場所のチェック開始なので行400に戻ります。
最終行の場合は解の一つですから行550で結果を表示し、その行の探索は終わってしまったので一行戻す処理となりますから、行440に飛びます。
BASICは再帰が出来ないので、途中結果を保持する必要があり、それがB%の盤面で、スタック構造になっています。スタックポインタはY%です。
ループはいわゆる状態遷移マシンになっていて、C言語でこのアルゴリズム(再帰無し)を採用するのなら、無限ループの最初でswitch/caseで分岐し、各状態を処理する形になるでしょう。もちろんその目的のためのスタック領域とスタックポインタは確保する必要があります。
BASICにもON n GOTO ...がありますが、状態(1~n)を示す追加の変数が必要で、冗長な感じがしたから省略していて、その代わりをするのがプログラムカウンタ自体で、そのためにループ内に飛び先が複数ある感じがします。
ここが曖昧な方は、ぜひ状態遷移図でネット検索してみて下さい。ついでながら、CPUというのもチューリング機械では状態を保持する有限オートマトン機構に相当します。
どうです?、PC-8001 / N-BASICでも結構、計算機科学の話題に接近できます。