Years ago, a colleague recommended me the book “A Vida Modo de Uso” by the Frenchman Georges Perec, winner of the prestigious Médicis prize in 1978. To say that I was fascinated would be an understatement. The meticulous, obsessive way in which Perec describes down to the last detail the contents –furniture, decorations, accessories– and the stories of the rooms of a Parisian building, to construct a vertiginous puzzle of the lives and thoughts of its residents, could not be most unlike anything I’ve read before (or since).
What I didn’t know at the time was that the structure of this remarkable work is based on an ancient and famous mathematical problem. Perec conceives the building as a “board”, consisting of ten rooms on each of the ten floors, and makes his narrative move on this board according to the movement of the knight in chess: two squares in one direction and one in the orthogonal direction. Thus, the book contains a solution to the problem of the horse walking on a board with ten rows and ten columns.
I told you last week that this problem – how to move a knight over all the squares on the chessboard without going through the same square twice – dates back to the 9th century in India. In the West, the first to study it systematically was Leonhard Euler, in 1759. He found a method to calculate solutions and realized that they exist in large numbers.
In 1823, the German HC von Warnsdorf proposed a heuristic rule for calculating solutions: at each step, the knight must be moved to the “least promising” accessible square, the one from which the number of moves available in the next step will be smaller. This method is quite efficient and was computationally implemented in 1984.
We need not stick to the usual eight-by-eight chess board: the problem has also been studied for general rectangular boards, with any number of rows and columns. In 1991, the American A. Schwenk characterized which boards have horse rides. In particular, we know that such walks always exist if the row and column numbers are both greater than four. In addition, in this case there are closed tours, that is, that return to the starting square, provided that the number of squares on the board is even.
Thus, the “curious problem” that caught Euler’s attention more than 250 years ago continues to drive scientific progress. Among recent advances is the use of artificial intelligence to find horse rides efficiently. The idea is to use neural networks in which each possible movement of the horse is represented by a “neuron”. The network can then be trained to activate neurons that form a solution and deactivate others. Such algorithms can be applied in several practical problems.
PRESENT LINK: Did you like this text? Subscriber can release five free hits of any link per day. Just click the blue F below.
