# Early History of Knight's Tours

## Acknowledgement

Much of the information given here on the mediaeval tours comes from H. J. R. Murray's A History of Chess (1913) and other manuscripts that he left unpublished at his death in 1955, particularly an incomplete one with the similar title The Early History of the Knight's Tour written about 1930. These manuscripts are now kept at the Bodleian Library, Oxford University. The earlier works of Antonius van der Linde, Geschichte und Litteratur des Schachspiels 1874 and Quellenstudien zur Geschichte des Schachspiels 1881, are also important sources. Writers of books on mathematics that include sections on knight's tours unfortunately tend to be ignorant of the work of the chess historians, and usually trace the history of the subject back only to the 1725 edition of Ozanam's book of mathematical recreations, which is where our next section on Rediscovery of the Knight's Problem begins.

## China, −2200

The 3 by 3 diagonal magic square is said by many sources to have been known in China about 2200 BC, though what evidence there is for this date I'm not sure. [Claude Berge Principles of Combinatorics Academic Press 1971, cites F. M. Müller Sacred Books of the East vol.XVI (The Yi-King) Oxford University Press 1882.] The square is usually presented in the orientation shown here, but of course by rotation and reflection (but keeping the number symbols the right way up!) it can appear in eight different orientations.

If the successive numbers are joined by straight lines the result is a tour of the 3 by 3 board by moves with coordinates {0,1}, {1,1} and {1,2}. This tour is a geometrical pattern which is centrosymmetric, i.e. unaltered by 180° rotation. In Variant Chess pieces with these moves are known respectively as wazir, fers and knight, and a combined wazir + fers + knight is known as a centaur. So the 3 by 3 diagonally magic square can be described as a centaur tour of the 3×3 board. The knight's move, which some take to be the defining element of chess, may have first been seen in the path of the successive numbers in this magic square.

## Ali C. Mani and al-Adli ar-Rumi, 840

In his History of Chess (1913) H.J.R.Murray describes an arabic manuscript, at that time #59 in the John Rylands Library, Manchester, scribed by Abu Zakariya Yahya ben Ibrahim al-Hakim, with the title Nuzhat al-arbab al-'aqulfi'sh-shatranj al-manqul {The delight of the intelligent, a description of chess}. This contains two 8 by 8 tours, one by Ali C. Mani, an otherwise unknown chess player, and the other by al-Adli ar-Rumi, who flourished around 840 and is known to have written a book on Shatranj (the form of chess then popular), which however survives only in extracts in this and other manuscripts. The later master of Shatranj as-Suli based his works on those of al-Adli, which he criticised.

## Which was the earliest knight's tour?

In his 1902 article in the British Chess Magazine, the chess historian H.J.R. Murray was of the opinion that Rudrata's half-board tour (see below) was the earliest known knight's tour, but by 1930 his view had changed to the above tour by Al-Adli. However, since the tour by Mani appears in the same manuscript, and is of a form so typical of many later constructed (e.g. de Moivre's tour of 1722 — see Rediscovery of the Knight's Problem) in starting in a corner, skirting the edges and ending up in the centre, and Al-Adli's is clearly more advanced, being a reentrant tour, I have chosen to place Mani's first, but no doubt there were other precursors that have not been recorded. The Islamic Empire was at its height around 800, extending from north Africa to northern India, and its capital Baghdad was probably the largest city in the world at the time. The discovery that the knight could make such a tour of the chessboard, wherever it may have been made, would soon have made its way to the capital.

## Rudrata, 900

The earliest Indian knight's tour is that given on a half-chessboard in the verse work Kavyalankara by the Kashmirian poet Rudrata, ascribed to the reign of Sankaravarman, 884 – 903. He also gives a simple boustrophedonal chariot (i.e. rook) tour and a sawtooth elephant tour. According to H.J.R.Murray (1913, pp.53-55) our knowledge of this work comes from a commentary by Nami of Guzerat (1069) and analysis by H. Jacobi (1896). The tour of the knight (known as turaga = horse) and the tours by rook and elephant, were apparently presented by a series of syllables on the squares which make sense when read in the sequence of the tour (i.e. what I call a cryptotour). For more on this see the page on Cryptotours. Murray maintains that the verse also makes sense when read normally; this may be true for the simpler tours, but seems very improbable to me in the case of the knight's tour.

```chariot (rat-ha)           elephant (gaja)
1  2  3  4  5  6  7  8     1  3  5  7  9 11 13 15
16 15 14 13 12 11 10  9     2  4  6  8 10 12 14 16
17 18 19 20 21 22 23 24    31 29 27 25 23 21 19 17
32 31 30 29 28 27 26 25    32 30 28 26 24 22 20 18
```

