Four reenactor 13th century knights (photograph by Hans Splinter, CC 2.0 license)

# Guarini's problem — the puzzle of the four knights

|
6

Today we get to grapple with the oldest puzzle in chess history.

Imagine that we have a 3 x 3 chessboard with two white knights on a1 and c1 and two black knights on a3 and c3.

If we ignore the two kings and focus on just the nine squares at the lower left of the chessboard, the starting position looks like this.

The challenge is to switch the positions of the white and black knights in the fewest number of moves so that the final position looks like this.

Each knight must stay within the 3 x 3 board (defined by a1 to a3 to c3 to c1). The rules of chess otherwise apply. You can move only one knight at a time and you can have only one knight on a square at any move. Since you need to end up with four knights, it's probably not a good idea to capture a knight along the way.

This is a great time to work out the solution yourself.

As chess puzzles go, this one is easy. While I'm betting that most readers will readily find the right solution, the purpose of this post isn't to merely solve the puzzle. We'll use this puzzle as a device to explore the history of our game and to understand at a deeper level how knights move.

And if you find this puzzle a breeze, why don't you, for extra credit, try to work out whether and how it's possible to swap the knights on a 3 x 3 grid to end up with this position with the same-colored knights at opposite corners?

Warning, there're spoilers below where I'll discuss the authors of this problem, its solution and what we can learn from it.

Paoli Guarini

Today's puzzle is commonly called Guarini's problem, after Paolo Guarini di Forli (Paulus Guarinus in Latin), who included the puzzle into a manuscript on chess he wrote in 1512.

After Guarini's problem laid dormant for roughly four centuries, Walter William Rouse Ball popularized the puzzle and gave it its name in his 1905 book, Mathematical Recreations and Essays

According to John J. Watkins, a professor emeritus of mathematics at Colorado College and the author of Across the Board: The Mathematics of Chessboard Problems, Guarini's problem is the earliest chessboard puzzle that he knows of.

As a nobleman in Renaissance Italy, Guarini led an interesting life during a turbulent time. In Chess in Iceland and Icelandic Culture (1905), Willard Fiske and Horatio Stevens White set forth this sketch of Guarini:

Very little has hitherto been known of Paolo Guarino (as that name stands in the vernacular, a variant being "Guerlnl"), although he has long been recognised by the historians of chess letters as the editor of an important and well-made collection of seventy-six positions selected in 1512 from the Florentine manuscripts....

Thanks, for the most part, to the researches of the learned Italian palaeographer, Dr. Giuseppe Mazzatinti, professor In the royal lyceum at Forli and librarian of the Forllvese communal library, we are now, however, more or less familiar with some of the prominent incidents of Guarino's life.

