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):

 

 

 

 

 

Rotary Encoders

With my upcoming robot arm project in mind, I bought a couple of these cheap Keyes KY-040 rotary encoders. Guess they may come handy for manually controlling servos with greater precision than potentiometers, especially in combination with the 12 bit resolution PWM controller that will drive the arm’s servos.

First I wanted to check that all encoders were OK (they could be Chinese clones of Chinese clones…), so I grabbed some sketches from the Internet. All sketches – with or without the use of interrupts – worked fine on all encoders, but I noticed that they would only count every second click of the encoder. As my encoders have 30 clicks (‘detents’) per revolution, using the technique from these sketches would reduce the resolution to only 15 steps per revolution of the shaft.

So, in order to find out what exactly happens with each click, I wrote this simple sketch:

Rotary encoders have two switches, A and B, that will be switched on and off when you turn the shaft, resulting in binary pulses on their CLK and DT connectors. Since the pulse sequence of  the switches are 90 degrees out of phase, you can not only count the pulses, but also detect whether the shaft is being rotated clockwise (CW) or counter clockwise (CWW).

 

The output of the above sketch showed that my type of encoder will click on every blue and every red marked event within the pulse sequence, whereas all sketches I’ve seen so far will count either the blue or the red events (i.e. full pulse cycles).

Once I understood why the sketches I found on the Internet ignored every second click of my decoders, it was time to write a sketch that would count every click, and tell me the direction as well. As the picture clearly illustrates, the values of A and B will be the same after every click. The direction is defined by which of them arrived at that value first. If it was A, then rotation is CW; if it was B, then rotation is CCW.

In order to detect every click of my decoder, I decided to attach a ‘CHANGE’ interrupt to switch A (marked CLK on the encoder). Note that attaching ‘CHANGE’ interrupts to both CLK and DT is useless.

A nice bonus of the encoder is that it has a third switch (marked SW), that is pulled to GND when you push the shaft. I decided to use this feature for cycling through different incremental step sizes, offering different resolutions for sending a servo to a desired position (coarse-, medium- and fine tuning).

Time to put it to work. The following sketch controls a two-servo pan/tilt module by reading two rotary encoders. It uses a 16 channel 12 bit PWM Servo breakout to drive the servos, but the sketch can easily be simplified if you drive them directly from Arduino PWM pins. The ‘step size per encoder click’ will cycle through values 1, 5 and 10  with each push of the shaft. Parameter values for debouncing were optimized after some testing.

In the end, this setup turned out to work remarkably well for controlling my pan/tilt module with two KY-040 encoders connected to an Arduino UNO.

Note that the code within interrupt routines ProcA1 and ProcA2 has been reduced to calculating the new servo position and setting an alert flag, while the overhead of polling within loop() is limited to checking these two alert flags. In sketches where single loop sequences can take long, one could improve responsiveness to encoder events by having the interrupt routines do all the work (including the actual servo control), although in general, that’s not recommended.

This approach will be used for my robot arm project, although I will have to drop the interrupt technique for some of the decoders because the UNO only has two pins for external interrupts.