PG26839.B00173
[PDF page 172] 156 UNICURSAL PROBLEMS. [CH. VI second and third diagrams will answer our purpose equally well and are easier to draw. A G J L N P Q R S T B C D E F H KM O U A B C D E F G H J K L M N O P Q R S T U A B C D E F U The first problem is go “all round the world,” that is, starting from any town, to go to every other town once and only once and to return to the initial town; the order of then towns to be first visited being assigned, where n is not greater than five. Hamilton’s rule for effecting this was given at the meeting in 1857 of the British Association at Dublin. At each angular point there are three and only three edges. Hence, if we approach a point by one edge, the only routes open to us are one to the right, denoted byr, and one to the left, denoted byl. It will be found that the operations indicated on opposite sides of the following equalities are equivalent, lr2l = rlr, rl 2r = lrl, lr 3l = r2, rl 3r = l2 . Also the operationl5 or r5 brings us back to the initial point: we may represent this by the equations l5 = 1, r 5 = 1 . To solve the problem for a figure having twenty angular points we must deduce a relation involving twenty successive operations, the total effect of which is equal to unity. By repeated use of the relation l2 = rl3r we see that 1 = l5 = l2l3 = (rl3r)l3 = {rl3}2 = {r(rl3r)l}2 = {r2l3rl}2 = {r2(rl3r)lrl}2 = {r3l3rlrl }2 . Therefore {r3l3(rl)2}2 = 1 ....... (i), and similarly {l3r3(lr)2}2 = 1 .......(ii).

PG26839.B00174
[PDF page 173] CH. VI] THE HAMILTONIAN GAME. 157 Hence on a dodecahedron either of the operations r r r l l l r l r l r r r l l l r l r l ....... (i), l l l r r r l r l r l l l r r r l r l r .......(ii), indicates a route which takes the traveller through every town, The arrangement is cyclical, and the route can be commenced at any point in the series of operations by transferring the proper number of letters from one end to the other. The point at which we begin is determined by the order of certain towns which is given initially. Thus, suppose that we are told that we start from F and then successively go to B, A, U, and T, and we want to find a route from T through all the remaining towns which will end atF. If we think of ourselves as coming intoF from G, the path F B would be indicated by l, but if we think of ourselves as coming intoF from E, the path F B would be indicated byr. The path fromB to A is indicated byl, and so on. Hence our first paths are indicated either byl l l r or by r l l r . The latter operation does not occur either in (i) or in (ii), and therefore does not fall within our solutions. The former operation may be regarded either as the1st, 2nd, 3rd, and 4th steps of (ii), or as the 4th, 5th, 6th, and7th steps of (i). Each of these leads to a route which satisfies the problem. These routes are F B A U T P O N C D E J K L M Q R S H G F , and F B A U T S R K L M Q P O N C D E J H G F . It is convenient to make a mark or to put down a counter at each corner as soon as it is reached, and this will prevent our passing through the same town twice. A similar game may be played with other solids provided that at each angular point three and only three edges meet. Of such solids a tetrahedron and a cube are the simplest instances, but the reader can make for himself any number of plane figures representing such solids similar to those drawn on the preceding page. Some of these were indicated by Hamilton. In all such cases we must obtain from the formulae analogous to those given above cyclical relations like (i) or (ii) there given. The solution will then follow the lines indicated above. This method may be used to form a rule for describing any maze in which no node is of an order higher than three.