He was a man of more than usual mark in his day and in the ancient provincial city In which he was born and resided, though descended from Bolognese ancestors. Besides being a cultivator of general literature, he was an architect by profession, and, as such, in a period of stress (1503), was one of the commission which superintended the task of strengthening and otherwise improving the castle, or rocca, of Forli.... [A noted surveyor and astrologer, he] afterwards (1517) furnished a plan for the erection of a notable church (S. Michele de'Battuti Rossi) in his native city.

Guarino also understood and practised the art of printing—not an ordinary accomplishment in that remote trans-apennine region in the closing years of the XVth century. To him is owing the issue of the first book printed at Forli, a work of unique typographical interest.... The only other printed work with which the name of Paolo Guarino is In any way associated, is an important document ("diploma") executed by him in an impression of 500 copies for the dissolute Cesare Borgia, whose one redeeming quality, as in the case of his even more infamous sister, was a willing patronage of letters and lettered men....

In 1512 — the very year in which Guarino was at work at his "Liber de partltia scaccorum" — the horrors of real war were raging in his native region, in which French and Spanish, papal and other Italian troops were taking part. The French, who had followed to Italy that renowned general, Gaston de Foix, duke of Nemours, had, by their threatened movements, led to the flight of a large portion of the wealthier inhabitants of Forli. [The residents of Forli who fled may have remembered their history, for Forli's resistance in 1282 to an earlier siege by the French was so famous that Dante recounted it in his Divine Comedy.]

But a few of the patriotic leaders of the people remained. A French commissioner suddenly visited the city and demanded an immediate supply of stores, for the use of the not very distant French camp, from the already impoverished citizens. The few notable denizens still within the walls, among them "Ser Paolo Guerrini," as he is styled by the narrator of the event, assembled for deliberation, but were soon satisfied that the supplies asked for must be forthcoming in order to avoid the destruction of their homes. Guarino was appointed a commissioner to arrange, with the aid of another member of the small company, the difficult affair, which he did with so much energy and tact that the town was finally saved from the menaced danger.

This good citizen was blessed, we are told with an amiable and intelligent wife, Maddalena, daughter of Antonio Ostoli [a prominent family in Forli that sponsored a chapel and altarpiece at the Church of Santa Maria del Carmine], who bore him two sons and three daughters...

Guarini's wife Maddalena was the daughter of a producer and merchant of fabrics. In 1490 Guarini went into business with his father-in-law, founding a textile trade company and an attached shop.

Guarini was one of Forli's leading citizens, acting as its diplomat, serving on the its Grand Council and holding offices of city elder, conservator, and treasurer.

The historian (and his friend) Leandro Alberti remembered Guarini as being a cultured and refined man "of a very sweet genius and urban and civil way."

Guarini is a worthy man to lend his name to this puzzle. While we owe Guarini thanks for preserving and passing on this puzzle, he was not its original author for this puzzle is far older than his time.

Al-Ádlí ar-Rúmí

Created long before 1512, this puzzle dates back to the 9th century chess master, al-Ádlí ar-Rúmí

As Raymond Keene has written,

A thousand years ago, [Baghdad] was a world capital of science, mathematics and, indeed, chess. During the 8th and 9th centuries in the Caliphate of Baghdad of the Abbasid dynasty, the game truly flourished. Grandmasters, known as Aliyat, developed, the subtlety of whose play, which survives in brief published fragments, rivaled that of modern masters. Among them were Rabrab, Ar-Razi, Al-Ádlí, As-Suli and Al-Lajlaj (the stammerer). The profound expertise of these players is evidence for me that Shatranj, as the old form of chess was known, emerged as the product of an immensely long heritage. Such honed excellence does not burst forth unannounced in a new game after a mere century or so. Even with the improvement in travel and communications which was to take place in the post-mediaeval world, there was still to be a gap of three centuries between the introduction of chess as we know it (about 1475) and the advent of an acknowledged master, such as the 18th-century Frenchman Philidor. Nevertheless, Baghdad could boast several players whose relative strength was comparable to that of the great Frenchman.

Al-Ádlí was the first of these great masters and is a giant of our game.

The Oxford Companion to Chess offers this overview of Al-Ádlí:

Patronized by several caliphs, including a son of Harun al-Rashid, Al-Ádlí was regarded as the strongest player of his time until defeated, not later than 848, by ar-Razi. Al-Ádlí wrote a book on chess... and also a book on nard [the Kitab an-nard], an old board game in the backgammon family often confused with chess by historians. His books have long since been lost but some of his problems, endgames, and opening systems have survived... His name suggests that he came from some part of the eastern Roman Empire, possibly Turkey.

As Yuri Averbakh notes in A History of Chess: From Chaturanga to the Present Day, "[s]ince the days of Harun ar-Rashid, who reigned from 786-809 [CE], caliphs, as a rule, kept the best players in their court. For example, al-Ádlí was considered the strongest chessplayer in the courts of two Baghdad caliphs: al-Wathiq (who died in 847) and al-Mutawwakkil (who died in 861). Only at the end of his life was al-Ádlí defeated by ar-Razi, a newcomer to the court." To show the importance of chess in that era, the Baghdad caliphs would pay pensions to chess masters and would attend championship matches, such as that between al-Ádlí and ar-Razi.

Much like Suhayb ar-Rumi, a former slave in the Byzantine Empire who became an esteemed companion of Muhammad, al-Ádlí's sobriquet was ar-Rúmí, which translates as the Roman. As Franklin Lewis of the University of Chicago explains, "[t]he Anatolian peninsula which had belonged to the Byzantine, or eastern Roman empire, had only relatively recently been conquered by Muslims and even when it came to be controlled by Turkish Muslim rulers, it was still known to Arabs, Persians and Turks as the geographical area of Rum. As such, there are a number of historical personages born in or associated with Anatolia known as Rumi, a word borrowed from Arabic literally meaning 'Roman,' in which context Roman refers to subjects of the Byzantine Empire or simply to people living in or things associated with Anatolia."

Just as Bobby Fischer in our day created Fischer random chess, Al-Ádlí pioneered oblong chess (shatranj al-mustatila in Arabic), a version of chess played on a 4 x 16 board. While the size of the board differs, oblong chess bears more than a passing resemblance to chess 960. To start with, as Harold Murray detailed in his magisterial A History of Chess, there were more than a half dozen common starting arrangements for the pieces. In addition, oblong chess was played with dice, with the roll of the die dictating which type of piece a player could move each turn.

Oblong chess was popular. In the 15th century, the Arab historian ibn Arabshah recorded that oblong chess was played at Tamerlane's court. (Tamerlane was a devout chess enthusiast, so much as that, according to Ibn Arabshah, he named his son Shah Rukh, literally king rook, which is the same as the Persian term for castling, because he was in the process of castling in a game when he heard the news of his son's birth.)

Chess.com already hosts 960 chess, 3 check, King of the hill, Crazyhouse, and Bughouse. Given that oblong chess is an excellent way for players of different abilities to play an interesting and challenging game, perhaps Al-Ádlí's game deserves a revival as an additional variant here someday.

The solution to today's puzzle

Now let's turn our attention to solving today's puzzle. There are two approaches that we can employ.

The first approach, which is what I used, is trial and error. I found the answer on my second try. I'm betting that a number of you solved the puzzle on your first attempt. Still trial and error (which is essentially the "thinking fast" approach I discussed in A queen and her knight) can be hit or miss. Even if you find a solution, you might not be sure that it's the one with the fewest moves.

The second approach is systematic, analyzing the puzzle based upon the nature of the 3 x 3 board and the nature of how knights move. (This is basically the "thinking slow" approach.) The technique that mathematicians bring out to solve these type of problems is graph theory. In fact, the great mathematician Leonhard Euler created graph theory in 1736 to deal with a similar problem — the Seven Bridges of Königsberg — where trial and error wasn't good enough.

Here's how we can use graph theory to solve Guarini's problem.

First, we start with the 3 x 3 board. We note the location of the knights, which we designate as a, b, c and d. We then draw a line on the grid for every path that a knight can take from each square. For example, the white knight at a1 (knight c) can go to either c2 or b3. That gives us the star-shaped diagram in the left image above. As we can see, on a 3 x 3 board, the knights can traverse only eight squares. The central square can be ignored, since no knight can ever enter it.

Second, we imagine that the lines we've drawn in the first diagram are pieces of string and that the squares are buttons tied to the string. (In a mathematician's eyes, the pieces of string are edges and the buttons are vertices.) Two buttons are connected by a piece of string if a knight can make a legal move from one to another. Disentangling these strings gives us the middle diagram above.

