アナクロなコンピューターエンジニアのつぶやき

8-Queensを解くプログラムです。これは、8x8のマスにお互いが鑑賞しないようにQueenのコマの配置を求めるプログラムです。オリジナルで作成しようと頑張ったのですが、行き詰まってしまいました。いつものように、先人の方々のお知恵を拝借しました。調べてみると、ヴィルトの「アルゴリズム＋データ構造＝プログラム」にPascalで書かれたスマートな解がありました。暑中参照している「マイクロコンピュータのプログラミング」にもMicroPlanでの解が掲載されています。このMicroPlanの解を参照して、プログラムを作成しました。

さて、下敷きにしたプログラムは、Queenの配置を求めるルーチンが再帰的に書かれています。これをMC6809のアセンブラで書き下すのがキーポイントでしょう。想像しているより簡単に実現できました。MC6809にはスタックが、システムスタック Sとユーザースタック Uの2つがあります。このユーザースタックに、再帰的関数内部のローカル変数を退避させることでうまく行きました。 プログラム、アセンブルリスト、実行結果などは、こちらです。 8Queen.zip

いつものように、Lコマンドでロード・モジュールをダウンロードし、Cコマンドで、C000から実行させます。

Queenの配置が、次々と出てきます。

         === 8 Queens ===
           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
           1 4 6 0 2 7 5 3
           1 4 6 3 0 7 5 2
                  :
                  :
                  :

例えば、"0 4 7 5 2 6 1 3"は、

          カラム 0のQueenは、ロウ 0に
          カラム 1のQueenは、ロウ 4に
          カラム 2のQueenは、ロウ 7に
          カラム 3のQueenは、ロウ 5に
          カラム 4のQueenは、ロウ 2に
          カラム 5のQueenは、ロウ 6に
          カラム 6のQueenは、ロウ 1に
          カラム 7のQueenは、ロウ 3に

にあることを示しています。こんな配置です。

            0 1 2 3 4 5 6 7
          0 Q . . . . . . .
          1 . . . . . . Q .
          2 . . . . Q . . .
          3 . . . . . . . Q
          4 . Q . . . . . .
          5 . . . Q . . . .
          6 . . . . . Q . .
          7 . . Q . . . . .