PG26839.B00175
[PDF page 174] 158 UNICURSAL PROBLEMS. [CH. VI For solids having angular points where more than three edges meet—such as the octahedron where at each angular point four edges meet, or the icosahedron where at each angular point five edges meet— we should at each point have more than two routes open to us; hence (unless we suppress some of the edges) the symbolical notation would have to be extended before it could be applied to these solids. I offer the suggestion to anyone who is desirous of inventing a new game. Another and a very elegant solution of the Hamiltonian dodecahe- dron problem has been given by M. Hermary. It consists in unfolding the dodecahedron into its twelve pentagons, each of which is attached to the preceding one by only one of its sides; but the solution is geo- metrical, and not directly applicable to more complicated solids. Hamilton suggested as another problem to start from any town, to go to certain specified towns in an assigned order, then to go to every other town once and only once, and to end the journey at some given town. He also suggested the consideration of the way in which a certain number of towns should be blocked so that there was no passage through them, in order to produce certain effects. These problems have not, so far as I know, been subjected to mathematical analysis. Knight’s Path on a Chess-Board. Another geometrical problem on which a great deal of ingenuity has been expended, and of a kind somewhat similar to the Hamiltonian game, consists in moving a knight on a chess-board in such a manner that it shall move suc- cessively on to every cell* once and only once. The literature on this subject is so extensive†that I make no pretence to give a full account of the various methods for solving the problem, and I shall content myself by putting together a few notes on some of the solutions I have come across, particularly on those due to De Moivre, Euler, Vandermonde, Warnsdorff, and Roget. On a board containing an even number of cells the path may or may not be re-entrant, but on a board containing an odd number of * The 64 small squares into which a chess-board is divided are termedcells. † For a bibliography see A. van der Linde, Geschichte und Literatur des Schachspiels, Berlin, 1874, vol.ii, pp. 101–111. On the problem see a memoir by P. Volpicelli inAtti della Reale Accademia dei Lincei, Rome, 1872, vol.xxv, pp. 87–162: alsoApplications de l’Analyse Mathématique au Jeu des échecs, by C.F. de Jaenisch, 3 vols., St Petersburg, 1862–3; and General Parmentier, Association Française pour l’avancement des Sciences, 1891, 1892, 1894.

PG26839.B00176
[PDF page 175] CH. VI] KNIGHT’S PATH ON A CHESS-BOARD. 159 cells it cannot be re-entrant. For, if a knight begins on a white cell, its first move must take it to a black cell, the next to a white cell, and so on. Hence, if its path passes through all the cells, then on a board of an odd number of cells the last move must leave it on a cell of the same colour as that on which it started, and therefore these cells cannot be connected by one move. The earliest solutions of which I have any knowledge are those given about the end of the seventeenth century by De Montmort and De Moivre*. They apply to the ordinary chess-board of64 cells, and dependondividing(mentally)theboardintoaninnersquarecontaining sixteen cells surrounded by an outer ring of cells two deep. If initially the knight is placed on a cell in the outer ring, it moves round that ring always in the same direction so as to fill it up completely—only going into the inner square when absolutely necessary. When the outer ring is filled up the order of the moves required for filling the remaining cells presents but little difficulty. If initially the knight is placed on the inner square the process must be reversed. The method can be applied to square and rectangular boards of all sizes. It is illustrated sufficiently by De Moivre’s solution which is given below, where the 34 49 22 11 36 39 24 1 21 10 35 50 23 12 37 40 48 33 62 57 38 25 2 13 9 20 51 54 63 60 41 26 32 47 58 61 56 53 14 3 19 8 55 52 59 64 27 42 46 31 6 17 44 29 4 15 7 18 45 30 5 16 43 28 De Moivre’s Solution. 30 21 6 15 28 19 7 16 29 20 5 14 22 31 8 35 18 27 9 36 17 26 13 4 32 23 2 11 34 25 1 10 33 24 3 12 Euler’s Thirty-six Cell Solution. numbers indicate the order in which the cells are occupied successively. I place by its side a somewhat similar re-entrant solution, due to Euler, for a board of36 cells. If a chess-board is used it is convenient to place a counter on each cell as the knight leaves it. * I do not know where they were published originally; they were quoted by Ozanam and Montucla, see Ozanam, 1803 edition, vol.i, p. 178; 1840 edition, p. 80.