The elephant, which is a piece still in use in Burmese and Thai forms of chess and was described by al-Beruni as used in India, is a {1,1}-mover (i.e. one step diagonally) with the extra power of a single pawn-like forward step (the five moves thus representing the elephant's four legs and trunk). I have shown the form of tour proposed by Murray, rather than that given in the commentary which has 17 at the start of the third row down so that 16-17 is not an elephant move. This also ensures that, like the rook tour, the columns are magic (all add to 66), being formed of pairs of complements adding to 33.

Rudrata's knight tour can be repeated on the lower half of the board so as to give a complete though not closed tour. A diagram showing it in this form, reflected left to right, appears in "a Persian manuscript of the early 19th century probably compiled in Northern India", described by George Walker (1844). Another version, in which the half-board tour is rotated 180° on the lower board and slightly modified to join to the upper half appears in the Manasollasa of Somesvara III, described by F. Bernhauer, "Der Rösselsprung im Manasollasa", Aus dem wissenschaftlichen Leben des Südasien-Instituts (1997).

## as-Suli, 946

Four other tours survive in the Arabic manuscripts, and are due to the later chess writer Abu-Bakr Muhammad b.Yahya as-Suli. Murray describes two arabic manuscripts, one in Constantinople (as it then was) and the other in Cairo. These are of the same work Kitab ash-shatranj mimma'l-lafahu'l-`Adli was-Suli wa ghair-huma {Book of chess; extracts from the works of al-'Adli, as-Suli and others}. The Turkish ms is written by Abu Ishaq Ibrahim b. al-Mubarak b.'Ali al-Mudhahhab al Baghdadi and has the Muslim date 535 (i.e. AD 1140). The Egyptian ms was dated as written about AD 1370. The two authors mentioned in the title are known, from a bibliography by b.Ishaq an-Nadim the Kitab al-fihrist, compiled 988, to have written books on chess, but these have not survived except as extracted in these and other later manuscripts. The Turkish ms contains four tours and the Egyptian ms has three of these, all attributed to as-Suli. The first two are knight tours. The first of these incorporates a 30-move tour (numbered 11 to 40) in the left halfboard which (when closed) shows perfect axial symmetry (which I call Sulian symmetry). The other is composed of two half-board tours.

Murray (1930) describes the solution to the second of as-Suli's tours as "given in two poems, one by Tahir al-Basri, the other by ibn Duraid (died 934). Each poem consists of 64 lines, and the first two letters in each line give the name of the square in the literal notation used by the Muslim chessplayers."

Murray continues: "Two other tours in the Arabic work based upon the works of al-Adli and as-Suli are more ambitious, and very remarkable. The text of the first runs: 'This diagram is arranged for the taking of two sets of chess from the board by the knight, which moves according to the knight's leap and according to the fil's leap. The knight starts from 1 and moves according to the order of the numbers. The arrangement of the diagram is such that the piece moves alternately as a knight and as a fil.' The text of the second is shorter: 'The capture of two sets of chess by way of revenge, with the knight's leap and the firzan's leap.' Arabic poems, constructed on the lines already described, are given in the manuscripts which solve these tours. That for the knight-fil tour was composed by 'Ali ibn Abi 'Abdallah ash-Shirazi." [For more on this method of presentation see our page on Representation of Tours.] The firzan (now called fers) moves one step diagonally and the fil (now called alfil) two steps diagonally. In constructing tours of this type as-Suli was well ahead of his time.

## Somesvara, 1150

The Manasollasa (translated "Freude des Geistes" i.e. "Delight of the Spirit" a traditional sobriquet for chess) is described as a "Fürstenspiegel" ("Princely Mirror") written for King Somesvara III of the Kalyani area in central India (c.1150). Another tour in this source is of Mani type. The tour is described in the form of a list of two-letter coordinates. [Once again the reader is referred to our page on Representation of Tours.] Bernhauer gives the open tour shown in the first diagram below. However, the sequence of syllables is somewhat corrupt and, as listed on the third page of Bernhauer's article, ends with the cell a knight's move from the corner. This suggested to me that the tour was intended to be reentrant, and led me to the second diagram which seems the most likely interpretation in my view.

## King's Library, c.1275

The only mediaeval European tour on the whole chessboard is one in a manuscript, dated as of "the last quarter of the thirteenth century" in the King's Library [formerly part of the British Museum, but now I believe in the new British Library building], written in Anglo-Norman. This has the description 'Guy de Chivaler'; where 'guy' has the archaic meaning of joke or puzzle. It is formed of two half-board tours joined together. It may be noted that the route in the top right quarter, g5 to g6 is as near as it is possible to get to a 4×4 tour, using only the cell g4 outside the 4×4 instead of the corner h5.

A half-board tour occurs in the same manuscript, presented in the form of the 32 chessmen occupying the left half of a board. The knight in the corner is to take the white pawns first then the black pawns, "travelling twice round the board", then the bishops, knights, rooks, queens and kings in that order. Without the "twice round the board" condition there is a second solution, as shown above.

## Nicolas de Nicolai, c.1325

A Latin manuscript of the first half of the 14th century in the Bibliotheque de Paris [described by van der Linde 1874 and Murray 1913, pp.627-8] is a version of the Bonus Socius {Good Companion} chess problem collection which exists in numerous manuscript copies. The writer of this manuscript is identified as Nicolas de Nicolai, a scholar from Picardy who studied and lectured at the Lombard universities. He presents a knight's tour problem in the form of an arrangement of the 32 chessmen in the upper half of a chessboard. The white knight in one corner is to capture all the other officers except the kings, and then all the pawns and finally the two kings. The first half of the tour is determinate, but the sequence of capture of the remaining pawns can be varied, giving six solutions, (a) to (f) as shown here.

Note that the cells used in the first and second halves of the tour form a domino pattern. This is typical of all tours on 4-rank boards, as was shown by Sainte-Marie 1877. The arrangement of the chessmen on the board in the King's Library ms is different from that of the Bonus Socius manuscript, but the solution is the same as diagram (a) above. The later collection of chess problems known by the name of Civis Bononiae (middle of the fifteenth century) also exists in numerous different manuscript copies, some of which contain a tour. A. Chicco and L. Porreca Dizionario Enciclopedico degli Scacchi suppose Civis Bononiae to be a professor teaching rhetoric in the Bologna University, with the name Buoncampagno da Signa; Signa being a little village near Florence. This tour is identical to solution (f) of Bonus Socius. A version of the Civis Bononiae collection was made by Paulo Guarini di Forli (died 1520) in 1512 (now in the J. G. White collection, Cleveland Library, Ohio, USA). His diagram shows the CB tour reflected, with a knight at the top right corner and the successive squares lettered in two styles, showing the two-part structure of the tour. All these manuscripts are thus related. The first printed tour occurs in the French work S`ensuit leux Partis des Eschez, printed in Paris between 1530 and 1540. This is the same as the Civis Bononiae tour.

## al Amuli, 1352

The Persian encyclopaedia Nafa'is al-funun fi'ara'is al-'uyun {Treasury of the Sciences} by Muhammad b. Mahmud al-Amuli (died 1352) survives in numerous manuscript copies of variable quality. It has three chapters on chess including a corner-to-corner tour. [Murray 1913 p.177, 1930 p.4]

Murray (1930) reports that "A Dresden manuscript of the end of the fourteenth century gives a half-tour without solution and sets as a wager game a tour over a board of 4×4 squares" and that "The sixteenth century Persian manuscript on chess in the library of the Royal Asiatic Society makes some remarks on the tour, and promises to give tours on the whole board and on boards of 4×8 and 4×4 squares which are lost owing to the fragmentary condition of the manuscript. The author boasts a little, for the tour on the 4×4 board is an impossibility." In his History (1913) Murray gives reasons for believing this manuscript may be due to Ala'addin Tabrizi, the leading player at the court of Timur. A translation by Forbes (1860) however refers to "one quarter of the board" rather than to a 4×4 board. The wording is critical, since a closed tour is possible on one particular non-rectangular quarter-board. I call this puzzle "Aladdin's Conundrum". Unfortunately there is no firm evidence that this quarter-board tour was known before de Hijo (1882).

## European work, after 1500

The remaining knight's tours in the late mediaeval European chess manuscripts are all confined to the half-board. Three are described by van der Linde and Murray. First, one by Joannes Chachi of Terni, included in his manuscript collection of chess problems, written in Rome in 1511; manuscript #791 in Casanatense Library, Rome [Murray (1913) pp.727, 730]. Second, one in Gianutio dalla Mantia's Libro nel quale si tratta della Maniera di giocar a Scacchi, con alcumi sottilissimi partiti, nuovamente composto (Antonio de Bianchi, Torino, 1597). Several writers, following Lucas (1872), have noted that the Gianutio tour can be combined with a copy of itself to form a closed tour of the whole board, however, D. E. Knuth points out that the Gianutio tour is in fact diagrammed at the top of an 8×8 board, so the possibility of duplicating it to form a symmetric compartmental tour was evidently missed. Third, a tour described as Florentine with the same end-points as the Gianutio tour.

## Other Knight Paths

Murray (1902) mentions an Arabic ms in the British Museum, which he dates 1257. He writes: "[This ms] contains two problems partaking somewhat of the nature of knight's tours. The problem in both is to capture all the pawns in the minimum number of moves. There is no explanatory text or comment to the first of these problems, but the second is to be solved in thirty moves." The first has Ng1, Ps on a8-h1 diagonal, and is solved in 17 moves. The second has Ng3 and Ps along both main diagonals, and solves in 30 moves.

The earliest Arab chess manuscripts (al-'Adli c.840) also contain simple puzzles involving the smallest possible knight-tourable boards. In one you are to place seven pawns round three edges of the 3×3 board, leaving only the top square vacant, each new pawn being placed at a knight's move from the preceding one (Murray 1913 p.337). The trick is to start at a knight's move from the vacant cell. These manuscripts also contain the puzzle of the four knights, often attributed to the later writer Guarini (1512), where white and black knights placed in the corners of the 3×3 board are to be interchanged. The knights go in procession round the star-shaped closed tour of the eight edge squares.

## Bhatta Nilakant-ha, 1650?

A tour is reported in the Bhagavantabaskara, described by Murray (1913, 1930) as a Sanskrit work on ritual, law and politics, written "either about 1600 or about 1700  the uncertainty being due to doubt as to the particular chronological era employed by the writer in dating his work." I have been unable to obtain an opinion from modern Sanskrit scholars, on the dating of this work. If the tour was in fact composed around 1600, or even 1700, it is a very remarkable isolated achievement, being a fully symmetric closed tour, before the work of Euler (1759). However, this tour first became known in the west in an article by Monneron (1776) written after the work of Euler, so I show it under that date in Rediscovery of the Knights Problem. The Nilakant-ha tour is given three times in his book, numbered from different points, the first being attributed to king Sri Sinhana of Sinhaladvipa (now Sri Lanka), the second to Nilakant-ha's father Samkara, the third to Nilakant-ha himself. Murray reports that the tour is also given in the Sardarnama, a modern Persian chess work written in the Indian Deccan, 1796-8, by Shir Muhammad-Khan. The Harikrishna manuscript of 1871, reproduced in S. R. Iyer's Indian Chess (1982), also contains the three versions of the Nilakant-ha tour, following others attributed to the Rajah Krishnaraj Wadiar of Mysore which date from 185268. The tour also appears in Naidu (1922). Indian works of the 19th century contain numerous tours but some of these are from European sources, thus, though tempting, it is impossible to justify claims for an earlier date for the Indian examples in the same sources.

## B. Frénicle de Bessy, 1693

Frénicle (died 1675), was the first to list all the 4 by 4 diagonally magic squares. The work was published after his death in: "Des Carres Magiques, Divers Ouvrages de Mathem. et de Physique (Par Messieurs de l'Academie Royale des Sciences de Paris 1693) pp.423-507" [as cited by W.Ahrens] Reprinted in: "Des Quarres ou Tables magiques. Including: Table Generale des Quarres Magiques de Quatre, Memoirs de l'Academie Royal des Sciences, depius 1666 jusqu'a 1699, vol.5, pp.209-354 (Paris 1729)." A computer print-out of the list is given in New Recreations with Magic Squares by W.H.Benson and O.Jacoby (Dover Publications 1976). They cite the reference: K.H. De Haas, Frénicle's 880 Basic Magic Squares of 4x4 cells, Normalised, Indexed and Inventoried (D. Van Sijn & Zonen, Holland, no date given).

Very surprisingly all but one of these require three or more types of move; the exception is number 100 in the list. This uses only wazir and knight moves and in variant chess terms is thus an emperor tour. This special case does not seem to have been noticed until I reported it in Chessics #26 1986. As I also noted there, two of the magic squares (2 and 619 in the list) can be interpreted as magic queen tours, but these use three or four different moves.

According to work of my own, when these diagonally magic squares are counted as geometrical tours, the total reduces to 382. This total is made up of: 6 eightfold magic (equivalent to 48 in Frénicle's list); 64 fourfold magic, namely 40 with null symmetry, 16 axial, 8 central (= 256 in F); 16 threefold magic (= 48 in F); 232 two-fold magic, namely 44 null, 60 axial closed, 96 axial open, 16 central closed, 16 central open (= 428 in F); 64 singly magic (= 64 in F).

This History of Knight's Tours continues with: Rediscovery of the Knight's Problem.