Last updated on December 29, 2020
The chessboard with its 64 squares is a huge playground for people who like solving puzzles. The knight’s tour problem is a classical chess problem that has been studied for centuries.
Arabs and Chess
The Knight’s Problem
The Knight is the piece with the trickiest move in chess. The Knight moves in an L-shape in any direction.
Perhaps one of the oldest puzzles is the so-called Knight’s Tour:
Can the knight (the horse) visit each square exactly once and return to the starting square?Knight’s Tour problem
Around 845, al-Adly al-Rumi (العدلي الرومي) from Baghdad gave the answer: Yes, it is possible.
Al-Adly al-Rumi’s books are all lost, but referenced in later works. The “Knight’s Problem” is found in a manuscript from around 1350 by Abu Zakariya Yahya Ibn Ibrahim al-Hakim. The title of the manuscript نزهة أرباب العقول في الشطرنج is usually translated as The Delight Of The Intelligent (a description of chess).
In the diagram, the tour begins from “1” and finishes at “64”. The tour is re-entrant, and if a line were drawn connecting 1 and 64 by a knight’s move, the result would be a knight’s circuit.
Who was al-Adly al-Rumi?
Al-Adly al-Rumi (800 – 870) was a philosopher who lived in Baghdad. He became the best player (of a pre-version of modern chess) in the courts of the caliphs of al-Wathiq (842-847) and al-Mutawakkil (847-681) in Baghdad.
His book Kitab al-Shatranj (Book of Chess), which was written around 840, included chess history, openings, endings and mansubat (chess problems).
The Arabic origin of the chess term “Tabiya”
An important and common chess term goes back to al-Adly and the Arabic language. Chess players know the term Tabiya.
In chess, a Tabiya is a position in the opening that is heavily standardized and thus a “starting” position. The term relates back to al-Adly who, for the first time, invented a system for sorting out openings and called certain basic positions Tabiya. But how is that written in Arabic?
There are two ideas:
تَعْبِيّة or تَعْبِئة
The word Al-Adly used in his lost treatise was probably تعبية taʿbiyya (also تعبئة taʿbi’a). (@Pablo: THANKS!)
Its root (عبي) means:
- Set in order, dispose or arrange the army in their places (Edward William Lane, Arabic-English Lexicon).
- To set troops in order (Francis Joseph Steingass)
- وَعَبَّى الجَيْشِ .. أَصْلَحَهُ وَهَيَّأَهُ تَعْبِيَةً وَتَعْبِئَةً وَبَعْبِيئاً (Lisān al-ʿArab, Ibn Manzur)
This word is also used in Arabic-speaking chess forums until today. The Arabic word denotes nature, normal manner.
How can you solve the “Knights Tour”?
The formulation of the problem
Let’s break down the problem of the Knight’s Tour.
The brilliant Swiss mathematician Leonhard Euler (who, by the way, was the first to write f(x) to denote the function f applied to the argument x) also took on the problem in the 1750s:
“I found myself one day in a company where, on the occasion of a game of chess, someone proposed this question: To move with a knight through all the squares of a chess board, without ever moving two times to the same square, and beginning with a given square.“
Euler’s solution shown above is a closed tour. Why do we call it closed? If the knights makes the final jump and lands on a square from which it can hop to the square from which it started, it is known as a closed tour. Otherwise, if the knight cannot jump to the original square, it is an open tour.
For a detailed analysis of Euler’s solution, have a look at this PDF).
Previously, in 1735, Euler presented a solution of the problem known as the Seven Bridges of Königsberg (Eulerkreisproblem). The city of Königsberg in Prussia (Kaliningrad, Russia) was set on both sides of the Pregel River and included two large islands: Kneiphof and Lomse. Seven Bridges connected both islands or the two mainland portions of the city.
The problem was to find a walk through the city that would cross each of the bridges once and only once. Euler proved that the problem has no solution. With his analysis he laid the foundations of graph theory.
The Knight’s Tour puzzle is also a graph theory problem. In mathematics, graph theory is the study of graphs which are mathematical structures used to model pairwise relations between objects. A graph is made of vertices (also called nodes or points) which are connected by edges (also called links or lines).
Let’s go back to chess. For example, the vertex that represents the a1 square would have edges connecting it to the vertices represented by b3 and c2 only – since they are the only two squares the knight can jump to from a1.
Let’s put the knight to e4. The vertex representing e4 would have edges connecting it to 8 other vertices: f2, g3, g5, f6, d6, c5, c3 and d2.
Now we need to introduce another term: A Hamiltonian path or traceable path is a path that visits each vertex of the graph exactly once. The closed Knight’s tour is a Hamiltonian cycle.
So much for the theory. How can we practically solve it?
Algorithms for the Knight’s Tour
There are two main approaches. Nowadays also neural network solutions are tried as well as “divide and conquer” solutions.
The simplest solution to this puzzle is a backtracking algorithm. You choose an arbitrary route and when you have reached a dead end, you take the last move back and choose an alternative move instead. This algorithm will definitely find a solution – but it is very slow and needs a lot of computing power.
We can optimize the above algorithm using the Warnsdorf’s rule – named after H.C. von Warnsdorf, a German judge, who developed the method in 1823.
What’s the idea behind it?
The knight always moves to the square from which it has the least free (i.e. not yet visited) squares available for its next move. This heuristic reduces the probability that the knight won’t be able to visit some squares. The Warnsdorf rule cannot guarantee that the solution will be found because the knight may be trapped in a dead end. But it is much faster.
Remark: The US-Belgian chess player George Koltanowski was famous for solving the Knight’s Tour blindfolded.
Some examples of solutions
How many solutions are there?
Unbelievably many! In 1997 Brendin Mckay (Computer Science Department, Australian National University) calculated the number of solutions: 13,267,364,410,532 (!) knight tours.
Regarding the knight’s tours that can’t be turned into a loop, Alexander Chernov calculated the following number: 19,591,828,170,979,904.
Famous ancient Arab chess players
Chess has not played a big role in Arab countries for decades. In recent years, it has changed and Egypt became a strong chess nation with strong grandmasters. The most famous and best African players are GM Bassem Amin (among the top 50 in the world) and Ahmed Adly (world junior champion 2007).
If we go back in time, the Arabs were masters of the game (or a perversion of the modern game) and can be called pioneers.
- al-Razy (رازی) wrote a book on chess problems around 845 (!). He defeated al-Adly to become the strongest chess player in the world.
- Around 890 Abu-Bakr Muhammad ibn Yahya al-Suli co-authored a book of problems (mansubat) and a book of openings (tabiyat).
- The historian Abu Ja’far Muhammad ibn Jarir al-Tabari (838-923) related a chess incident of the caliph al-Mutazz (المعتز). The Caliph was playing a game of chess when a messenger brought the head of his rival al-Musta’in (المستعين) to him. The caliph, as the story goes, paid no attention until the chess game was over.
- In 947 the Arabic historian al-Masudi (المسعودي) wrote a history of chess in India and Persia. al-Masudi was the first to combine history and scientific geography in a large-scale work.