PG26839.B00177
[PDF page 176] 160 UNICURSAL PROBLEMS. [CH. VI The next serious attempt to deal with the subject was made by Eu- ler* in 1759: it was due to a suggestion made by L. Bertrand of Geneva, who subsequently (in 1778) issued an account of it. This method is ap- plicable to boards of any shape and size, but in general the solutions to which it leads are not symmetrical and their mutual connexion is not apparent. Euler commenced by moving the knight at random over the board until it has no move open to it. With care this will leave only a few cells not traversed: denote them by a, b, . . .. His method consists in establishingcertainrulesbywhichthesevacantcellscanbeinterpolated into various parts of the circuit, and also by which the circuit can be made re-entrant. The following example, mentioned by Legendre as one of excep- tional difficulty, illustrates the method. Suppose that we have formed 55 58 29 40 27 44 19 22 60 39 56 43 30 21 26 45 57 54 59 28 41 18 23 20 38 51 42 31 8 25 46 17 53 32 37 a 47 16 9 24 50 3 52 33 36 7 12 15 1 34 5 48 b 14 c 10 4 49 2 35 6 11 d 13 Figure i. 22 25 50 39 52 35 60 57 27 40 23 36 49 58 53 34 24 21 26 51 38 61 56 59 41 28 37 48 3 54 33 62 20 47 42 13 32 63 4 55 29 16 19 46 43 2 7 10 18 45 14 31 12 9 64 5 15 30 17 44 1 6 11 8 Figure ii. Example of Euler’s Method. the route given in figure i; namely,1, 2, 3, . . ., 59, 60; and that there are four cells left untraversed, namely,a, b, c, d. We begin by making the path1 to 60 re-entrant. The cell 1 com- mands a cell p, where p is 32, 52, or 2. The cell 60 commands a cell q, where q is 29, 59, or 51. Then, if any of these values of p and q differ by unity, we can make the route re-entrant. This is the case here if p = 52, q = 51. Thus the cells 1, 2, 3, . . . ,51; 60, 59, . . . ,52 form a * Mémoires de Berlin for 1759, Berlin, 1766, pp. 310–337; orCommentationes Arithmeticae Collectae, St Petersburg, 1849, vol.i, pp. 337–355.

PG26839.B00178
[PDF page 177] CH. VI] KNIGHT’S PATH ON A CHESS-BOARD. 161 re-entrant route of60 moves. Hence, if we replace the numbers60, 59, . . . ,52 by 52, 53, . . . ,60, the steps will be numbered consecutively. I recommend the reader who wishes to follow the subsequent details of Euler’s argument to construct this square on a piece of paper before proceeding further. Next, we add the cellsa, b, d to this route. In the new diagram of 60 cells formed as above the cella commands the cells there numbered 51, 53, 41, 25, 7, 5, and 3. It is indifferent which of these we select: suppose we take51. Then we must make51 the last cell of the route of 60 cells, so that we can continue witha, b, d. Hence, if the reader will add 9 to every number on the diagram he has constructed, and then replace 61, 62, . . . ,69 by 1, 2, . . . ,9, he will have a route which starts from the cell occupied originally by60, the 60th move is on to the cell occupied originally by 51, and the 61st, 62nd, 63rd moves will be on the cells a, b, d respectively. It remains to introduce the cellc. Since c commands the cell now numbered 25, and63 commands the cell now numbered24, this can be effected in the same way as the first route was made re-entrant. In fact the cells numbered 1, 2, . . . ,24; 63, 62, . . . ,25, c form a knight’s path. Hence we must replace 63, 62, . . . ,25 by the numbers 25, 26, . . . ,63, and then we can fill upc with 64. We have now a route which covers the whole board. Lastly, it remains to make this route re-entrant. First, we must get the cells 1 and 64 near one another. This can be effected thus. Take one of the cells commanded by1, such as28, then 28 commands 1 and 27. Hence the cells64, 63, . . . ,28; 1, 2, . . . ,27 form a route; and this will be represented in the diagram if we replace the cells numbered 1, 2, . . . ,27 by 27, 26, . . . ,1. The cell now occupied by1 commands the cells26, 38, 54, 12, 14, 16, 28; and the cell occupied by 64 commands the cells 13, 43, 63, 55. The cells 13 and 14 are consecutive, and therefore the cells64, 63, . . . ,14; 1, 2, . . . ,13 form a route. Hence we must replace the numbers 1, 2, . . . ,13 by 13, 12, . . . ,1, and we obtain a re-entrant route covering the whole board, which is represented in the second of the diagrams given on the facing page. Euler showed how seven other re-entrant routes can be deduced from any given re-entrant route. It is not difficult to apply the method so as to form a route which begins on one given cell and ends on any other given cell.

