Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

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

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

はじめに

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

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

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

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

エイト・クイーン

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 言語版ほぼそのままです。

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

ではまた、次回。

Kray-G
C++ & boost lover だったが、禅の心持ちというかシンプル・イズ・ザ・ベストの精神で C に回帰中。メタルからロックンロールに戻ってきて Rolling Stones に今更夢中。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away