# 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

• 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.

## 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