# Finding A Knight's Tour

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.

## Backtracking

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.

## Warnsdorff’s rule

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.

## Output

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.