Knight’s Tour

The purchase of a simple 8×8 LED Matrix module recently triggered a new intellectual challenge. Looking for possible applications of 64 LEDs in a square, the link to a chess board was easily made. Eventually, I started wondering if it would be possible to turn on all LEDs one by one, starting from a random LED, and then jumping to the next unlit LED, according to the rules for a knight’s move on a chess board. The real challenge, of course, was that the process was not allowed to jump to previously lit LEDs.

 

[The video shows the ‘luxury version’ on a TFT touchscreen. The sketch for a 8×8 LED matrix is at the end of this post]

 

Some googling would have told me that this is a classic problem in mathematics, called the Knight’s Tour problem. I would have learned that great mathematicians like Leonhard Euler had devoted their superior brains to it and that, especially when restricted to a chess board’s 8×8 dimension, many relatively simple solutions exist. I’m glad I did my googling much later, otherwise I would have missed a nice challenge.

 

Preventing LEDs from becoming isolated

Intuition will tell you that the first thing to do is trying to prevent LEDs from becoming unreachable during the process. For our knight (LED), not all squares on the board are equally accessible. The corner squares can only be reached from two other squares, whereas squares in the center can be reached from eight. The following picture (found on Internet) shows for every square how many other squares could jump to it in one move.

 

As soon as a position becomes visited, the numbers in the ‘within reach’ squares of this position have to be adjusted: they all loose a neighbor that could reach them in one jump during the rest of the process. The green squares show the adjusted numbers.

The knight’s current position will be given a zero to indicate that it cannot be visited again.

Now that we keep track of the ‘reachability-index’ of each square during the process, we can have our algorithm select the best candidate for the next jump, based on the lowest value of this index. If this results in a draw between candidates, we pick a candidate closest to the border of the board, as derived from (static) values in a matrix similar to the picture above (a purely intuitive tactics that turned out to exist as Warnsdorf’s rule, although I’m confident that Mr. Warnsdorf contributed much more to the solution than just this).

Algorithms like clarity, so I still had to decide what to do when candidates for the next jump shared both the same index and proximity to the border. The algorithm checks the candidates in a certain order, keeping track of the lowest index value and (in case of a draw) the proximity to the border. When the next candidate in the check order scores equally good as the current best, the algorithm can either stick to the old candidate or switch to the new one. In my algorithm, I keep the old candidate, but that’s not important. What does matter, though, is the check order as coded in the program.

The nature of a knight’s move means that, from a given position, there could be 8 possible positions for the next jump. Some of these positions may turn out to be impossible because they would bring the knight outside the board. Other positions may be illegal because they have already been visited. For our algorithm to figure that out, it will have to test all 8 moves, so let’s assign them letters: a for ‘2 up, 1 right ‘, b for ‘1 up, 2 right’, and so on, moving clockwise in the picture until we’ve reached move h.

As we saw earlier, a different check order will produce a different candidate (and thereby a different tour) in cases when there is a draw. Now that we have labeled the moves with letters ah, we can choose between 40320 different check orders (8x7x6x5x4x3x2, the number of permutations of our 8 letters).

 

Brute-force (sorry, couldn’t resist)

By now, I had become so anxious to find out a few things about my algorithm that I decided to go for the brute-force approach. This is what I wanted to know:

  • Were there check orders amongst the 40320 that would successfully generate a complete tour for all 64 starting positions?
  • Were there starting positions that would not lead to a complete tour, regardless of the chosen check order?
  • What about ‘closed’ tours, where the knight could jump to the starting position directly from the last position in the tour?

Having my poor Arduino Uno go through 40320 check orders from all 64 starting positions on the board would be cruel.  So, after reducing the number of needed loops by using the board’s symmetry, I wrote a php script to do the job on a fast PC. For each combination of starting position and check order, it stored the results in a MySQL database. Once the program finished, some simple SQL queries were enough to reveal the power and limitations of my algorithm.

 

Some results

  • Out of 40320 check order permutations, 24454 will produce a successful Knight Tour from all 64 starting positions!
  • No check order will ever fail on more than 3 out of 64 starting positions.
  • 240 check orders will fail on 3 out of 64 starting positions
  • 2456 check orders will fail on 2 out of 64 starting positions
  • 13170 check orders will fail on 1 out of 64 starting positions
  • There are 4 ‘super’ check orders that will produce a closed tour from 21 starting positions. Apart from this being a maximum, they will also produce a complete tour for the remaining 43 positions.
  • None of the check orders will produce a closed tour from any of the four corner squares.

Note that if your target is to write a sketch that produces closed tours for every starting position, you’ll just need to hard code one single closed tour in an array, start reading at the position that corresponds with the current start position and then cycle through the array, moving to the first element after you reached te last (not exactly an algorithm).

 

Put it to work

In the end, I wrote the following sketch that, in each loop, will randomly pick a starting position. Then it will also randomly pick one of the four ‘super’ check orders that I found by brute-force. This adds some more variation to the process because the same starting position can now have four different tours. Besides, almost 33% of the tours will be closed.

The gradual slow down while filling the board is a built in ‘feature’. It tries to suggest that it becomes more difficult for the algorithm to find a free position towards the end…

You can attach a piezo buzzer to GPIO 6 and GND for a sound effect.

The sketch (for the LED matrix):