The so-called “Knight's Tour” is an ancient mathematical puzzle related to chess. It consists of finding a sequence of valid moves for this piece so that it travels across all squares of the board, visiting each one only once. Entire armies of mathematicians have tackled this problem, yet the exact number of solutions remains unknown. The problem has been posed on boards of different sizes and under various initial conditions, and it remains as engaging as it was 1,200 years ago.
Over the centuries, mathematicians have used the board and pieces of the game of chess to pose thousands of puzzles, many of which are so complex that they have not been solved even with the most powerful supercomputers.
The Knight's Tour
The so-called “knight's tour” is one of the chess-related challenges that is simplest to state but hardest to solve. The challenge is to place a knight on one square of an empty chess board, and, respecting the valid moves for this piece, travel across every square without passing through the same one twice, returning (or not) to the starting position. Although several proven tours satisfy the stated conditions, the exact number of possible solutions for the knight's tour remains unknown despite the efforts of many mathematicians.
One of the earliest known solutions dates from the ninth century. Indeed, in a manuscript by the Arab Abu Zakariya Yahya ben Ibrahim al-Hakim, two valid tours are documented. One belongs to a chess player named Ali C. Mani, and the other to Al-Adli ar-Rumi, an enthusiast who also wrote a book about a popular form of chess at that time called “Shatranj”.
Over the centuries, the knight's tour has been modified, giving rise to different variants. For example, boards of dimensions other than the traditional 8x8 squares can be used, or the ending square does not have to coincide with the starting square. This last variant makes things a little easier and increases the number of possible solutions even more. When the knight must return to the same square it started from, the tour is said to be “closed”. As-Suli, another Arab master of Shatranj, who based his analysis on the earlier works of Al-Adli, found around the year 900 CE two closed tours:
The first major mathematical study of this problem is believed to be by the brilliant mathematician Leonhard Euler (1707–1783), who presented his work to the Berlin Academy of Sciences in 1759. In fact, Euler, a recognized figure who published more than a thousand brilliant works and books during his lifetime, knew that the Academy offered a prize of 4,000 francs to anyone who could shed some light on the knight's tour. Although many solutions were known, no one had managed to estimate their number or find an algorithm that could generate them easily.
Those who had tackled the problem knew that finding a solution by simply moving the knight “by trial and error” was practically impossible, but they were also unable to find a method that would facilitate the process. So Euler tackled the problem and found that there were several closed tours that had the advantage of allowing one to start from any square on the board and complete the tour from there. Unfortunately, at the time he published his work, Euler was serving as Director of Mathematics at the Berlin Academy, so for ethical reasons he could not collect the prize.
Today we know that the number of possible tours is truly very large. Despite using the largest computers available to search for all ways the knight can traverse the board, we are not sure that the values found are correct. In 1995, Martin Löbbing and Ingo Wegener set 20 Sun computers—powerful for the time—to work for four months and published a paper in which they proclaimed that the number of possible tours on an 8x8 board was 33,439,123,484,294. Two years later, in 1997, Brendan McKay tackled the knight's tour by dividing the board into two halves and arrived at a somewhat smaller result: “only” 13,267,364,410,532 possible tours would exist. To get an idea of what these numbers mean, suffice it to say that if a robot could move the knight to complete one tour per second, it would take more than 420 years to try them all.
What use does knowing these tours have for a chess player? Very little. But this kind of challenge has driven many enthusiasts or mathematicians to tackle problems that eventually often have practical applications in finding optimal routes that pass through a certain number of places or that allow, for example, saving time or fuel. In any case, the Knight's Tour has managed to keep mathematicians interested for centuries, and everything seems to indicate that it will continue to do so for a long time. Don't you think?
https://old.neoteo.com/23-damas-versus-39-caballos-de-ajedrez-quien-gana/
For further reading, see The knight's tour.