PG26839.B00179
[PDF page 178] 162 UNICURSAL PROBLEMS. [CH. VI Euler next investigated how his method could be modified so as to allow of the imposition of additional restrictions. An interesting example of this kind is where the first32 moves are confined to one half of the board. One solution of this is delineated below. The order of the first32 moves can be determined by Euler’s 58 43 60 37 52 41 62 35 49 46 57 42 61 36 53 40 44 59 48 51 38 55 34 63 47 50 45 56 33 64 39 54 22 7 32 1 24 13 18 15 31 2 23 6 19 16 27 12 8 21 4 29 10 25 14 17 3 30 9 20 5 28 11 26 Euler’s Half-board Solution. 50 45 62 41 60 39 54 35 63 42 51 48 53 36 57 38 46 49 44 61 40 59 34 55 43 64 47 52 33 56 37 58 26 5 24 1 20 15 32 11 23 2 27 8 29 12 17 14 6 25 4 21 16 19 10 31 3 22 7 28 9 30 13 18 Roget’s Half-board Solution. method. It is obvious that, if to the number of each such move we add 32, we shall have a corresponding set of moves from33 to 64 which wouldcovertheotherhalfoftheboard; butingeneralthecellnumbered 33 will not be a knight’s move from that numbered32, nor will64 be a knight’s move from1. Euler however proceeded to show how the first32 moves might be determined so that, if the half of the board containing the correspond- ing moves from33 to 64 was twisted through two right angles, the two routes would become united and re-entrant. Ifx and y are the num- bers of a cell reckoned from two consecutive sides of the board, we may call the cell whose distances are respectivelyx and y from the opposite sides a complementary cell. Thus the cells(x, y) and (9 − x, 9 − y) are complementary, wherex and y denote respectively the column and row occupied by the cell. Then in Euler’s solution the numbers in comple- mentary cells differ by32: for instance, the cell(3, 7) is complementary to the cell(6, 2), the one is occupied by57, the other by25. Roget’smethod, whichisdescribedlater, canbealsoappliedtogive half-board solutions. The result is indicated on this page. The close of Euler’s memoir is devoted to showing how the method could be applied to crosses and other rectangular figures. I may note in particular his elegant re-entrant symmetrical solution for a square of100 cells.

PG26839.B00180
[PDF page 179] CH. VI] KNIGHT’S PATH ON A CHESS-BOARD. 163 The next attempt of any special interest is due to Vandermonde*, who reduced the problem to arithmetic. His idea was to cover the board by two or more independent routes taken at random, and then to connect the routes. He defined the position of a cell by a fraction x/y, whose numeratorx is the number of the cell from one side of the board, and whose denominatory is its number from the adjacent side of the board; this is equivalent to saying thatx and y are the co-ordinates of a cell. In a series of fractions denoting a knight’s path, the differences between the numerators of two consecutive fractions can be only one or two, while the corresponding difference between their denominators must be two or one respectively. Alsox and y cannot be less than1 or greater than 8. The notation is convenient, but Vandermonde applied it merely to obtain a particular solution of the problem for a board of 64 cells: the method by which he effected this is analogous to that established by Euler, but it is applicable only to squares of an even order. The route that he arrives at is defined in his notation by the following fractions. 5 5, 4 3, 2 4, 4 5, 5 3, 7 4, 8 2, 6 1, 7 3, 8 1, 6 2, 8 3, 7 1, 5 2, 6 4, 8 5, 7 7, 5 8, 6 6, 5 4, 4 6, 2 5, 1 7, 3 8, 2 6, 1 8, 3 7, 1 6, 2 8, 4 7, 3 5, 1 4, 2 2, 4 1, 3 3, 1 2, 3 1, 2 3, 1 1, 3 2, 1 3, 2 1, 4 2, 3 4, 1 5, 2 7, 4 8, 3 6, 4 4, 5 6, 7 5, 8 7, 6 8, 7 6, 8 8, 6 7, 8 6, 7 8, 5 7, 6 5, 8 4, 7 2, 5 1, 6 3. The path is re-entrant but unsymmetrical. Had he transferred the first three fractions to the end of this series he would have obtained two symmetrical circuits of thirty-two moves joined unsymmetrically, and might have been enabled to advance further in the problem. Van- dermonde also considered the case of a route in a cube. In 1773 Collini† proposed the exclusive use of symmetrical routes arranged without reference to the initial cell, but connected in such a manner as to permit of our starting from it. This is the foundation of the modern manner of attacking the problem. The method was re- invented in 1825 by Pratt‡, and in 1840 by Roget, and has been subse- quently employed by various writers. Neither Collini nor Pratt showed skill in using this method. The rule given by Roget is described later. One of the most ingenious of the solutions of the knight’s path is * L’Histoire de l’Académie des Sciencesfor 1771, Paris, 1774, pp. 566-574. † Solution du Problème du Cavalier au Jeu des échecs, Mannheim, 1773. ‡ Studies of Chess, sixth edition, London, 1825.

