In this 2 parts post, I will show how I wrote in Go how to solve an open knight’s tour, what problem I confronted, and the evolution of my code.

As I wanted to continue playing with non-scripted languages, I choosed to continue learning some Go with a program to find solutions on the knight’s tour.

The idea behind this problem is to put a knight on your chessboard, make him move on every square without using the same square twice. This problem helped me pass boring hours in school (kids, don’t try this !), but it was somme 30 years ago and haven’t thought about it since.

A solution of the knight's tour

For more informations, the Wikipedia page about it.

The code

At first, I wanted a program that will throw me all the solutions. When I saw the time it took to find only one, I started making a version that will stop on the first solution founded (it appears, after reading the Wikipedia page, that there are 26,534,728,821,064 solutions for directed closed tours. That’s a lot !)

The idea is :

  • Create an 8x8 matrix of the path
  • Create a recursive function that tests the 8 possibility for each move
  • For every possibility test the next move
  • Exit when we have a solution

It’s abrute forceand, let’s face it, a very naive method. But you’ve got to start somewhere.

So first I create anarray valuesof 8 by 8, I fill it with 0 (I could have done it in one time, but I thought if I wanted to change the chessboard dimensions, it will be easyier).

Then I start the recursion and stop if(when) I have a solution (testOk is true).

I’ve defined the directions by a value of 1 to 8, each one is a move the knight can do on the board. The first call is with 0 in the direction to put the knight on 0,0 in the matrix (a1 in chess notation) and don’t move it.

When I find a solution, I print it with a double loop.

 1import "fmt"
 2
 3func main() {
 4
 5    // Initialisation of the matrix to 0
 6    values := [8][8]int{}
 7
 8    for i := 0; i < 8; i++ {
 9        for j := 0; j < 8; j++ {
10            values[i][j] = 0
11        }
12    }
13
14    // Start the recursion
15    valueReturn, testOk := nextMove(values, 0, 0, 0, 0)
16    if testOk {
17        for j := 7; j >= 0; j-- {
18            for k := 0; k < 8; k++ {
19                fmt.Printf("|%3d", valueReturn[j][k])
20            }
21            fmt.Print("|\n")
22        }
23    }
24}

The recursive functionnextMoveget in parameters the actual state of the matrix, the position in X and Y, the direction to test and the deep.
The return values are the matrix, modified if a move was possible, identical if not, and a boolean which is true if the matrix is full.

After testing if we have a solution (64 square are filled), we make the move. For exemple, direction 1 is one straignt move to the right and one diagonal move down.

We test if we are not out of the board, and if the square is free (not already passed by there).

All conditions cleared, we make the move (put the deep value at the matrix position).

To stop, we propagate the boolean.

 1func nextMove(values [8][8]int, posX int, posY int, direction int, deep int) ([8][8]int, bool) {
 2
 3    // Chek if it's full filled
 4    if deep == 64 {
 5        return values, true
 6    }
 7
 8    // Move according to direction
 9    switch direction {
10    case 1:
11        posX -= 1
12        posY -= 2
13    case 2:
14        posX += 1
15        posY -= 2
16    case 3:
17        posX += 2
18        posY -= 1
19    case 4:
20        posX += 2
21        posY += 1
22    case 5:
23        posX += 1
24        posY += 2
25    case 6:
26        posX -= 1
27        posY += 2
28    case 7:
29        posX -= 2
30        posY += 1
31    case 8:
32        posX -= 2
33        posY -= 1
34
35    }
36    // Test if we are out of the board
37    if posX < 0 || posY < 0 || posX > 7 || posY > 7 {
38        return values, false
39    }
40    // Test if already been there
41    if values[posX][posY] != 0 {
42        return values, false
43    }
44
45    // Increment deep
46    deep++
47
48    // Affect the deep to the current position in the matrix
49    values[posX][posY] = deep
50
51    // Test the 8 directions
52    for i := 1; i <= 8; i++ {
53        valueReturn, testOk := nextMove(values, posX, posY, i, deep)
54        if testOk {
55            return valueReturn, true
56        }
57    }
58    return values, false
59}

