[JAVA] Kinx Algorithm-Knight Patrol Problem

Kinx Algorithm-Knight Patrol Problem

Introduction

** "Looks like JavaScript, brain (contents) is Ruby, (stability is AC / DC)" ** Scripting language Kinx ). "Program = algorithm + data structure". Introducing an implementation example of the algorithm.

The original story is "The latest algorithm encyclopedia in C language (even after 30 years)". This time is the knight traveling problem.

There are quite a few such things in the latest algorithm encyclopedia. It's like a puzzle.

This algorithm was also written and tested in the early days of Kinx. Again around double array control and recursive processing. thank you for helping me.

Knight patrol problem

From Wikipedia

Knight's Tour is a type of mathematical puzzle using chess. Also known as "Knight's Journey" and "Keima Picking" [1], it has long been well known among chess-themed puzzles. Move the knight on the chess board and pass all 64 squares once.

Source code

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();

result

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

...(abridgement)

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

in conclusion

This is almost the same as the C language version.

In this way, at the beginning (about half a year ago), I was testing with this kind of source code. It would be nice to see this kind of thing working properly.

See you next time.

Recommended Posts

Kinx Algorithm-Knight Patrol Problem