Third, for the sake of clarity, we number the cells on the 3 x 3 grid, with a1 being cell 1, b1 cell 2, c1 3, and so forth, ending up with c3 being cell 8. Since we're ignoring the center cell, we have eight numbered cells. This gives us the right diagram above, which depicts graphically both the nature of the 3 x 3 grid and how the knights can move on the grid. For example, the white knight at cell 1 (a1) can move to either cell 5 (c2) or cell 7 (b3).

As a mathematician would say, the three diagrams above are isomorphic, i.e., the second and third diagrams preserve the topological structure and the connectedness of the original 3 x 3 board. In other words, while they might look different, these three diagrams are the same as long as we focus on how the knights move on a 3 x 3 board. So any solution that we find using the third diagram will apply to the original 3 x 3 board.

Guarini's problem challenges us to swap the knights on the 3 x 3 grid. It's a snap to solve this problem using the third diagram above. All we need to do is to move the knights round the circle in one direction or the other.

Since we can start with any of the four knights and we can shift the knights either clockwise or counter-clockwise, there are multiple 8-move solutions. Here is one example.

And to give a better idea of the pattern of the knights' movement, here's an animation, which recalls GM J.H. Donner's argument that "[t]he movement of the knight on the chess board is ... along a circle."

Extra credit

The third diagram above also enables us to answer the extra-credit problem about whether it's possible to swap the knights to end up with the same-colored knights at opposite corners. As we can tell from the third diagram, we can shift the knights clockwise or counterclockwise but it's not possible for one knight to leapfrog another knight.

The four knights on the 3 x 3 board are like four horses on a carousel that cannot change their relative positions. The analogy between knights on a chessboard and horses on a carousel is particularly apt because the modern-day carousel grew out of the medieval carrousel where, as as practice for joustingknights on horseback rode around in a circle tossing balls from one to another .

Thus, graph theory enables us to know with certainty that it's impossible to end up with same-colored knights at opposite corners.