Leonhard Euler
Knight's Tour Problem - The Adventure of a Knight
Derin Değerli
In the intricate art of mind games, there exists an extraordinary dance between chess and mathematics. The strategic scheme behind chess consists of numerous math phenomena, including geometry, game theory, optimization, statistics, and number theory. There is one particular intriguing problem that piqued my interest regarding the relationship between chess and mathematics: the knight’s tour problem. The knight’s tour problem is an old puzzle where the knight makes legal moves on a classical chessboard (8x8) to visit every tile exactly once in one rotation. The animated model below offers a visual demonstration of this problem.
Knight’s tour problem on an 8x8 chessboard
There is a beautiful symmetry in the knight’s tour problem. To find this symmetry, let’s give each move of the knight a number based on their order. The diagram below shows how this symmetry is created in the animated model above.
Knight’s tour problem order of the moves
The order of these moves creates a magic sum where the sum of all numbers in any row and column is exactly the same. In this 8x8 board, the magic sum is the sum of all integers through 1 and 64 divided by 8. Through the formula sum of “n” natural numbers , the magic sum can be rewritten as ÷ 8 which is equal to 260. Although it is fun to discover this symmetry, there is something even more amusing and complex about this problem: finding the number of routes that the tour can be completed through. It is not easy to calculate such routes due to their exponential nature. An increase in the number of tiles creates whole new routes for the knight to discover. For example, to tour an 8x8 classical chessboard using every single possibility, the knight has to take 26,534,728,821,064 different routes. The number of routes that the knight can take as the tiles increase can be calculated in a number of ways. The most known, efficient, and applicable ways are backtracking algorithms, Warnsdorff’s Rule, and the Hamiltonian path. Backtracking algorithms are like exploring a maze. You start at one point, try different paths, and when you reach a dead end, you go back and try a different route. In the context of the knight's tour problem, all possible moves are explored and successful tours are counted. As another method, Warnsdorff’s Rule can be used. This rule suggests that the knight should prioritize squares with the fewest options for its next move. To count the number of routes, the knight is guided from different starting points, following the rule and keeping track of how many times it successfully visits every square. Last but not least, the Hamiltonian path is another method. In this method, the chessboard is represented as a graph where each square corresponds to a vertex, and edges represent valid knight moves between squares. The task is to count the number of Hamiltonian paths in this graph, as these paths correspond to valid knight's tours that visit each square exactly once.
In conclusion, the knight's tour problem on an 8x8 chessboard reveals a captivating interplay between chess strategy and mathematical intricacies. The puzzle's symmetrical beauty, illustrated through the magic sum concept, adds an intriguing layer. However, the real challenge lies in calculating the exponential number of routes the knight can take to complete the tour. Various methods, including backtracking algorithms, Warnsdorff's Rule, and the Hamiltonian path, offer distinct approaches to tackle this complexity. This topic can also be extended where knight’s tour problems can be observed not only in square chessboards, but also chess boards of different geometric shapes.
Sources:
https://www.jstor.org/stable/41190919?searchText=Mathematics+of+chess&seq=1
https://en.wikipedia.org/wiki/Knight%27s_tour#/media/File:Knight's_tour_anim_2.gif
https://www.sciencedirect.com/science/article/pii/S0166218X04003488#:~:text=The%20knight's%20tour%20problem%20is,algorithms%20for%20subsets%20of%20chessboards.
https://www.sciencedirect.com/science/article/pii/S0304397521007052#:~:text=The%20exact%20number%20of%20knight's,tours%20have%20also%20been%20studied.
