[Java] Kinx Algorithm-Knight Travel Problem

2 minute read

Kinx Algorithm-Knight Travel Problem

Introduction

The script language Kinxdeliveredby”“ItlookslikeJavaScript,thebrain(contents)isRuby,(stabilityisAC/DC)”). “Program = algorithm + data structure”. Introducing an example implementation of the algorithm.

The original story is “The latest algorithm encyclopedia in C language (even after 30 years)”. This time it is a knight patrol problem.

The latest algorithm encyclopedia also has quite a few of these. Like a puzzle.

I wrote this algorithm in the early days of Kinx and used it for testing. After all about the control of double array and the 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

The Knight’s Tour is a type of chess-based mathematical puzzle. Also known as “Knight’s Journey” or “Keima Pickup” [1], it has long been known as a chess-based puzzle. 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 can be written almost in the same form as the C language version.

Looking at it this way, at the beginning (about 6 months ago), I was testing with this kind of source code. It would be nice to see something like this working.

See you next time.