A HOME FOR ANYONE ADDICTED TO ARABIC. 
JOIN ARABIC FOR NERDS➕

Support this site with a membership: For only $2.99 a month or $29.99 a year, you can have a true AD-FREE experience. You also get a 15% discount in my shop and a monthly premium newsletter. Find out more here.

SUPPORT THIS SITE

Passion doesn't need money. Unfortunately, my web provider does. Your contribution ensures that this site will grow and grow.

Buy Me A Coffee

PayPal Donate
amazon wishlist button
Free monthly newsletter

Subscribe to my FREE newsletter and get 10% off in my store!

chess pieces ai

Chess and the Knight’s Tour: How an Arab Solved It

The Knight’s Tour problem is a famous mathematical chess puzzle. The first solution provided an Arab philosopher in the 9th century from present-day Iraq.

Last updated: 8 months ago

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.

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.

knights move jpeg

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?

sep

Knight's Tour problem
knightstour
The Knights Tour. credit: wikimedia.

Al-Adly's solution

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).

knight tour solution adli
This is al-Adly's solution to the Knight's Tour. It is most probably the first documented solution of this intriguing problem.

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).

We are a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for us to earn fees by linking to Amazon.com and affiliated sites.


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 (, 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.

If you don't know Arabic – the pronunciation that comes pretty close to the original Arabic would be: “tabeea”.

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
This is one of Euler's solutions.

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.

euler bridge

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.

boarda1

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.

knight graph
Knight's graph showing all possible paths for a knight's tour on a chessboard. The numbers on each node indicate the number of possible moves that can be made from that position. picture credit: Wikimedia

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.

Backtracking

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.

Warnsdorf's rule

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

solutions
Some examples of solutions (closed track)

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 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 . al-Masudi was the first to combine history and scientific geography in a large-scale work.

NOTE ABOUT A PREVIOUS PICTURE IN THIS ARTICLE:

In an earlier version of this article I used a “feature image” that showed a photo of chess pieces. The photo was free to use, but the pieces in the picture were trademarked/copyrighted by the manufacturer of the chess pieces, which I was not aware of, and for which I sincerely apologize. Due to a DMCA Copyright Infringement Notice dated August 3, 2023, which I received from the trademark attorney representing “Wood Chess – Disadvantages”, I have removed the image and replaced it with an image showing chess pieces that are not and have not been produced by “Wood Chess – Disadvantages”, but drawn by myself. Although the image objected to by “Wood Chess – Disadvantages” is no longer used in this article and has been deleted from my servers, their legal counsel has requested that I include the following link in the article to give credit [and also as an information for people who may have seen the article with the objectionable image in an archived version of a third party website or found it in the cached version of a search engine or as a cached or previously published or archived post (among other possibilities)], which I hereby do: https://www.woodenearth.com/blogs/wooden-blog/is-chess-really-a-good-game

DISCLAIMER: As the operator of the website Arabic for Nerds, I hereby disclaim any liability for the use of the above mentioned link. Furthermore, I would like to point out that the mention of this link is in no way to be understood as a recommendation, endorsement or affiliation.

Subscribe
Notify of
guest
2 Comments
Inline Feedbacks
View all comments
Pablo Tornielli
Pablo Tornielli
3 years ago

Interesting article!

I’d like to add that the word Al-Adly used in his lost treatise was most probably تعبية taʿbiyya (also تعبئة taʿbi’a), rather than طبيعة. Its root (عبي) means:

Set in order, dispose or arrange the army in their places (Edward Willian Lane, Arabic-English Lexicon).
To set troops in order (Francis Joseph Steingass)
وَعَبَّى الجَيْشِ .. أَصْلَحَهُ وَهَيَّأَهُ تَعْبِيَةً وَتَعْبِئَةً وَبَعْبِيئاً (Lisān al-ʿArab, Ibn Manzur).

In the following manuscript you can find the word تعبية and its plural تعابي with the relevant sense:

https://drive.google.com/file/d/1FSKOsKNqgHfJPiVgt3Z_lvABjUuAILYD/view?usp=sharing

The term is still in use in the world of (Arabic-speaking) chess:

https://www.google.com/search?q=%D8%AA%D8%B9%D8%A8%D8%A6%D8%A9+%D8%B4%D8%B7%D8%B1%D9%86%D8%AC&oq=%D8%AA%D8%B9%D8%A8%D8%A6%D8%A9+%D8%B4%D8%B7%D8%B1%D9%86%D8%AC&aqs=chrome..69i57.27345j0j4&sourceid=chrome&ie=UTF-8

Previous Article
Yehia Molden

20 questions for: Yehia Moldan (#24)

Next Article
superlativejpg

Comparative and Superlative in Egyptian Arabic

Related Posts

Subscribe to our FREE newsletter

Don't miss any updates and get your regular dose of Arabic.