Let’s talk about chess. After all, chess is closely related to mathematics and econometricians love mathematics. We’ll start with how mathematics is related to chess or how chess is related to mathematics in the first place. Although mathematics and chess are entirely different disciplines, there have been many great chess players that studied mathematics. The patience and logic we need for both contributes to a beauty that is said to be found in both disciplines: “Chess is the gymnasium of the mind”- Blaise Pascal. “In many cases, mathematics as well as chess, is an escape from reality” – Stanislaw Ulam. Furthermore, the geometry of the chessboard and the characteristics of the game lends itself for solving some recreational mathematical problems. Therefore, I have decided to dedicate a series of articles on mathematical chess problems. This will be the first of this series and perhaps the most famous math problem in chess: the knight’s problem.
A painting of knights playing chess from the year 1283.
The knight’s problem is a related to our studies as it is effectively a pathfinding problem. One has a knight, whose set of possible next steps is such that the knight’s move consists of two steps in one direction and one in the other. See the picture below for the set of legal moves.The question for the knights problem is: can you find a closed path such that the knight crosses every square on the chessboard exactly once?
Legal moves for a knight.
This problem was described very early in an Arab text from 840. The Arabs had conquered Persia and with it they discovered a game called Shatranj, a game that was very similar to chess which was played in the third century in Persia already. Al-Adli ar-Rumi was one of the strongest chess players of his time and it is known that he already described the knight’s problem.
In order to explain how we can solve this problem, let’s first watch a solution made by someone else:
In this video, the square and diamonds method is explained. The intuition behind this solution is easy to follow. There are four networks: right-square, left-square, left-diamond and right-diamond. We can make a tour of legal moves around each network and we can enter the diamond systems from the square systems and vice versa. Hence this will always provide an easy to find solution on an 8×8 board.
But we want to go a bit further than just an easy trick to find a solution. In mathematical terms, we are looking for a Hamiltonian path. That is a path that crosses every vertex exactly once. A multiple of ideas have been proposed through the course of time, but there is one that is far more elegant than the others (including Euler’s solution). This method was developed by H.C. von Warnsdorf in 1823. The described method seeks an open Hamiltonian path. First, it is noticed that depending on the square you’re in, there is a number of legal moves that can be made. Warnsdorf rule says that one should always go to the square from which the least legal moves can be made. This means that automatically the first moves will be on the outside and gradually one would move to the inside. In the scenario of the picture below, the optimal move would be to go to either one of the squares with score 3. A typical solution of a knight’s tour provided by the Warnsdorf heuristic is shown in picture (zie links hieronder check copyright). Warnsdorf rule provides a very easy rule of thumb. At the time, he claimed that it could find a solution for a board of any size. However, extensive research has found that it fails on 76×76 boards. Heuristiscs such as Warnsdorf’s are preferred over algorithms, because algorithms use backtracking and therefore slowly become ineffective. The time for heuristics increases approximately linearly with the size of the board.
Warnsdorf’s scores.
Closed knight’s tours
A closed knight’s tour is not possible on an nxm chessboard for n and m odd. To prove this, first we note that if both are odd, there will be one more black or white square. Also, with every move, the knight will go to a different colour. Therefore, closed tours will visit as many white squares as black squares. However, this is not possible because we need to visit one more black square.
Warnsdorf’s rule does not provide a solution to find a closed knight’s tour, nor can it be easily adapted such that it comes up with a closed tour. It turns out that finding closed tours is far less elegant than Warnsdorf’s rule. A common method is to make a number of closed tours on the board and find ways to join them such as to make larger tours. The first to do this was a Frenchman by the name of A.T van der Monde. Hence tours created by this method are called Vandermondian. An example of this was the square and diamond method that we saw in the clip earlier.
Magic knight’s tour
Mathematicians, being fond of problems that don’t have much application, rose the question whether a magic knight’s tour exists. This is a knight’s tour where each square is ranked with the number of the move that the knight makes to reach this square. Then the magic tour is a tour such that the ranks of all columns, rows and diagonals add up to the same number, so as to form a magic square. In the picture below, one can see a 16×16 knight’s tour. Finding these magic knight’s tours involves mathematics that is beyond the scope of this article and makes use of computers.
For a long time, it was unknown whether magic knight’s tours exist on the 8×8 chess board. It turns out that this is not the case. This question remained unanswered for a long time until an extensive research using a computer was done to enumerate all possibilities in 2003. It was then found that there is no such tour. However, there are 140 semi-magic knight’s tours on the 8×8 board. Those are tours in which the rows and columns have equal sum, but the diagonals do not.
In conclusion, we can say that, although there is not particular use for knight’s tour in modern mathematics, it is a nice problem for recreational mathematicians. A problem that can be made harder by imposing extra conditions such as the magic tour. A different approach of adding dimension to this problem may be to change the knight (a (1,2)-leaper) for a hypothetical piece that is a (1,3)-leaper or a (1,4)-leaper, called the camel graph and the giraf graph problems respectively.
Dit artikel is geschreven door Tim van Schaick
