The Knight’s Tour: Finding Some of its Solutions
Fuelled by lockdown boredom and a certain Netflix show, I (like many others) have found myself enjoying the occasional game of chess. I may be terrible and I may blunder my pieces more often than not, but it has given me a fantastic way to put off that growing stack of Uni work. Procrastination aside, it has also inspired me to take another look at a well-known and well-loved classic puzzle: the Knight’s Tour.
So what is the Knight’s Tour?
The problem of the Knight’s Tour is quite simple; given an mxn chessboard and a starting position, can you move the knight around the board so that every square is visited and no square is visited twice? It’s a fairly managable problem on a small board, but as the size gets bigger it becomes a little more daunting to figure out what that path may be, especially if you don’t know if it’s even possible!
We can break down the problem of the Knight’s Tour into something more familiar for mathematicians. Imagine the chessboard as a graph with the squares as nodes and edges between nodes that are reachable within one knight’s move. We can imagine our knight moving between nodes that have an edge connecting them, and our problem becomes that of finding a path in our graph that visits every node exactly once. In other words, we find a Hamiltonian Cycle from our starting position.
The problem of the Hamiltonian Cycle is itself a difficult one as it belongs to the class of NP-Complete problems. As previously stated, solving this problem with a brute force method soon becomes impossible due to the number of possibilities to consider growing exponentially with the size of the board. Instead, we can use heuristic methods to make finding a solution more feasible. One such heuristic is Warnsdorff’s Rule, where you travel to the squares that leave you with fewer subsequent possible moves. In terms of our graph, we travel to the nodes with the lowest degree, excluding those already visited. This method allows us to find a path in time linear to the size of the board — something much less formidable than our previous exponential time.
Path vs Cycle
There are two variations on the Knight’s Tour; one in which we want the knight to finish on its starting square and the other where it can finish anywhere on the board. In terms of our graph, the difference is that between finding a cycle and a path. A cycle is a walk around the graph where vertices are visited exactly once, except for our start node which we end on. A path is where we visit every node once but our walk may finish on any node. We will be mainly looking at cycles rather than paths in the Knight’s Tour Puzzle.
Existence of a Cycle
It is also possible for us to know whether a cycle exists before we even begin moving the knight. The graph formed by the Knight’s Tour is a special kind of graph called a bipartite graph or a bigraph — a kind of graph that separates its nodes into two sets and members of the same set are never adjacent. In the case of the Knight’s Tour, those two sets are the nodes that correspond to black squares and those that correspond to white squares as the knight never moves onto a square of the same colour. One property of bigraphs is that they have no odd cycles i.e. the number of nodes in a cycle must always be even. Therefore, the number of squares on our chessboard must be even as well. Any board where both m and n are odd can contain no solution to the Knight’s Tour.
There are two other constraints on the size of the chessboard to determine whether such a cycle exists: m or n cannot equal one, two, or four and if one side is of length three the other side cannot be of length four, six, or eight.
It’s easy to see how a board with sides of length one or two cannot possibly allow the knight to traverse every square. With side length one, the knight cannot make any move at all and with side length two, the knight can travel in one direction only and it’s unable to turn back on itself without stepping on a previously visited square. When one of the sides is of length four, it’s a little more difficult to see why the cycle can’t exist. The proof of this is something quite ingenious; conjured by Louis Posa whilst he was still a teenager (Honsberger, 1973).
Let’s assume that we have a Knight’s Tour on our chessboard with four rows and an arbitrary number of columns. There are two rows of ‘outer’ squares and two rows of ‘inner’ squares, the number of which are equal. When a knight is on one of the ‘outer’ rows it can only ever move to an ‘inner’ row, so in our cycle we must alternate between ‘outer’ squares and ‘inner’ squares.
We also alternate between black and white squares due to how the knight moves. We must therefore have a one to one correspondence between squares of one colour and squares on either the ‘outer’ or ‘inner’ rows — but this cannot be true as both black and white squares appear on both kinds of row. Therefore we can conclude that no such cycle can exist on a board where one of the sides is four squares long.
Now we turn our attention to boards of size 3x4, 3x6, and 3x8. The 3x4 case has already been proven to have no possible cycle by our previous proof. To show our claim is true for the other two cases, we use a property of Hamiltonian Graphs; if k nodes are removed from the graph, then there should be at most k connected components remaining.
For the 3x6 board, we construct the graph for the knights moves and we remove the nodes that correspond to the squares on the first and third rows in the third column. What we have left is three connected components and two nodes removed, so there cannot be a Hamiltonian Cycle in the graph and therefore no knight’s tour on the board.
The 3x8 case is less straightforward. We can’t simply remove some nodes on the graph as with the previous case but what we can do is construct a new graph that, if there is a Hamiltonian Cycle in the new graph then there will be one in our original one. In the graph constructed be the knight’s moves on the 3x8 board, there are eight nodes of degree two and the edges from these 8 nodes form 6 paths within the graph. We know that these paths must be traversed by the knight within the tour, so we construct a new graph with these paths replaced by nodes and draw edges when there is a knights move from the endpoints of these paths to other endpoints.
We then remove the two nodes of degree three from this new graph, leaving three connected components. Therefore, there can be no Hamiltonian Cycle in this graph and therefore no cycle in the original one.
On all other board sizes, a tour will exist. The full proof of this (Schwenk, 1991) contains a lot of graphs and a lengthy proof by induction, but satisfying at its conclusion nonetheless.
Puzzle Variations
It’s important to note that these constraints do not all apply to the version of the Knight’s Tour where any square may be its final square. For example, there are many tours to be found on a 5x5 board and on some 4xn boards: two conditions which mean the impossibility of a closed tour.
We can also ask the question, what if the boards aren’t rectangular? What if the boards have holes in the middle? What if the board we’re working on is the surface of a cube? Or a torus? There’s a multitude of variations we can conjure with this puzzle — the applications of which I have no idea, but who actually does maths for its applications?
References
Schwenk, A. (1991). Which Rectangular Chessboards Have a Knight’s Tour? Mathematics Magazine, 64. (pp. 325–332)
Honsberger, R. (1973). Mathematical Gems. (pp. 145)
