A Knight’s Tour is a sequence of moves done by a knight on a chessboard such that it visits each and every square exactly once. Subsequently, the objective of the Knight’s Tour problem is to determine whether there exists a Knight’s Tour from a given starting position. In graph theory terms, it is a form of Hamiltonian path where you visit each vertex of the graph exactly once along the path. Tours can also be cyclic or closed if the final square is a knight’s move away from the first and acyclic or open otherwise.
On a typical 8 x 8 chessboard, according to this paper, the number of undirected closed knight’s tours was computed to be 13,267,364,410,532, (directed would be twice that). The number of directed open tours on a 8 x 8 was not actually known and estimated to be about 2x10^16 until in 2013, Alex Chernov computed that the number is 19,591,828,170,979,904.
On an irregular board, the smallest rectangular board dimensions in which there is an open knight’s tour is 3 x 4.
I was trying to solve problem out manually on a chessboard. There are some strategies if you start from a corner, but I keep running into dead-ends, if I start from a non-corner position. So, I resort to programming and here are some of my attempts to search for a knight’s tour.
With a depth-first traversal with backtracking, a knight tour can be searched. The gist is that at each branch of traversal, go with the first branch and if the search reaches a dead-end, go back a step and try other alternatives. Eventually, either a tour will be found or there is no possible knight tour from the given starting position.
Most of the magic happens in the knight-tour function in which, the search starts from the initial position on the board (count=1). From the current position, possible legal knight moves are generated and tried out by incrementing the count and marking it on the board. If a move turns out to be leading a dead end, reset the board position and the count will be decremented and it would reach the end of the function (return False) and exit from a recursion instance. Eventually, a knight’s tour will be found (count == total) provided that there is one.
This approach works reasonably well for small boards but as the size of the board grows (N >= 7 onwards ), the search will take exponentially longer as there would be more “center” pieces which have 8 possible moves.
In order to improve from that, Warnsdorff’s rule can be applied. Warnsdorff’s rule is a heuristic which states that in each step of the tour, the square with the least possible moves the knight can make from that square is favored. If a tie occurs, it may be broken arbitrarily.
The idea is to have a list of possible moves (next_possible_moves()) and calculate and store the number of possible moves from each of those moves (warnsdorff()) and choose the move with fewest onward moves. Reaching a dead-end means, there are no possible moves returning from the warnsdorff function.
This approach works well for really big boards as well. A Knight’s Tour can be found in a few seconds during my testing with big boards. (N=200,300,400)
As you can see, I rely on Python’s sorted() function and didn’t do anything special for ties. However, as far as I have researched, there are some approaches to break the ties in more specific manners instead of choosing arbitrarily.