Puzzle
Knight's tour problem
BACKGROUND
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?
KNIGHT'S TOUR PUZZLE
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.
SOLVING THE ORIGINAL KNIGHT'S TOUR
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.
Here is a solution from the website Geeksforgeeks in C++ that does it blazingly fast in linear time:
