Chess and Math: A Closer Look at the Knight's Tour

People often talk about the connections between math and chess, assuming that being good at one means that you are (or would be with a bit of effort) also good at the other. Certainly, many traits of a successful mathematician or chess player overlap: strong analytical ability, spatial awareness, a high level of creativity, intuition, pattern recognition and on and on. I would suggest it is no coincidence that some of the best chess players ever were also accomplished mathematicians: Euwe, Lasker and Nunn to name a few. Many other great chess players were also in fields related to mathematics; Botvinnik, for example, was an electrical engineer and computer scientist. In this article, I would like to introduce some of the connections between mathematics and chess. In many cases, some familiar chess problems are really just math problems in disguise. In some more interesting cases (to me at least), you can apply certain math techniques to analyze some chess positions and decide the answer to the ultimate question: who, if anyone, is winning in a given position (although this might have to wait until a future article)? Hopefully, some of you will also be introduced to some new concepts, will find them interesting, and will go on to explore some new and beautiful ideas! To begin, let’s look at the famous knight’s tour in chess.

For those of you who are not familiar with the knight’s tour, the goal is to place a knight on an empty chess board and then move the knight to each of the remaining 63 squares while only visiting each square once. If on visiting the last square the knight is able to hop to the square on which it first started it is known as a closed tour (and so the knight could resume the exact same sequence of moves to complete another tour) while if the knight is unable to hop to the original square, it is known as an open tour. The famous mathematician Euler spent some time creating his own knight tours. The following are two diagrams of knight’s tours. The first is a diagram of a closed tour, and the second is an open tour (numbers are included in the second diagram to further illustrate the knight’s movements):

Many chess problems can be discussed quite nicely using techniques and terminology from ‘graph theory’ in mathematics. To put it simply, a graph is a collection of points (vertices) connected by lines (edges), relating some relationship between the points. For example, each point (vertex) could represent a different person and an edge connecting two vertices could indicate that those people know each other. There are certainly many more nuances of what constitutes a graph, but, for our discussion, this will suffice. To make the connection between graph theory and the knight’s tour, let each square on the chess board be represented by a different vertex; connect the vertices with an edge if the knight can move from square to another square. So, for example, the vertex that represents the a1 square would have edges connecting it to the vertices represented by b3 and c2 only, since those are the only two squares the knight can jump to from a1. From a more central square, say e4, the vertex representing e4 would have edges connecting it to 8 other vertices, namely those represented by: f2, g3, g5, f6, d6, c5, c3 and d2. Furthermore, this type of graph would give rise to what 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. Notice this makes sense as a knight always alternates the colors of the squares it visits: if the knight stands on a black square, it can only travel to a white square and vice versa. So we could separate our 64 vertices into two sets: one set with 32 vertices that represents the white squares and another set with 32 vertices representing the black squares. Below is a PARTIALLY filled in bipartite graph representing the squares to which a knight can travel. The complete graph would be too large and messy! Note only the vertex representing the c2 square has all of its edges. Edges are missing from all of the other labeled vertices.

Now, when looking at a closed Knight’s tour in this graph theory setting we are really asking another famous question that crops up for a given graph: does our graph have a Hamiltonian cycle? A Hamiltonian cycle is ‘closed loop’ where a path is found that visits each vertex exactly once and upon visiting the last vertex, it is possible to return to the starting vertex.

So really the question of a knight’s tour is really just a thinly veiled question about Hamiltonian cycles in graph theory! In general, to answer the question of whether a given graph has a Hamiltonian cycle is known as an NP problem which in essence means there is no good way to decide except by using brute force search methods (mathematicians are typically not excited about such methods when it comes to solving problems). Hamiltonian cycles have many real life applications, and finding them turns out to be a useful endeavor. A simple example of why finding a Hamiltonian cycle is useful is as follows: suppose you take a road trip and you want to go to a number of different spots during your vacation but would like to visit each spot only once in order to save time and money on gas. Ideally, you would find a Hamiltonian cycle that would take you to each location (represented by vertices) via roads that directly connect the locations (represented by the edges). This way you visit each spot once and return home at the end of your trip! You would probably even add more restrictions such as trying to minimize the total distance traveled, but the basic idea is still there. You can imagine how someone planning the routes for delivery drivers would be interested in finding such a minimal cost solution (consider the USPS or FedEx, for example). Instead of vacation spots, the locations are mailboxes or homes scheduled for delivery for the day. For those in logistics operating on a large scale, tons of money can be saved or wasted depending on the route selected! As a parting gift, here is a partially completed open knight’s tour. See if you can fill in the remaining squares to complete the tour! You will complete moves 41 through 64. Depending on the final solution, you might notice another ‘magic’ property. See if you can discover it! Good luck!

PatrickJMT received his undergraduate and Master's degree in Mathematics from the University of Louisville. While studying math, he somehow managed to find time to play lots of blitz chess. While he has never been a tournament player and takes long breaks from chess, he keeps a respectable blitz and bullet rating online and has beaten hundreds of titled players (not that blitz and bullet count for much though!). His happiest chess moment was drawing Korchnoi during a simul game in London and being told how well he played by the legendary player himself.