MacTutor
Mathematics and Chess
John MacQuarrie
Puzzles
A Chess puzzle, while perhaps sounding childish, is in fact far more acutely mathematical than a Chess problem. As is not uncommon in mathematics, it strips the game of Chess of all but a few properties in order to allow more general or abstract questions to be asked and answered. Questions arising from the Chessboard and its inhabitants are numerous and varied, with common problems being combinatorial, optimisational, Boolean, procedural, or a combination of these. New Chess puzzles are easy to devise, and new questions frequently occur, many leading to interesting new mathematics. Others are extremely old, and have attracted the interest of renowned mathematicians.
By far the best example is the Knight's Tour. Here, only the movement of a Knight on a Chessboard is important. Simply, one asks whether the Knight, using its legal moves in Chess, can move around the board, landing on each square exactly once. In general, such a sequence of moves is called a Knight's path. If the Knight can do such a tour and finish on a square from which it can move directly to the square from which it started, then the path is called re-entrant. Further, if the Knight makes this final move, creating a loop, then the closed path is called a Knight's circuit or closed tour.
As the Knight's tour involves only the movement of the Knight, it may not be surprising to note that, like Chess Problems, the first known Knight's tour is considerably older than modern Chess. It is believed that al-Adli ar-Rumi, a philosopher who lived in Baghdad in the ninth Century, was the creator of the first known tour. While he is known to have written a book about Shatranj, the tour (shown below) is found in a manuscript from around 1350 by Abu Zakariya Yahya ben Ibrahim al-Hakim, whose title translates as The Delight Of The Intelligent, A Description Of Chess (Quoted in Murray, 1913). In the diagram, the tour begins from S and finishes at F. Note that the tour is re-entrant, and if a line were drawn connecting S and F by a Knight's move, the result would be a Knight's circuit.
The Earliest Known Knight's Tour
While the Knight's tour certainly does seem to have been considered as far back as the ninth century, the considerations do not seem to be largely apparent to more modern mathematicians. Euler rediscovered the question in the eighteenth Century, and he and De Moivre were amongst the first then to consider it. Both men constructed solutions for the 8 × 8 board that have a more methodical appearance than the solution found in the 1350 manuscript (Ball, 1939).
Note the connection with graph theory, also pioneered by Euler. Consider the squares of the board to be the vertices of a graph, and the pairs of vertices obtained by legal Knight's moves to be the edges. Then a question of Knight's tours is reduced to a question of Hamiltonian paths or circuits in graphs. For consistency, however, problems will not be considered explicitly in terms of Graph theory.
The question becomes far more interesting when attempt is made to generalise. This can be done in many ways, though the most obvious, and perhaps the most fruitful, is to consider more general boards. It is not difficult to see that tours cannot exist for N × N boards where N < 5, except for the trivial tour on a 1 × 1 board.
This is clear since on a 2 × 2 board the Knight cannot move at all, on a 3 × 3 board the Knight cannot reach the centre square, and on a 4 × 4 board the paths from opposite corners form a complete circuit which cannot be broken, as shown below.
4 × 4 Board showing a necessary circuit
Beyond these simple cases, the question of existence of Knight's tours must be answered, and where tours do exist, a method for determining satisfactory ones would be desirable. Satisfactory is a vague word, but intuition reigns. That is, a desirable tour will possess as much symmetry as can be, will be re-entrant where possible, and will be derived through logical and understandable methods.
Euler found a simple (if awkward) method for making re-entrant Knight's tours on a board where such tours exist. (Ball, 1939)
Firstly, the Knight is moved around the board in a near random, but careful fashion, where each square landed upon is indexed in the natural way, with the initial square being labelled '1'. If such a procedure is done 'carefully', then when the Knight has no further legal moves, either a tour has been accomplished, or there are several squares remaining un-indexed. The method then alters the order in which the squares are numbered to make the partial tour re-entrant. If such a tour exists, this is always possible. Now, by again re-labelling appropriately, it is possible to add in the missed squares one or more at a time. Having done this, the procedure used to make the partial tour re-entrant can be used again to make the complete tour re-entrant. While the method is not difficult to explain, it is as tedious as it is simple, and of little interest. Further, the actual process of re-labelling is extremely awkward, so the details have been omitted. It should be noted further that since the algorithm involves tinkering with a failed Knight's tour rather than producing a correct Knight's tour from the outset, it not considered a fully satisfactory solution. The tours produced are in general highly asymmetric, and their derivation is ugly.
In 1823, H.C. Warnsdorff found a different algorithm for finding Knight's tours (Ball, 1939). It is simple, effective, and does not involve the extensive re-labelling required when using Euler's method. The algorithm is this:
There are several difficulties. Firstly, paths produced are not re-entrant, though an application of the last part of Euler's method will make them so, assuming a re-entrant tour exists. Also, the method allows a degree of freedom at times, where there is more than one possible next square with lowest value. Warnsdorff claimed that in such an event it made no difference which possible square was selected, but counterexamples to this claim have since been produced. Indeed even with square boards, computers have shown that when the board gets too big (of side more than about 76 squares), the algorithm will encounter difficulties. (Roth, n.d., Quoted in Weisstein, n.d.).
Since then, a variety of further partial solutions have been found. One important solution is attributed to P.M. Roget who published a paper on the subject in 1840, though in fact J.E.T. de Lavernède first published the result, in 1839. The method is simple, will give re-entrant tours, and can produce highly symmetric results, but it only applies to boards of (4n)2 squares, where n is a natural number greater than one (Ball, 1939).
Thus, it still remains to ask for what boards a Knight's tour exists. Paul Cull and Jeffery De Curtins give the answer for the vast majority of rectangular boards. Their paper, Knight's Tour Revisited was published as recently as 1978. In the paper, they demonstrate that a Knight's tour exists for any board whose smallest side has length greater than or equal to five, and that a re-entrant tour exists if the number of squares is even.
The result is proved with remarkable simplicity, using template tours of various types. A sequence of lemmas are employed as follows:
1) Any 5 × M board with M ≥ 5 has a Knight's path beginning in the lower left and exiting at either the lower right, or at the upper right.
2) Every 6 × M board with M ≥ 5 has a Knight's circuit and a Knight's path starting in the lower left and exiting at the upper left.
3) Every 8 × M board with M ≥ 5 has a Knight's path starting in the lower left and ending in the upper left, and a Knight's circuit.
4) Every N × M board with N odd, min(N, M) ≥5, has a Knight's path that starts in the upper left and exits at the upper right.
Leading to:
5) An N × M board with NM even, min(N, M) ≥ 5, has a Knight's circuit.
6) Every N × M board with min(N, M) ≥ 5 has a Knight's path.
The proofs for the lemmas are simple, and follow a similar pattern. As demonstration, the proof for Lemma 1 will be given:
Firstly, it is shown that the result is true for 5 × R boards, where R is 5, 6, 7, 8 or 9, using boards constructed to demonstrate the property required. For example, the appropriate tours for a 5 × 5 board and for a 5 × 8 are shown below. Similar boards are presented for R being 6, 7 or 9.
The tours demonstrated above are presented such that the number i in a square represents the ith square visited on the tour shown. Note that these tours fulfil the condition of the lemma. That is, the Knight can exit at the lower right and upper right corners respectively.
Consider now a board for which M ≥ 10. Taking M to be 5T + R where 5 ≤ R ≤ 9, it is clear that the board can be partitioned up into T boards of dimension 5 × 5, and one (at the far right) of dimension 5 × R. Now, starting with the leftmost of these sub-boards, we can perform the Knight's tour that will exit at the lower right, and then jump to the lower left square of the next. We can continue doing this until we arrive at the 5 × R board, and then perform the tour that will exit from the lower or upper right as required. Thus, the lemma is proved.
The proof of the second lemma uses similar tricks to the proof of the first; the third is very similar to the second. The proof of the fourth is a little more involved, and relies on the previous results, but is still not difficult.
To prove theorem 5, assume first that N is even and N ≥ 10. Partition the board into two sub-boards, namely a 5 × M board and an (N - 5) × M board. Now choose as starting square the upper left hand corner of our (N - 5) × M board. Since N - 5 is odd, by lemma 4 there exists a Knight's path of this board that will finish on a square accessible to the lower right hand corner of the 5 × M board. By reflecting a path found in lemma 1 using a vertical mirror, we obtain a Knight's path of the 5 × M board starting in the lower right hand corner, and exiting at the lower left. Exiting thus will bring us back to our starting position, on the upper left hand square of the (N - 5) × M board, giving a Knight's circuit.
If M is even and M ≥ 10, then the same argument can be used, by interchanging rows and columns. The only remaining possibilities are when N is 6 or 8, but the second and third lemmas can be used to construct Knight's circuits for these cases.
Note that this result is almost as strong as is possible. With the board chequered, as a Chessboard is, the Knight under its legal move will always travel from a square of one colour to one of the other. If the board has an odd number of squares, then the final square reached by the Knight is of the same colour as the starting square. Thus, the Knight cannot return to the beginning in a single move and the tour cannot be re-entrant.
The only extra result required for completeness involves boards of the form 3 × M or 4 × M. These questions were answered in Allen Schwenk's paper Which Rectangular Chessboards Have a Knight's Tour? (1991). Such questions on rectangular boards have all now been answered, though it would certainly not be difficult to dream up more perverse boards if the desire came upon someone to do so.
Returning briefly to tours on the regular 8 × 8 Chessboard, one obvious question remains. We know that tours exist, but how many of them are there? Martin Löbbing and Ingo Wegener (1996), using powerful computers, claimed that the number of Knight's tours on a regular chessboard was 33,439,123,484,294. Unfortunately, this result was shown to be incorrect, since it was not, as it had to be, divisible by 4. Wegener (2000) continued to attempt the question, and later came to the conclusion that the number was in fact only 13,267,364,410,532. While it is difficult to be certain, this result seems more satisfactory. It is divisible by 4, and agrees with independent, unpublished results obtained by Brendan McKay (Weisstein, n.d).
By far the best example is the Knight's Tour. Here, only the movement of a Knight on a Chessboard is important. Simply, one asks whether the Knight, using its legal moves in Chess, can move around the board, landing on each square exactly once. In general, such a sequence of moves is called a Knight's path. If the Knight can do such a tour and finish on a square from which it can move directly to the square from which it started, then the path is called re-entrant. Further, if the Knight makes this final move, creating a loop, then the closed path is called a Knight's circuit or closed tour.
As the Knight's tour involves only the movement of the Knight, it may not be surprising to note that, like Chess Problems, the first known Knight's tour is considerably older than modern Chess. It is believed that al-Adli ar-Rumi, a philosopher who lived in Baghdad in the ninth Century, was the creator of the first known tour. While he is known to have written a book about Shatranj, the tour (shown below) is found in a manuscript from around 1350 by Abu Zakariya Yahya ben Ibrahim al-Hakim, whose title translates as The Delight Of The Intelligent, A Description Of Chess (Quoted in Murray, 1913). In the diagram, the tour begins from S and finishes at F. Note that the tour is re-entrant, and if a line were drawn connecting S and F by a Knight's move, the result would be a Knight's circuit.
The Earliest Known Knight's Tour
While the Knight's tour certainly does seem to have been considered as far back as the ninth century, the considerations do not seem to be largely apparent to more modern mathematicians. Euler rediscovered the question in the eighteenth Century, and he and De Moivre were amongst the first then to consider it. Both men constructed solutions for the 8 × 8 board that have a more methodical appearance than the solution found in the 1350 manuscript (Ball, 1939).
Note the connection with graph theory, also pioneered by Euler. Consider the squares of the board to be the vertices of a graph, and the pairs of vertices obtained by legal Knight's moves to be the edges. Then a question of Knight's tours is reduced to a question of Hamiltonian paths or circuits in graphs. For consistency, however, problems will not be considered explicitly in terms of Graph theory.
The question becomes far more interesting when attempt is made to generalise. This can be done in many ways, though the most obvious, and perhaps the most fruitful, is to consider more general boards. It is not difficult to see that tours cannot exist for N × N boards where N < 5, except for the trivial tour on a 1 × 1 board.
This is clear since on a 2 × 2 board the Knight cannot move at all, on a 3 × 3 board the Knight cannot reach the centre square, and on a 4 × 4 board the paths from opposite corners form a complete circuit which cannot be broken, as shown below.
4 × 4 Board showing a necessary circuit
Beyond these simple cases, the question of existence of Knight's tours must be answered, and where tours do exist, a method for determining satisfactory ones would be desirable. Satisfactory is a vague word, but intuition reigns. That is, a desirable tour will possess as much symmetry as can be, will be re-entrant where possible, and will be derived through logical and understandable methods.
Euler found a simple (if awkward) method for making re-entrant Knight's tours on a board where such tours exist. (Ball, 1939)
Firstly, the Knight is moved around the board in a near random, but careful fashion, where each square landed upon is indexed in the natural way, with the initial square being labelled '1'. If such a procedure is done 'carefully', then when the Knight has no further legal moves, either a tour has been accomplished, or there are several squares remaining un-indexed. The method then alters the order in which the squares are numbered to make the partial tour re-entrant. If such a tour exists, this is always possible. Now, by again re-labelling appropriately, it is possible to add in the missed squares one or more at a time. Having done this, the procedure used to make the partial tour re-entrant can be used again to make the complete tour re-entrant. While the method is not difficult to explain, it is as tedious as it is simple, and of little interest. Further, the actual process of re-labelling is extremely awkward, so the details have been omitted. It should be noted further that since the algorithm involves tinkering with a failed Knight's tour rather than producing a correct Knight's tour from the outset, it not considered a fully satisfactory solution. The tours produced are in general highly asymmetric, and their derivation is ugly.
In 1823, H.C. Warnsdorff found a different algorithm for finding Knight's tours (Ball, 1939). It is simple, effective, and does not involve the extensive re-labelling required when using Euler's method. The algorithm is this:
Having selected a starting square, count the number of unused squares reachable from each of the possible next squares. Then move to the square that has the smallest value computed.
There are several difficulties. Firstly, paths produced are not re-entrant, though an application of the last part of Euler's method will make them so, assuming a re-entrant tour exists. Also, the method allows a degree of freedom at times, where there is more than one possible next square with lowest value. Warnsdorff claimed that in such an event it made no difference which possible square was selected, but counterexamples to this claim have since been produced. Indeed even with square boards, computers have shown that when the board gets too big (of side more than about 76 squares), the algorithm will encounter difficulties. (Roth, n.d., Quoted in Weisstein, n.d.).
Since then, a variety of further partial solutions have been found. One important solution is attributed to P.M. Roget who published a paper on the subject in 1840, though in fact J.E.T. de Lavernède first published the result, in 1839. The method is simple, will give re-entrant tours, and can produce highly symmetric results, but it only applies to boards of (4n)2 squares, where n is a natural number greater than one (Ball, 1939).
Thus, it still remains to ask for what boards a Knight's tour exists. Paul Cull and Jeffery De Curtins give the answer for the vast majority of rectangular boards. Their paper, Knight's Tour Revisited was published as recently as 1978. In the paper, they demonstrate that a Knight's tour exists for any board whose smallest side has length greater than or equal to five, and that a re-entrant tour exists if the number of squares is even.
The result is proved with remarkable simplicity, using template tours of various types. A sequence of lemmas are employed as follows:
1) Any 5 × M board with M ≥ 5 has a Knight's path beginning in the lower left and exiting at either the lower right, or at the upper right.
2) Every 6 × M board with M ≥ 5 has a Knight's circuit and a Knight's path starting in the lower left and exiting at the upper left.
3) Every 8 × M board with M ≥ 5 has a Knight's path starting in the lower left and ending in the upper left, and a Knight's circuit.
4) Every N × M board with N odd, min(N, M) ≥5, has a Knight's path that starts in the upper left and exits at the upper right.
Leading to:
5) An N × M board with NM even, min(N, M) ≥ 5, has a Knight's circuit.
6) Every N × M board with min(N, M) ≥ 5 has a Knight's path.
The proofs for the lemmas are simple, and follow a similar pattern. As demonstration, the proof for Lemma 1 will be given:
Firstly, it is shown that the result is true for 5 × R boards, where R is 5, 6, 7, 8 or 9, using boards constructed to demonstrate the property required. For example, the appropriate tours for a 5 × 5 board and for a 5 × 8 are shown below. Similar boards are presented for R being 6, 7 or 9.
The tours demonstrated above are presented such that the number i in a square represents the ith square visited on the tour shown. Note that these tours fulfil the condition of the lemma. That is, the Knight can exit at the lower right and upper right corners respectively.
Consider now a board for which M ≥ 10. Taking M to be 5T + R where 5 ≤ R ≤ 9, it is clear that the board can be partitioned up into T boards of dimension 5 × 5, and one (at the far right) of dimension 5 × R. Now, starting with the leftmost of these sub-boards, we can perform the Knight's tour that will exit at the lower right, and then jump to the lower left square of the next. We can continue doing this until we arrive at the 5 × R board, and then perform the tour that will exit from the lower or upper right as required. Thus, the lemma is proved.
The proof of the second lemma uses similar tricks to the proof of the first; the third is very similar to the second. The proof of the fourth is a little more involved, and relies on the previous results, but is still not difficult.
To prove theorem 5, assume first that N is even and N ≥ 10. Partition the board into two sub-boards, namely a 5 × M board and an (N - 5) × M board. Now choose as starting square the upper left hand corner of our (N - 5) × M board. Since N - 5 is odd, by lemma 4 there exists a Knight's path of this board that will finish on a square accessible to the lower right hand corner of the 5 × M board. By reflecting a path found in lemma 1 using a vertical mirror, we obtain a Knight's path of the 5 × M board starting in the lower right hand corner, and exiting at the lower left. Exiting thus will bring us back to our starting position, on the upper left hand square of the (N - 5) × M board, giving a Knight's circuit.
If M is even and M ≥ 10, then the same argument can be used, by interchanging rows and columns. The only remaining possibilities are when N is 6 or 8, but the second and third lemmas can be used to construct Knight's circuits for these cases.
Theorem 6 follows directly from Lemma 4.
Note that this result is almost as strong as is possible. With the board chequered, as a Chessboard is, the Knight under its legal move will always travel from a square of one colour to one of the other. If the board has an odd number of squares, then the final square reached by the Knight is of the same colour as the starting square. Thus, the Knight cannot return to the beginning in a single move and the tour cannot be re-entrant.
The only extra result required for completeness involves boards of the form 3 × M or 4 × M. These questions were answered in Allen Schwenk's paper Which Rectangular Chessboards Have a Knight's Tour? (1991). Such questions on rectangular boards have all now been answered, though it would certainly not be difficult to dream up more perverse boards if the desire came upon someone to do so.
Returning briefly to tours on the regular 8 × 8 Chessboard, one obvious question remains. We know that tours exist, but how many of them are there? Martin Löbbing and Ingo Wegener (1996), using powerful computers, claimed that the number of Knight's tours on a regular chessboard was 33,439,123,484,294. Unfortunately, this result was shown to be incorrect, since it was not, as it had to be, divisible by 4. Wegener (2000) continued to attempt the question, and later came to the conclusion that the number was in fact only 13,267,364,410,532. While it is difficult to be certain, this result seems more satisfactory. It is divisible by 4, and agrees with independent, unpublished results obtained by Brendan McKay (Weisstein, n.d).