Knight's tour problem


The knight in chess is a piece which can move in an L shape. It is said to be the secret ingredient which has made chess such a popular game for so long! Allegedly, the asymmetry introduced to the board by this weird movement shape and unique property of jumping over other pieces is what makes chess such a beautiful game (all other pieces can only move straight or diagonally).

It is also the only piece that makes sense in an otherwise bizarre game. I suppose a bishop could do damage on the battlefield by being extremely judgemental, but moving a castle multiple times is impractical to say the least - good luck getting planning permission with no objections at the local council meeting multiple times. Who came up with this insane army setup?

The Queen is dangerous and can move in all directions, but even she can’t jump over other pieces or take a non-linear path like a knight.

The original knight’s tour puzzle involves the Knight being placed in the top corner of the board, and goes around the board on a ‘tour’. This involves the knight jumping around on the board, and not revisiting the same square twice.

According to the Knight’s tour Wikipedia page, the puzzle has been around for a while (back to the 9th century!) with some OG mathematicians like Euler having a go at it. There are a few variations on it (different board sizes, etc) but the original 8 x 8 board has exactly 26,534,728,821,064 directed closed tours (closed meaning the Knight’s final position means for its next move it can return to the same square it started so can start the tour all over again if visiting each square once wasn’t thrilling enough for it). If you count the open tours (finishing in any old spot) the number of solutions goes up to 19,591,828,170,979,904. As you can see, it is a large number and also explains why my laptop nearly melted trying to solve it prior to using optimising heuristics.

There are a few ways to solve the original puzzle. The one I looked at used a heuristic named Warnsdorff’s rule, which optimises the brute force style recursion algorithm down to linear time by defaulting to taking the move where the knight has the fewest possible options for the subsequent move. Programatically you can represent the board as a graph and sort the nodes based on the number of possible next moves. This causes the path to default to going along the edges of the board, working inwards, which supposedly saves your computer the pain of going through the dead variations where it gets stuck and can’t find a way to visit an edge square (note in the gif above showing a complete tour the pattern ends up like a thorny crown). Another way to get it down to linear time is using a divide and conquer algorithm to cut up the board and patch up the sections after completing tours on the smaller pieces.

As explained on Wikipedia: A graphical representation of Warnsdorff's Rule. Each square contains an integer giving the number of moves that the knight could make from that square. In this case, the rule tells us to move to the square with the smallest integer in it, namely 2.

Here is a solution from the website Geeksforgeeks in C++ that does it blazingly fast in linear time:



Trickier version of Knight's tour problem


This journey down hole looking at chess puzzles one wild Friday evening was started by looking at a puzzle asking for a Knight’s tour solution for a board with a knight’s tour performed on a board numbered by the position and move, but with random values rubbed off. So in essence, you know some positions. The chess board is also 10 x 10 rather than 8 x 8, so many more walks you can take.

Here is an example of a board to solve:

I wrote the code the first time with the only constraints being to solve for the preset values using recursion and no Warnsdorff: you could have cooked an egg on my poor laptop.

The solution I ended up with in the end uses recursion and takes custom board sizes. Managed to solve a puzzle on a board of 20 x 20 in <1 second which I thought was cool!

Code and solution explanation coming soon