PG26839.B00181
[PDF page 180] 164 UNICURSAL PROBLEMS. [CH. VI that given in 1823 by Warnsdorff*. His rule is that the knight must be moved always to one of the cells from which it will command the fewest squares not already traversed. The solution is not symmetrical and not re-entrant; moreover it is difficult to trace practically. The rule has not been proved to be true, but no exception to it is known: apparently it applies also to all rectangular boards which can be covered completely by a knight. It is somewhat curious that in most cases a single false step, except in the last three or four moves, will not affect the result. Warnsdorffaddedthatwhen, bytherule, twoormorecellsareopen to the knight, it may be moved to either or any of them indifferently. This is not so, and with great ingenuity two or three cases of failure have been constructed, but it would require exceptionally bad luck to happen accidentally on such a route. The above methods have been applied to boards of various shapes, especially to boards in the form of rectangles, crosses, and circles†. All the more recent investigations impose additional restrictions: such as to require that the route shall be re-entrant, or more generally that it shall begin and terminate on given cells. The best complete solution with which I am acquainted—and one which I believe is not generally known—is due to Roget‡. It divides the whole route into four circuits, which can be combined so as to enable us to begin on any cell and terminate on any other cell of a different colour. Hence, if we like to select this last cell at a knight’s move from the initial cell, we obtain a re-entrant route. On the other hand, the rule is applicable only to square boards containing(4n)2 cells: for example, it could not be used on the board of the Frenchjeu des dames, which contains 100 cells. Roget began by dividing the board of64 cells into four quarters. Each quarter contains 16 cells, and these 16 cells can be arranged in 4 groups, each group consisting of4 cells which form a closed knight’s path. All the cells in each such path are denoted by the same letter l, e, a, or p, as the case nay be. The path of4 cells indicated by the * Des Rösselsprunges einfachste und allgemeinste Lösung, Schmalkalden, 1823: see Jaenisch, vol.ii, pp. 56–61, 273–289. † See ex. gr.T. Ciccolini’s workDel Cavallo degli Scacchi, Paris, 1836. ‡ Philosophical Magazine, April, 1840, series 3, vol. xvi, pp. 305–309; see also the Quarterly Journal of Mathematics for 1877, vol. xiv, pp. 354–359. Some solutions, founded on Roget’s method, are given in theLeisure Hour, Sept. 13, 1873, pp. 587–590; see alsoIbid., Dec. 20, 1873, pp. 813–815.

PG26839.B00182
[PDF page 181] CH. VI] KNIGHT’S PATH ON A CHESS-BOARD. 165 consonants l and the path indicated by the consonantsp are diamond- shaped: the paths indicated respectively by the vowels e and a are square-shaped, as may be seen by looking at one of the four quarters in figure i below. l e a p l e a p a p l e a p l e e l p a e l p a p a e l p a e l l e a p l e a p a p l e a p l e e l p a e l p a p a e l p a e l Roget’s Solution(i). 34 51 32 15 38 53 18 3 31 14 35 52 17 2 39 54 50 33 16 29 56 37 4 19 13 30 49 36 1 20 55 40 48 63 28 9 44 57 22 5 27 12 45 64 21 8 41 58 62 47 10 25 60 43 6 23 11 26 61 46 7 24 59 42 Roget’s Solution(ii). Now all the16 cells on a complete chess-board which are marked with the same letter can be combined into one circuit, and wherever the circuit begins we can make it end on any other cell in the circuit, provided it is of a different colour to the initial cell. If it is indifferent on what cell the circuit terminates we may make the circuit re-entrant, and in this case we can make the direction of motion round each group (of 4 cells) the same. For example, all the cells markedp can be arranged in the circuit indicated by the successive numbers1 to 16 in figure ii above. Similarly all the cells markeda can be combined into the circuit indicated by the numbers17 to 23; all thel cells into the circuit33 to 48; and all the e cells into the circuit49 to 64. Each of the circuits indicated above is symmetrical and re-entrant. The consonant and the vowel circuits are said to be of opposite kinds. The general problem will be solved if we can combine the four circuits into a route which will start from any given cell, and terminate on the64th move on any other given cell of a different colour. To effect this Roget gave the two following rules. First. If the initial cell and the final cell are denoted the one by a consonant and the other by a vowel, take alternately circuits indicated by consonants and vowels, beginning with the circuit of16 cells indi- cated by the letter of the initial cell and concluding with the circuit indicated by the letter of the final cell.

