The Knight’s Tour Problem - Chess and Math Combined
When I was around 11 or 12, I went to a chess camp during the summer, and on the last day, our teacher made us do a knight's tour. Every time I tried, I failed it. I kept getting my knight trapped, and no one could do it. My best try was my first and I couldn't beat 50 squares.
Let's back up a little. What IS the knight's tour?
The knight's tour is a famous chess puzzle in which the objective is to move the knight around the board using only valid L-shaped movements, and so that each square is only visited once. There are in fact 30 trillion possible knight's tour, but it's not that easy!
The puzzle is believed to be discovered in the 9th century by a Kashmiri poet called Rudrata, a Sanskrit poet, in the 9th century. One of the first mathematicians to investigate the Knight's Tour problem was Leonhard Euler. The first procedure was called the Warnsdorf's Rule (which we'll get to later) discovered in 1823 by H. C. von Warnsdorf.
First, you have to familiarize yourself with the Four Quadrants of the chess board, and the Four Systems of moves.
The four quadrants are similar to four quadrants on a graph. This would be 1 quadrant, for example:
There are two diamond-shaped systems and two square-shaped systems. The shape is repeated in each quadrant, collectively forming all the moves for that particular system.
For each shape (diamond and square) there are two orientations, a left-hand shape and a right-hand shape.
The left-hand diamonds point up to the left, whereas the right-hand diamonds point up to the right.
The left-hand square has the topmost square on the left side of the quadrant, and the right-hand square has the topmost square on the right side of the quadrant.
Here is an example of a left-hand diamond system:
Right-hand diamond system:
Left-hand square system:
How to Complete a Knight's Tour
There is one (dumb) way to do the Knight's Tour and it is to just move your knight around, hoping you can complete it. There is a very low chance you will succeed, so let’s get into the right way of doing the Knight’s Tour.
First, you note which system the knight occupies on its first square. A Knight’s Tour is possible with every square! Then, you move the knight around the other three squares of the system within the same quadrant before doing so in the next quadrant. For example, if the start square is g1, you would move the knight to h3, then f4, and ending at e2 before going to the next quadrant. When doing this, all you have to worry about is that the final move in each quadrant allows you to move to the same system in another quadrant. To do this, you must decide whether to move clockwise or counter-clockwise around each quadrant so you don't get trapped on your final move.
When you move into the final quadrant of the system, you must choose your direction of movement carefully to ensure the final move in that quadrant allows you to move on to another system. You repeat this procedure through all the other systems until you have completed the knight's tour. The four systems are also supposed to be completed in a specific sequence. If you start with a diamond-shaped system, it will be followed by a square-shaped one and vice versa.
There is one more way to do this. Instead of having random end squares, you determine start AND end squares using this method. To start things off, you must make sure both start and end squares are opposite colored squares or else the Knight's Tour is impossible.
Once you've selected valid start and end squares, you must note which system they are in.
Opposite shapes
This section would apply if the start square is in a square-shaped system and the end square is in a diamond-shaped system, or vice versa.
First, you should complete the first system as with this method, but in the final quadrant, you must select your direction of movement so that you can enter the opposite-shaped system that is NOT the system occupied by the end square. For example, if the end square is in the left-hand diamond system, you must enter the right-hand diamond system as the second system. Then, complete the second and third systems as normal, making sure that you can enter the final system without hitting the end square.
Same shape, opposite orientation
In this scenario, the start square may be in the left diamond system and the end square in the right diamond system (or vice versa).
First, you should complete the first and second systems as usual, making sure you can enter the third system on a vacant square. Now, you have to move out of the third system and into the next system as soon as you can. Certainly you should move out before you complete the first quadrant of the system. To ensure you move out safely, you need to check that the remaining squares in that quadrant allow you to move in and out of the quadrant from adjacent quadrant(s) of the same system when you return to it later. If you don't do this, you will trap your knight. Depending on the third system, and the position in which you entered its first quadrant, you may be able to leave three, two, or only one of the squares in that quadrant.
Once you have moved out of the third system, you complete the new system in the normal way, making sure that you are able to enter back into the system from your final move.
Same shape, same orientation
Here, both start and end squares are in the right square systems.
First, you must move out of the first system as soon as you can. As in the previous case, you should move out before you complete the first quadrant of the system, checking as you do so that the remaining squares in that quadrant allow you to move both in and out of the quadrant from adjacent quadrant(s) of the same system when you return to it later. Again, if you don't do this, you will get trapped. Depending on the third system, and the position occupied by the start square, you may be able to leave three, two, or only one of the squares in the initial quadrant.
Having moved out from the first system, you complete the next three systems as normal before re-entering the first system.
Same System and Same Quadrant
For example, both start and end squares are in the left diamond system and also both in the lower right quadrant.
Solving this one is basically identical to the previous case, except you just need to ensure that you can enter the final quadrant containing the end square.
Warnsdorf's Rule
Warnsdorf's Rule is a heuristic for finding a Knight's Tour. The knight is moved so that it always proceeds to to the square from which the knight will have the fewest onward moves. When calculating the number of onward moves for each candidate square, we do not count moves that revisit any square the knight has already visited. It is also possible to have two or more choices for which the number of onward moves is equal.
Now, let’s get into how this has anything to do with math. To start off, a graph is a collection of points (vertices) connected by lines (edges). For example, each point (vertex) could represent a different person and an edge connecting two vertices can indicate that those people know each other.
To make the connection between graph theory and the knight’s tour, let each square on the board be represented by a different vertex; connect the vertices with an edge if the knight can move from square to square. For example, a vertex that represents the a1 square would have edges connected to the vertices representing b3 and c2 ONLY, since those are the only two square the knight can jump to from a1. From a more central square, such as e4, the vertex representing e4 would have edges connecting to 8 other vertices - f2, g3, g5, f6, d6, c5, c3, and d2.
When graphed, this is known as a bipartite graph. In a bipartite graph, one is able to form two sets so that no vertex in a given set is connected to another vertex in that same set. This makes sense as a knight always alternates the colors of squares it visits - if a knight stands on a White square, it can only travel to a Black square, or vice versa. So we separate our 64 vertices into two sets - one set with 32 that represents the White squares, and another 32 that represents the Black squares.
Below is a partially filled bipartite graph. The completed graph would be way too large and messy. Note that only the vertex representing the c2 square has all of its edges.
