** "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.

- Reference
- First motivation ... Script language KINX (introduction)
- All links to individual articles are collected here.
- Repository ... https://github.com/Kray-G/kinx
- We are waiting for Pull Request etc.

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.

- 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

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.

```
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
...(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
```

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