Kinx アルゴリズム - エイト・クイーン

はじめに

「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。「プログラム＝アルゴリズム＋データ構造」。アルゴリズムの実装例をご紹介。

元ネタは「C言語による（30年経っても）最新アルゴリズム事典」。今回はエイト・クイーン（一般的には N Queens）です。

• 参考
  • 最初の動機 ... スクリプト言語 KINX（ご紹介）
    • 個別記事へのリンクは全てここに集約してあります。
  • リポジトリ ... https://github.com/Kray-G/kinx
    • Pull Request 等お待ちしております。

最新アルゴリズム事典にはこういうのも結構載ってる。パズル的な。

エイト・クイーンも Kinx の最初のころにサンプルを作り、ちゃんと 92 通りの解が出せるか確認に使った。

エイト・クイーン

• https://ja.wikipedia.org/wiki/%E3%82%A8%E3%82%A4%E3%83%88%E3%83%BB%E3%82%AF%E3%82%A4%E3%83%BC%E3%83%B3

Wikipedia より

エイト・クイーンとは、チェスの盤とコマを使用したパズルの名称である。
チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。

尚、この 8 個を n 個に拡張 したのが N Queens です。

ソースコード

var a = [], b = [], c = [], x = [];
var solution = 0;

function found(n) {
    System.print("\nSolution %d\n" % ++solution);
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++)
            if (x[i] == j) System.print(" Q");
            else           System.print(" .");
        System.print("\n");
    }
}

function test(i, n) {
    for (var j = 0; j < n; j++)
        if (a[j] && b[i + j] && c[i - j + n - 1]) {
            x[i] = j;
            if (i < n - 1) {
                a[j] = b[i + j] = c[i - j + n - 1] = 0;
                test(i + 1, n);
                a[j] = b[i + j] = c[i - j + n - 1] = 1;
            } else found(n);
        }
}

function nqueen(n) {
    for (var i = 0; i < n; i++)         a[i] = 1;
    for (var i = 0; i < 2 * n - 1; i++) b[i] = 1;
    for (var i = 0; i < 2 * n - 1; i++) c[i] = 1;
    test(0, n);
}

nqueen(8);

結果

Solution 1
 Q . . . . . . .
 . . . . Q . . .
 . . . . . . . Q
 . . . . . Q . .
 . . Q . . . . .
 . . . . . . Q .
 . Q . . . . . .
 . . . Q . . . .

Solution 2
 Q . . . . . . .
 . . . . . Q . .
 . . . . . . . Q
 . . Q . . . . .
 . . . . . . Q .
 . . . Q . . . .
 . Q . . . . . .
 . . . . Q . . .

Solution 3
 Q . . . . . . .
 . . . . . . Q .
 . . . Q . . . .
 . . . . . Q . .
 . . . . . . . Q
 . Q . . . . . .
 . . . . Q . . .
 . . Q . . . . .

...(省略)

Solution 92
 . . . . . . . Q
 . . . Q . . . .
 Q . . . . . . .
 . . Q . . . . .
 . . . . . Q . .
 . Q . . . . . .
 . . . . . . Q .
 . . . . Q . . .

おわりに

これもほぼほぼ C 言語版ほぼそのままです。

こういうのがちゃんと動くと「うまくいってる感」があって前に進んでる感じがしてました、と当時を思い出す。やっぱり配列要素のアクセスとインクリメント・デクリメントあたりがきちんと動くようになった時が色々できるようになる最初の一歩でしたね。

ではまた、次回。