PG26839.B00183
[PDF page 182] 166 UNICURSAL PROBLEMS. [CH. VI Second. If the initial cell and the final cell are denoted both by consonants or both by vowels, first select a cell,Y, in the same circuit as the final cell,Z, and one move from it, next select a cell,X, belonging to one of the opposite circuits and one move fromY. This is always possible. Then, leaving out the cellsZ and Y, it always will be possible, by the rule already given, to travel from the initial cell to the cellX in 62 moves, and thence to move to the final cell on the64th move. In both cases however it must be noticed that the cells in each of the first three circuits will have to be taken in such an order that the circuit does not terminate on a corner, and it may be desirable also that it should not terminate on any of the border cells. This will necessitate some caution. As far as is consistent with these restrictions it is convenient to make these circuits re-entrant, and to take them and every group in them in the same direction of rotation. As an example, suppose that we are to begin on the cell numbered 1 in figure ii on the previous page, which is one of those in ap circuit, and to terminate on the cell numbered64, which is one of those in an e circuit. This falls under the first rule: hence first we take the 16 cells marked p, next the16 cells marked a, then the16 cells marked l, and lastly the16 cells marked e. One way of effecting this is shown in the diagram. Since the cell64 is a knight’s move from the initial cell the route is re-entrant. Also each of the four circuits in the diagram is symmetrical, re-entrant, and taken in the same direction, and the only point where there is any apparent breach in the uniformity of the movement is in the passage from the cell numbered 32 to that numbered 33. A rule for re-entrant routes, similar to that of Roget, has been given by various subsequent writers, especially by De Polignac* and by Laquière†, who have stated it at much greater length. Neither of these authors seems to have been aware of Roget’s theorems. De Polignac, like Roget, illustrates the rule by assigning letters to the various squares in the way explained above, and asserts that a similar rule is applicable to all even squares. Roget’s method can be also applied to two half-boards, as indicated * Comptes Rendus, April, 1861; and Bulletin de la Société Mathématique de France, 1881, vol.ix, pp. 17–24. † Bulletin de la Société Mathématique de France, 1880, vol.viii, pp. 82–102, 132– 158.
