Kinx アルゴリズム - 騎士巡回問題

はじめに

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

元ネタは「C言語による（30年経っても）最新アルゴリズム事典」。今回は騎士巡回問題です。

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

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

このアルゴリズムも Kinx 初期の頃に書いてテストに使った。やはり二重配列の制御と再帰処理あたりで。お世話になりました。

騎士巡回問題

https://ja.wikipedia.org/wiki/%E3%83%8A%E3%82%A4%E3%83%88%E3%83%BB%E3%83%84%E3%82%A2%E3%83%BC

Wikipedia より

ナイト・ツアー（Knight's Tour）は、チェスを使った数学的パズルの一種。「騎士の巡歴（じゅんれき）」「桂馬拾い」[1]とも呼ばれ、チェスをモチーフにしたパズルの中でも昔からよく知られている。チェスボード上のナイトを移動させ、64マス全てを一回ずつ通過させる。

ソースコード

const N = 5;    // N x N

var board = [],
    dx = [ 2, 1,-1,-2,-2,-1, 1, 2 ],
    dy = [ 1, 2, 2, 1,-1,-2,-2,-1 ];
var count = 0;
var solution = 0;

function printboard() {
    System.print("\nSolution %d\n" % ++solution);
    for (var i = 2; i <= N + 1; i++) {
        for (var j = 2; j <= N + 1; j++) System.print("%4d" % board[i][j]);
        System.print("\n");
    }
}

function test(x, y) {
    if (board[x][y] != 0) return;
    board[x][y] = ++count;
    if (count == N * N) printboard();
    else for (var i = 0; i < 8; i++) test(x + dx[i], y + dy[i]);
    board[x][y] = 0;  count--;
}

function knight() {
    for (var i = 0; i <= N + 3; i++)
        for (var j = 0; j <= N + 3; j++) board[i][j] = 1;
    for (var i = 2; i <= N + 1; i++)
        for (var j = 2; j <= N + 1; j++) board[i][j] = 0;
    test(2, 2);
}

knight();

結果

Solution 1
   1   6  15  10  21
  14   9  20   5  16
  19   2   7  22  11
   8  13  24  17   4
  25  18   3  12  23

Solution 2
   1   6  11  18  21
  12  17  20   5  10
   7   2  15  22  19
  16  13  24   9   4
  25   8   3  14  23

Solution 3
   1   6  11  16  21
  12  15  20   5  10
   7   2  13  22  17
  14  19  24   9   4
  25   8   3  18  23

...(省略)

Solution 304
   1  10   5  16  25
   4  17   2  11   6
   9  20  13  24  15
  18   3  22   7  12
  21   8  19  14  23

おわりに

これはほとんど C 言語版と一緒の形で書けている。

こうしてみると、最初の頃（半年ほど前）は、この手のソースコードを使ってテストしてたんだなー。こういうのがちゃんと動くのを見られると嬉しいよね。

ではまた、次回。