the results

Well, to be honest I had strictly no result when I launched the program. I own a i7-6700K @ 4.00GHz, the programm is on only one thread. As I was curious I added a counter to see the number of steps, I relaunch the program a few hours. It was still running when I decided to stop it. I was at 252,811,463 steps :-) Without a solution.

So I thought I made a mistake in my exit condition, and start trying small deep to see if it was ok. I started with a deep of 10 (modifying line 4 of my function). The result was instantaneous. So I tried with 20. The same. 32 ? Alike. 40, 50, 60… Instantaneous. 64 again. Never stop.

So I tried 61, it tooked 9 seconds. Ah ! Something new.

A B C D E F G H
8 16 13 10 5 26 29 0 0
7 9 4 17 14 11 6 27 30
6 18 15 12 7 28 25 44 51
5 3 8 19 24 43 50 31 34
4 20 23 38 49 32 35 52 45
3 39 2 21 36 55 42 33 58
2 22 37 48 41 60 57 46 53
1 1 40 61 56 47 54 59 0

We can see that this “solution” is a dead end for the resolution, but it proves that my function works nicely.

So I tested 62. Again, 10 seconds was enough.

A B C D E F G H
8 16 13 10 5 26 29 0 0
7 9 4 17 14 11 6 27 30
6 18 15 12 7 28 25 48 41
5 3 8 19 24 47 40 31 34
4 20 23 46 39 32 35 42 49
3 53 2 21 36 43 58 33 60
2 22 45 52 55 38 61 50 57
1 1 54 37 44 51 56 59 62

So 63 ! Now we are at nearly 40 seconds (and still a dead end)

A B C D E F G H
8 16 13 10 5 26 29 0 63
7 9 4 17 14 11 6 27 30
6 18 15 12 7 28 25 62 49
5 3 8 19 24 51 48 31 36
4 20 23 52 47 32 37 50 61
3 53 2 21 42 45 58 35 38
2 22 43 46 55 40 33 60 57
1 1 54 41 44 59 56 39 34

Well 64 stays reste inaccessible in terms of execution time, when 63 got out pretty quick.. Frustrating.

So, out of curiosity, I changed the order of my direction rules (from 8 to 1). Unexpectedly, a solution occurs. In less than a second.

Iterations : 2,635,139

A B C D E F G H
8 48 51 30 55 14 63 28 7
7 31 56 49 62 29 8 13 64
6 50 47 52 25 54 15 6 27
5 41 32 57 46 61 26 9 12
4 58 45 40 53 24 11 16 5
3 39 42 33 60 35 18 21 10
2 44 59 2 37 20 23 4 17
1 1 38 43 34 3 36 19 22

That is in chess norm :

a1 c2 e1 g2 h4 g6 h8 f7 g5 h3 f4 h5 g7 e8 f6 g4 h2 f3 g1 e2 g3 h1 f2 e4 d6 f5 h6 g8 e7 c8 a7 b5 c3 d1 e3 f1 d2 b1 a3 c4 a5 b3 c1 a2 b4 d5 b6 a8 c7 a6 b8 c6 d4 e6 d8 b7 c5 a4 b2 d3 e5 d7 f8 h7

The solution is valid. So the order of execution of the rules had an importance when I started from the a1 square. It’s highly possible that it would have a different behaviour if I started else where..

So now I’v got a solution. Weeeeee.

So in part 2 of this post (aka when I’ll have time to finish this), I’ll modify the code to show solutions as I find them (without exiting), launching a thread for the 8 first iterations. I will also use Warnsdorf’s rule to limit the tests. We’ll see if it speeds up and how much results we get on an acceptable time.

Image by Michał Parzuchowski