In college, some of my favorite courses involved optimizations of graph algorithms. Since I've recently spent my spare time implementing chess with a friend, it was only natural for me to reduce the chess board to a graph. An interesting tangential question then arose – what graph algorithms could I apply here?

A common coding challenge in computer science courses is to write a script that finds knight's tours. A knight's tour is a sequence of chess moves that allows a knight to visit every square on the board exactly once. It's actually just a specific instance of the Hamiltonian path problem, which is itself reducible to the travelling salesperson problem. Luckily, unlike the NP-complete travelling salesperson problem, the knight's tour problem is solvable in linear time. Still, that doesn't mean my personal machine is powerful enough to compute all possible knight's tours. On a standard 8x8 chess board, there are 26,534,728,821,064 possible directed closed knight's tours!

Directed, you say? And what's closed? Okay yes, I introduced some jargon up there, so let's cover that vocabulary really quick:

**Directed:**A directed knight's tour is one where the knight's direction is part of the solution. That means that two tours that use the same path but travel in opposite directions are considered distinct solutions.**Undirected:**An undirected knight's tour does not include direction as part of the solution. Because every directed knight's tour can always be traced in reverse, there are always half as many undirected tours as directed ones.**Closed:**A closed knight's tour is one where the knight ends its tour on the same position that it started.**Open:**An open knight's tour is one where the knight does not necessarily end its tour in the same position that it started.**Hamiltonian path problem:**A problem to determine whether there exists a path through a graph that visits every vertex exactly once.**Travelling salesperson problem:**An optimization problem to find the shortest and most efficient path that a salesperson can take in order to visit every single destination in a list exactly once.

This vocabulary is important, because each variant adds its own difficulty to the process of counting the number of knight's tours that are possible on a board. For example, even though we can count the number of closed knight's tours on the 8x8 chess board, the number of open knight's tours is still unknown (though estimated at 33 trillion)!

I was surprised to learn how big chess boards must be for knight's tours to even be possible. They're never possible for `1 x n`

or `2 x n`

boards, which makes sense, but they also don't exist on `3 x 3`

or `4 x 4`

boards either. According to an older source I found, open tours are only possible for boards with dimensions `3 x 4`

, `3 x n`

where `n >= 7`

, and `m x n`

where `m >= 4, n >=5`

. Closed tours are even more constrained. They're only possible on boards with dimensions of `3 x n`

for `n >= 10 (even)`

or `m x n`

for `m >= 5; n >= 6 (even)`

.

The requirement for closed knight's tours that at least one of the board's sides be an even length was initially odd to me. But it didn't take long for me to figure out why this is necessary. In a board with odd dimensions, the total number of squares on the board is odd, which means that there are an unequal number of black and white tiles and that the knight must move an odd number of times to visit every position on the board. However, since a knight alternates between black and white tiles when it moves, an odd number of moves would have it end its tour on the wrong color. There'd be no way for it to end in the same position it started on.

So how exactly are knight's tours found? Well, there's the basic brute-force algorithm that's too slow to work on anything but the smallest boards, the divide-and-conquer algorithm that doesn't necessarily find all possible tours for a board, and Warnsdorff's rule. Warnsdorff's rule is unique because it's a heuristic, so it's not possible to prove that it even produces a valid knight's tour when used!

All this knight's tour research left me feeling intrigued. I decided to implement a naive brute-force algorithm of my own. Here's the recursive solution I managed in a handful of minutes:

The exercise was fun and reminded me of a silly tradition I do during December every year – Advent of Code. (That's a story for another day, but if you don't know what it is, definitely check it out!) Next up, I plan to code a few other knight's tour implementations to see how big of a chess board I can find tours on!