[Java] Kinx Algorithm-Eight Queen

2 minute read

Kinx Algorithm-Eight Queen

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’s Eight Queens (generally N Queens).

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

Eight Queen also made samples at the beginning of Kinx and used them to see if there were 92 possible solutions.

Eight Queen

  • https://ja.wikipedia.org/wiki/%E3%82%A8%E3%82%A4%E3%83%88%E3%83%BB%E3%82%AF%E3%82%A4% E3%83%BC%E3%83%B3

From Wikipedia

Eight Queen is the name of a puzzle that uses chess boards and pieces. Place 8 queens on the chess board. At this time, any piece must not be in a position where it can be taken by another piece.

N Queens has expanded these 8 to n.

Source code

var a = [], b = [], c = [], x = [];
var solution = 0;

function found(n) {
    System.print("\nSolution %d\n" %++solution);
    for (var i = 0; i <n; i++) {
        for (var j = 0; j <n; j++)
            if (x[i] == j) System.print(" Q");
            else System.print(" .");
        System.print("\n");
    }
}

function test(i, n) {
    for (var j = 0; j <n; j++)
        if (a[j] && b[i + j] && c[i-j + n-1]) {
            x[i] = j;
            if (i <n-1) {
                a[j] = b[i + j] = c[i-j + n-1] = 0;
                test(i + 1, n);
                a[j] = b[i + j] = c[i-j + n-1] = 1;
            } else found(n);
        }
}

function nqueen(n) {
    for (var i = 0; i <n; i++) a[i] = 1;
    for (var i = 0; i <2 * n-1; i++) b[i] = 1;
    for (var i = 0; i <2 * n-1; i++) c[i] = 1;
    test(0, n);
}

nqueen(8);

result

Solution 1
 Q .. .. .. ..
 .. .. Q ...
 .. .. .. .. Q
 .. .. .. Q ..
 .. Q .. .. ..
 ....... Q ..
 .Q .. .. ..
 .. .Q .. ..

Solution 2
 Q .. .. .. ..
 .. .. .. Q ..
 .. .. .. .. Q
 .. Q .. .. ..
 ....... Q ..
 .. .Q .. ..
 .Q .. .. ..
 .. .. Q ...

Solution 3
 Q .. .. .. ..
 ....... Q ..
 .. .Q .. ..
 .. .. .. Q ..
 .. .. .. .. Q
 .Q .. .. ..
 .. .. Q ...
 .. Q .. .. ..

...(abridgement)

Solution 92
 .. .. .. .. Q
 .. .Q .. ..
 Q .. .. .. ..
 .. Q .. .. ..
 .. .. .. Q ..
 .Q .. .. ..
 ....... Q ..
 .. .. Q ...

in conclusion

This is almost the same as the C language version.

I remember back then that when this kind of thing worked properly, I felt that it was working well and I was moving forward. After all, it was the first step to be able to do various things when access to array elements and increment / decrement got to work properly.

See you next time.