Mathematical Recreations and Essays · W. W. Rouse Ball
I propose to consider in this chapter some problems which arise out of the theory of unicursal curves. I shall commence with Euler's Problem and Theorems, and shall apply the results briefly to the theories of Mazes and Geometrical Trees. The reciprocal unicursal problems of the Hamilton Game and the Knight's Path on a Chess-board will be discussed in the latter half of the chapter.
Euler's problem
has its origin in a memoir (Solutio problematis ad Geometriam situs pertinentis, Commentarii Academiae Scientiarum Petropolitanae for 1736, St Petersburg, 1741, vol. viii, pp. 128--140. This has been translated into French by M. Ch. Henry; see Lucas, vol. i, part 2, pp. 21--33.) presented by him in 1736 to the St Petersburg Academy, in which he solved a question then under discussion as to whether it was possible to take a walk in the town of Königsberg in such a way as to cross every bridge in it once and only once.
The town is built near the mouth of the river Pregel, which there takes the form indicated [below]illus:185a and includes the
island of Kneiphof. In 1759 there were (and according to Baedeker there are still) seven bridges in the positions shown in the diagram, and it is easily seen that with such an arrangement the problem is insoluble. Euler however did not
confine himself to the case of Königsberg, but discussed the general problem of any number of islands connected in any way by bridges. It is evident that the question will not be affected if we suppose the islands to diminish to points and the bridges to lengthen out. In this way we ultimately obtain a geometrical figure or network. In the Königsberg problem this figure is of the shape indicated [below]illus:185b, the areas being represented by the points A , B , C , D , and the bridges being represented by the lines l , m , n , p , q , r , s.
Euler's problem consists therefore in finding whether a given geometrical figure can be described by a point moving so as to traverse every line in it once and only once. A more general question is to determine how many strokes are necessary to describe such a figure so that no line is traversed twice: this is covered by the rules hereafter given. The figure may be either in three or in two dimensions, and it may be represented by lines, straight, curved, or tortuous,
joining a number of given points, or a model may be constructed by taking a number of rods or pieces of string furnished at each end with a hook so as to allow of any number of them being connected together at one point.
The theory of such figures is included as a particular case in the propositions proved by Listing in his Topologie (Die Studien, Göttingen, 1847, part x. See also Tait on Listing's Topologie, Philosophical Magazine, London, January, 1884, series 5, vol. xvii, pp. 30--46.). I shall, however, adopt here the methods of Euler, and I shall begin by giving some definitions, as it will enable me to put the argument in a more concise form.
tocsubsectionDefinitions A node (or isle) is a point to or from which lines are drawn. A branch (or bridge or path) is a line connecting two consecutive nodes. An end (or hook) is the point at each termination of a branch. The order of a node is the number of branches which meet at it. A node to which only one branch is drawn is a free node or a free end. A node at which an even number of branches meet is an even node: evidently the presence of a node of the second order is immaterial. A node at which an odd number of branches meet is an odd node. A figure is closed if it has no free end: such a figure is often called a closed network.
A route consists of a number of branches taken in consecutive order and so that no branch is traversed twice. A closed route terminates at the point from which it started. A figure is described unicursally when the whole of it is traversed in one route.
tocsubsectionEuler's Theorems The following are Euler's results. (i) In a closed network the number of odd nodes is even. (ii) A figure which has no odd node can be described unicursally, in a re-entrant route, by a moving point which starts from any point on it. (iii) A figure which has two and only two odd notes can be described unicursally by a moving point which starts from one of the odd nodes and finishes at the other. (iv) A figure which has more than two odd nodes cannot be described
completely in one route; to which Listing added the corollary that a figure which has 2n odd nodes, and no more, can be described completely in n separate routes. I now proceed to prove these theorems.
First The number of odd nodes in a closed network is even.
Suppose the number of branches to be b. Therefore the number of hooks is 2b. Let k_n be the number of nodes of the n th order. Since a node of the n th order is one at which n branches meet, there are n hooks there. Also since the figure is closed, n cannot be less than 2. 0pt
Second A figure which has no odd node can be described unicursally in a re-entrant route.
Since the route is to be re-entrant it will make no difference where it commences. Suppose that we start from a node A. Every time our route takes us through a node we use up one hook in entering it and one in leaving it. There are no odd nodes, therefore the number of hooks at every node is even: hence, if we reach any node except A , we shall always find a hook which will take us into a branch previously untraversed. Hence the route will take us finally to the node A from which we started. If there are more than two hooks at A , we can continue the route over one of the branches from A previously untraversed, but in the same way as before we shall finally come back to A.
It remains to show that we can arrange our route so as to make it cover all the branches. Suppose each branch of the network to be represented by a string with a hook at each end, and that at each node all the hooks there are fastened together. The number of hooks at each node is even, and if
they are unfastened they can be re-coupled together in pairs, the arrangement of the pairs being immaterial. The whole network will then form one or more closed curves, since now each node consists merely of two ends hooked together.
If this random coupling gives us one single curve then the proposition is proved; for starting at any point we shall go along every branch and come back to the initial point. But if this random coupling produces anywhere an isolated loop, L , then where it touches some other loop, M , say at the node P , unfasten the four hooks there (viz. two of the loop L and two of the loop M ) and re-couple them in any other order: then the loop L will become a part of the loop M. In this way, by altering the couplings, we can transform gradually all the separate loops into parts of only one loop.
For example, take the case of three isles, A , B , C , each connected with both the others by two bridges. The most unfavourable way of re-coupling the ends at A , B , C would be to make ABA , ACA , and BCB separate loops. The loops ABA and ACA are separate and touch at A ; hence we should re-couple the hooks at A so as to combine ABA and ACA into
one loop ABACA. Similarly, by re-arranging the couplings of the four hooks at B , we can combine the loop BCB with ABACA and thus make only one loop.
I infer from Euler's language that he had attempted to solve the problem of giving a practical rule which would enable one to describe such a figure unicursally without knowledge of
its form, but that in this he was unsuccessful. He however added that any geometrical figure can be described completely in a single route provided each part of it is described twice and only twice, for, if we suppose that every branch is duplicated, there will be no odd nodes and the figure is unicursal. In this case any figure can be described completely without knowing its form: rules to effect this are given below.
Third A figure which has two and only two odd nodes can be described unicursally by a point which starts from one of the odd nodes and finishes at the other odd node.
This at once reduces to the second theorem. Let A and Z be the two odd nodes. First, suppose that Z is not a free end. We can, of course, take a route from A to Z ; if we imagine the branches in this route to be eliminated, it will remove one hook from A and make it even, will remove two hooks from every node intermediate between A and Z and therefore leave each of them even, and will remove one hook from Z and therefore will make it even. All the remaining network is now even: hence, by Euler's second proposition, it can be described unicursally, and, if the route begins at Z , it will end at Z. Hence, if these two routes are taken in succession, the whole figure will be described unicursally, beginning at A and ending at Z. Second, if Z is a free end, then we must travel from Z to some node, Y , at which more than two branches meet. Then a route from A to Y which covers the whole figure exclusive of the path from Y to Z can be determined as before and must be finished by travelling from Y to Z.
Fourth A figure having 2n odd nodes, and no more, can be described completely in n separate routes.
If any route starts at an odd node, and if it is continued until it reaches a node where no fresh path is open to it, this latter node must be an odd one. For every time we enter an even node there is necessarily a way out of it; and similarly every time we go through an odd node we use up one hook in entering and one hook in leaving, but whenever we reach it as
the end of our route we use only one hook. If this route is suppressed there will remain a figure with 2n-2 odd nodes. Hence n such routes will leave one or more networks with only even nodes. But each of these must have some node common to one of the routes already taken and therefore can be described as a part of that route. Hence the complete passage will require n and not more than n routes. It follows, as stated by Euler, that, if there are more than two odd nodes, the figure cannot be traversed completely in one route.
tocsubsectionExamples The Königsberg bridges lead to a network with four odd nodes; hence, by Euler's fourth proposition, it cannot be described unicursally in a single journey, though it can be traversed completely in two separate routes.
The first and second diagrams figured [below]illus:190 contain only even nodes, and therefore each of them can be described unicursally.
The first of these--a re-entrant pentagon--was one of the Pythagorean symbols. The other is the so-called sign-manual of Mohammed, said to have been originally traced in the sand by the point of his scimetar without taking the scimetar off the ground or retracing any part of the figure--which, as it contains only even nodes, is possible. The third diagram is taken from Tait's article: it contains only two odd nodes, and therefore can be described unicursally if we start from one of them and finish at the other.
As other examples I may note that the geometrical figure
formed by taking a (2n+1) gon and joining every angular point with every other angular point is unicursal. On the other hand a chess-board, divided as usual by straight lines into 64 cells, has 28 odd nodes and 53 even nodes: hence it would require 14 separate pen-strokes to trace out all the boundaries without going over any more than once. Again, the diagram on page has 20 odd nodes and therefore would require 10 separate pen-strokes to trace it out.
It is well known that a curve which has as many nodes as is consistent with its degree is unicursal.
[Mazes][Mazes and Labyrinths.]Mazes Everyone has read of the labyrinth of Minos in Crete and of Rosamund's Bower. A few modern mazes exist here and there--notably one, which is a very poor specimen of its kind, at Hampton Court--and in one of these, or at any rate on a drawing of one, most of us have threaded our way to the interior. I proceed now to consider the manner in which any such construction may be completely traversed even by one who is ignorant of its plan.
The theory of the description of mazes is included in Euler's theorems given above. The paths in the maze are what previously we have termed branches, and the places where two or more paths meet are nodes. The entrance to the maze, the end of a blind alley, and the centre of the maze are free ends and therefore odd nodes.
If the only odd nodes are the entrance to the maze and the centre of it--which will necessitate the absence of all blind alleys--the maze can be described unicursally. This follows from Euler's third proposition. Again, no matter how many odd nodes there may be in a maze, we can always find a route which will take us from the entrance to the centre without retracing our steps, though such a route will take us through only a part of the maze. But in neither of the cases mentioned in this paragraph can the route be determined without a plan of the maze.
A plan is not necessary, however, if we make use of
Euler's suggestion, and suppose that every path in the maze is duplicated. In this case we can give definite rules for the complete description of the whole of any maze, even if we are entirely ignorant of its plan. Of course to walk twice over every path in a labyrinth is not the shortest way of arriving at the centre, but, if it is performed correctly, the whole maze is traversed, the arrival at the centre at some point in the course of the route is certain, and it is impossible to lose one's way.
tocsubsectionRules for completely traversing a Maze I need hardly explain why the complete description of such a duplicated maze is possible, for now every node is even, and hence, by Euler's second proposition, if we begin at the entrance we can traverse the whole maze; in so doing we shall at some point arrive at the centre, and finally shall emerge at the point from which we started. This description will require us to go over every path in the maze twice, and as a matter of fact the two passages along any path will be always made in opposite directions.
If a maze is traced on paper, the way to the centre is generally obvious, but in an actual labyrinth it is not so easy to find the correct route unless the plan is known. In order to make sure of describing a maze without knowing its plan it is necessary to have some means of marking the paths which we traverse and the direction in which we have traversed them--for example, by drawing an arrow at the entrance and end of every path traversed, or better perhaps by marking the wall on the right-hand side, in which case a path may not be entered when there is a mark on each side of it. If we can do this, and if when a node is reached, we take, if it be possible, some path not previously used, or, if no other path is available, we enter on a path already traversed once only, we shall completely traverse any maze in two dimensions (See Le problème des labyrinthes by G. Tarry, Nouvelles Annales de math-é-mat-iques, May, 1895, series 3, vol. xiv.). Of course a path must not be traversed twice in the same direction, a
path already traversed twice (namely, once in each direction) must not be entered, and at the end of a blind alley it is necessary to turn back along the path by which it was reached.
tocsubsectionNotes on the History of Mazes I think most people would understand by a maze a series of interlacing paths through which some route can be obtained leading to a space or building at the centre of the maze. I believe that few, if any, mazes of this type existed in classical or medieval times.
One class of what the ancients called mazes or labyrinths seems to have comprised any complicated building with numerous vaults and passages (For instance, see the descriptions of the labyrinth at Lake Moeris given by Herodotus, bk. ii, c. 148; Strabo, bk. xvii, c. 1, art. 37; Diodorus, bk. i, cc. 61, 66; and Pliny, Hist. Nat., bk. xxxvi, c. 13, arts. 84--89. On these and other references see A. Wiedemann, Herodots zweites Buch, Leipzig, 1890, p. 522 See also Virgil, Aeneid, bk. v, c. v, 588; Ovid, Met., bk. viii, c. 5, 159; Strabo, bk. viii, c. 6.). Such a building might be termed a labyrinth, but it is not what is usually understood by the word. The above rules would enable anyone to traverse the whole of any structure of this kind. I do not know if there are any accounts or descriptions of Rosamund's Bower other than those by Drayton, Bromton, and Knyghton: in the opinion of some, these imply that the bower was merely a house, the passages in which were confusing and ill-arranged.
Another class of ancient mazes consisted of a tortuous path confined to a small area of ground and leading to a place or shrine in the centre (On ancient and medieval labyrinths--particularly of this kind--see an article by Mr E. Trollope in The Archaeological Journal, 1858, vol. xv, pp. 216--235, from which much of the historical information given above is derived). This is a maze in which there is no chance of taking a wrong turning; but, as the whole area can be occupied by the windings of one path, the distance to be traversed from the entrance to the centre may be considerable, even though the piece of ground covered by the maze is but small.
The traditional form of the labyrinth constructed for the Minotaur is a specimen of this class. It was delineated on the reverses of the coins of Cnossus, specimens of which are not uncommon; one form of it is indicated in the [accompanying diagram][diagram ]illus:194 (figure i). The design really is the same as that drawn in figure ii, as can be easily seen by bending round a circle the rectangular figure there given.
Mr Inwards has suggested (Knowledge, London, October, 1892.) that this design on the coins of Cnossus may be a survival from that on a token given by
the priests as a clue to the right path in the labyrinth there. Taking the circular form of the design shown above he supposed each circular wall to be replaced by two equidistant walls separated by a path, and thus obtained a maze to which the original design would serve as the key. The route thus indicated may be at once obtained by noticing that when a node is reached ( a point where there is a choice of paths) the path to be taken is that which is next but one to that by which the node was approached. This maze may be also threaded by the simple rule of always following the wall on the right-hand side or always that on the left-hand side. The labyrinth may be somewhat improved by erecting a few additional barriers, without affecting the applicability of the above rules, but it cannot be made really difficult. This makes a pretty toy, but though the conjecture on which it is founded is ingenious it must be regarded as exceedingly
improbable. Another suggestion is that the curved line on the reverse of the coins indicated the form of the rope held by those taking part in some rhythmic dance; while others consider that the form was gradually evolved from the widely prevalent svastika.
Copies of the maze of Cnossus were frequently engraved on Greek and Roman gems; similar but more elaborate designs are found in numerous Roman mosaic pavements (See Breton's Pompeia, p. 303.). A copy of the Cretan labyrinth was embroidered on many of the state robes of the later Emperors, and, apparently thence, was copied on to the walls and floors of various churches (Ozanam, Graphia aureae urbis Romae, pp. 92, 178.). At a later time in Italy and in France these mural and pavement decorations were developed into scrolls of great complexity, but consisting, as far as I know, always of a single line. Some of the best specimens now extant are on the walls of the cathedrals at Lucca, Aix in Provence, and Poitiers; and on the floors of the churches of Santa Maria in Trastevere at Rome, San Vitale at Ravenna, Notre Dame at St Omer, and the cathedral at Chartres. It is possible that they were used to represent the journey through life as a kind of pilgrim's progress.
In England these mazes were usually, perhaps always, cut in the turf adjacent to some religious house or hermitage: and there are some slight reasons for thinking that, when traversed as a religious exercise, a pater or ave had to be repeated at every turning. After the Renaissance, such labyrinths were frequently termed Troy-towns or Julian's bowers. Some of the best specimens, which are still extant, are those at Rockliff Marshes, Cumberland; Asenby, Yorkshire; Alkborough, Lincolnshire; Wing, Rutlandshire; Boughton-Green, Northamptonshire; Comberton, Cambridgeshire; Saffron Walden, Essex; and Chilcombe, near Winchester.
The modern maze seems to have been introduced--probably from Italy--during the Renaissance, and many of the
palaces and large houses built in England during the Tudor and the Stuart periods had labyrinths attached to them. Those adjoining the royal palaces at Southwark, Greenwich, and Hampton Court were particularly well known from their vicinity to the capital. The last of these was designed by London and Wise in 1690, for William III, who had a fancy for such conceits: a plan of it is given in various guide-books.
For the majority of the sight-seers who enter, it is sufficiently elaborate; but it is an indifferent construction, for it can be described completely by always following the hedge on one side (either the right hand or the left hand), and no node is of an order higher than three.
Unless at some point the route to the centre forks and subsequently the two forks reunite, forming a loop in which the centre of the maze is situated, the centre can be reached by the rule just given, namely, by following the wall on one side--either on the right hand or on the left hand. No labyrinth is worthy of the name of a puzzle which can be threaded in this way. Assuming that the path forks as described above, the more numerous the nodes and the higher their order the more difficult will be the maze, and the difficulty might be increased considerably by using bridges and tunnels so as to construct a labyrinth in three dimensions. In an ordinary garden and on a small piece of ground, often
of an inconvenient shape, it is not easy to make a maze which fulfils these conditions. [Here][Here ]illus:197 is a plan of one which I put up
in my own garden on a plot of ground which would not allow of more than 36 by 23 paths, but it will be noticed that none of the nodes are of a high order.
Euler's original investigations were confined to a closed network. In the problem of the maze it was assumed that there might be any number of blind alleys in it, the ends of which formed free nodes. We may now progress one step farther, and suppose that the network or closed part of the figure diminishes to a point. This last arrangement is known as a tree. The number of unicursal descriptions necessary to completely describe a tree is called the base of the ramification.
We can illustrate the possible form of these trees by rods, having a hook at each end. Starting with one such rod, we can attach at either end one or more similar rods. Again, on any free hook we can attach one or more similar rods, and so on. Every free hook, and also every point where two
or more rods meet, are what hitherto we have called nodes. The rods are what hitherto we have termed branches or paths.
The theory of trees--which already plays a somewhat important part in certain branches of modern analysis, and possibly may contain the key to certain chemical and biological theories--originated in a memoir by Cayley (Philosophical Magazine, March, 1857, series 4, vol. xiii, pp. 172--176; or Collected Works, Cambridge, 1890, vol. iii, no. 203, pp. 242--346: see also the paper on double partitions, Philosophical Magazine, November, 1860, series 4, vol. xx, pp. 337--341. On the number of trees with a given number of nodes, see the Quarterly Journal of Mathematics, London, 1889, vol. xxiii, pp. 376--378. The connection with chemistry was first pointed out in Cayley's paper on isomers, Philosophical Magazine, June, 1874, series 4, vol. xlvii, pp. 444--447, and was treated more fully in his report on trees to the British Association in 1875, Reports, pp. 257--305.), written in 1856. The discussion of the theory has been analytical rather than geometrical. I content myself with noting the following results.
The number of trees with n given nodes is n^(n-2). If A_n is the number of trees with n branches, and B_n the number of trees with n free branches which are bifurcations at least, then (1-x)^-1 (1-x^2)^(-A_1) (1-x^3)^(-A_2) = 1 + A_1 x + A_2 x^2 + A_3 x^3 +...,; (1-x)^-1 (1-x^2)^(-B_2) (1-x^3)^(-B_3) = 1 + x + 2B_2 x^2 + 2B_3 x^3 +.... Using these formulae we can find successively the values of A_1,A_2... , and B_1,B_2.... The values of A_n when n = 2 , 3 , 4 , 5 , 6 , 7 , are 2 , 4 , 9 , 20 , 48 , 115 ; and of B_n are 1 , 2 , 5 , 12 , 33 , 90.
I turn next to consider some problems where it is desired to find a route which will pass once and only once through each node of a given geometrical figure. This is the reciprocal of the problem treated in the first part of this chapter, and is a far more difficult question. I am not aware that the general theory has been considered by mathematicians, though two
special cases--namely, the Hamiltonian (or Icosian) Game and the Knight's Path on a Chess-Board--have been treated in some detail; and I confine myself to a discussion of these.
The Hamiltonian Game
consists in the determination of a route along the edges of a regular dodecahedron which will pass once and only once through every angular point. Sir William Hamilton (See Quarterly Journal of Mathematics, London, 1862, vol. v, p. 305; or Philosophical Magazine, January, 1884, series 5, vol. xvii, p. 42; also Lucas, vol. ii, part vii.), who invented this game--if game is the right term for it--denoted the twenty angular points on the solid by letters which stand for various towns. The thirty edges constitute the only possible paths. The inconvenience of using a solid is considerable, and the dodecahedron may be represented conveniently in perspective by a flat board marked as shown in the first of the annexed diagrams. The second and third diagrams will answer our purpose equally well and are easier to draw.
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 the n 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 by r , and one to the left, denoted by l. It will be found that the operations indicated on opposite sides of the following equalities are equivalent, lr^2l = rlr, rl^2r = lrl, lr^3l=r^2, rl^3r=l^2. Also the operation l^5 or r^5 brings us back to the initial point: we may represent this by the equations l^5=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 l^2 = rl^3r we see that 1=l^5=l^2l^3=(rl^3r)l^3 ={rl^3}^2={r(rl^3r)l}^2; ={r^2l^3rl}^2={r^2(rl^3r)lrl}^2={r^3l^3rlrl}^2.; Therefore {r^3l^3(rl)^2}^2=1 to2cm(i),; and similarly {l^3r^3(lr)^2}^2=1 to2cm(ii).; 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 li; l l l r r r l r l r l l l r r r l r l rii 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 at F. If we think of ourselves as coming into F from G , the path FB would be indicated by l , but if we think of ourselves as coming into F from E , the path FB would be indicated by r. The path from B to A is indicated by l , and so on. Hence our first paths are indicated either by l;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 the 1 st, 2 nd, 3 rd, and 4 th steps of (ii), or as the 4 th, 5 th, 6 th, and 7 th 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 illus:199. 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.
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 dodecahedron 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 geometrical, 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
.
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 successively on to every cell (The 64 small squares into which a chess-board is divided are termed cells.) once and only once. The literature on this subject is so extensive (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 in Atti della Reale Accademia dei Lincei, Rome, 1872, vol. xxv, pp. 87--162: also Applications 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.) 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 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.
tocsubsectionMethod of De Montmort and De Moivre 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 (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.). They apply to the ordinary chess-board of 64 cells, and depend on dividing (mentally) the board into an inner square containing 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]DeMoivre,
where the 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 of
36 cells. If a chess-board is used it is convenient to place a counter on each cell as the knight leaves it.
tocsubsectionMethod of Euler The next serious attempt to deal with the subject was made by Euler (Mémoires de Berlin for 1759, Berlin, 1766, pp. 310--337; or Commentationes Arithmeticae Collectae, St Petersburg, 1849, vol. i, pp. 337--355.) 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 applicable 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 establishing certain rules by which these vacant cells can be interpolated 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 exceptional difficulty, illustrates the method. Suppose that we
have formed the route given in Euler:ifigure 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 path 1 to 60 re-entrant. The
cell 1 commands 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 re-entrant route of 60 moves. Hence, if we replace the numbers 60, 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 cells a , b , d to this route. In the new diagram of 60 cells formed as above the cell a commands the cells there numbered 51 , 53 , 41 , 25 , 7 , 5 , and 3. It is indifferent which of these we select: suppose we take 51. Then we must make 51 the last cell of the route of 60 cells, so that we can continue with a , 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 by 60 , the 60 th move is on to the cell occupied originally by 51 , and the 61 st, 62 nd, 63 rd moves will be on the cells a , b , d respectively.
It remains to introduce the cell c. Since c commands the cell now numbered 25 , and 63 commands the cell now numbered 24 , 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 up c 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 by 1 , such as 28 , then 28 commands 1 and 27. Hence the cells 64, 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 by 1 commands the cells 26 , 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 cells 64, 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 Euler:i. 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.
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 first 32 moves are confined to one half of the board. One solution of this is delineated [below]figure:Roget. The order of the first 32 moves
can be determined by Euler's method. It is obvious that, if to the number of each such move we add 32 , we shall have a corresponding set of moves from 33 to 64 which would cover the other half of the board; but in general the cell numbered 33 will not be a knight's move from that numbered 32 , nor will 64 be a knight's move from 1.
Euler however proceeded to show how the first 32 moves might be determined so that, if the half of the board containing the corresponding moves from 33 to 64 was twisted through two right angles, the two routes would become united and re-entrant. If x and y are the numbers of a cell reckoned from two consecutive sides of the board, we may call the cell whose distances are respectively x and y from the opposite sides a complementary cell. Thus the cells (x, y) and (9-x, 9-y) are complementary, where x and y denote respectively the column and row occupied by the cell. Then in Euler's solution the numbers in complementary cells differ by 32 : for instance, the cell (3, 7) is complementary to the cell (6, 2) , the one is occupied by 57 , the other by 25.
Roget's method, which is described later, can be also applied to give half-board solutions. The result is indicated figure:Roget. 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 of 100 cells.
tocsubsectionMethod of Vandermonde The next attempt of any special interest is due to Vandermonde (L'Histoire de l'Académie des Sciences for 1771, Paris, 1774, pp. 566-574.), 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 numerator x is the number of the cell from one side of the board, and whose denominator y is its number from the adjacent side of the board; this is equivalent to saying that x 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. Also x and y cannot be less than 1 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.
=1.5 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. Vandermonde also considered the case of a route in a cube.
In 1773 Collini (Solution du Problème du Cavalier au Jeu des échecs, Mannheim, 1773.) 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 (Studies of Chess, sixth edition, London, 1825.), and in 1840 by Roget, and has been subsequently employed by various writers. Neither Collini nor Pratt showed skill in using this method. The rule given by Roget is described later.
tocsubsectionMethod of Warnsdorff One of the most ingenious of the solutions of the knight's path is that given in 1823 by Warnsdorff (Des Rösselsprunges einfachste und allgemeinste Lösung, Schmalkalden, 1823: see Jaenisch, vol. ii, pp. 56--61, 273--289.). 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.
Warnsdorff added that when, by the rule, two or more cells are open 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 (See T. Ciccolini's work Del Cavallo degli Scacchi, Paris, 1836.).
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.
tocsubsectionMethod of Roget The best complete solution with which I am acquainted--and one which I believe is not generally known--is due to Roget (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 the Leisure Hour, Sept. 13, 1873, pp. 587--590; see also , Dec. 20, 1873, pp. 813--815.). 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 French jeu des dames, which contains 100 cells.
Roget began by dividing the board of 64 cells into four quarters. Each quarter contains 16 cells, and these 16 cells can be arranged in 4 groups, each group consisting of 4 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 of 4 cells indicated by the consonants l and the path indicated by the consonants p 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]Roget:i.
Now all the 16 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 marked p can be arranged in the circuit indicated by the successive numbers 1 to 16 in figure ii [above]Roget:i. Similarly all the cells marked a can be combined into the circuit indicated by the numbers 17 to 23 ; all the l cells into the circuit 33 to 48 ; and all the e cells into the circuit 49 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 the 64 th 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 of 16 cells indicated by the letter of the initial cell and concluding with the circuit indicated by the letter of the final cell.
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 from Y. This is always possible. Then, leaving out the cells Z and Y , it always will be possible, by the rule already given, to travel from the initial cell to the cell X in 62 moves, and thence to move to the final cell on the 64 th 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 Roget:i, which is one of those in a p circuit, and to terminate on the cell numbered 64 , 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 the 16 cells marked a , then the 16 cells marked l , and lastly the 16 cells marked e. One way of effecting this is shown in the diagram. Since the cell 64 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 (Comptes Rendus, April, 1861; and Bulletin de la Société Mathématique de France, 1881, vol. ix, pp. 17--24.) and by Laquière (Bulletin de la Société Mathématique de France, 1880, vol. viii, pp. 82--102, 132--158.), 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 in the figure given above on page.
tocsubsectionMethod of Moon Another way of dividing the board into closed circuits which can be connected was given in 1843 by Moon (Cambridge Mathematical Journal, 1843, vol. iii, pp. 233--236.). He
divided the board into a central square containing 4^2 cells and a surrounding annulus (see figure Jaenisch). The annulus may be
divided into four closed circuits, each containing 12 cells: these are marked respectively with the letters a , b , c , d. The central square may be divided similarly into four closed circuits, each containing 4 cells, denoted by the letters A , B , C , D. We can connect these routes as follows. If we are moving outwards from the central square to the annulus we can go from a cell A either to b or to c or to d (but not to a ) and similarly for the other letters. If we are moving inwards from the annulus to the central square we must go from a to D , or d to A , or b to C , or c to B , as the case may be. Thus if the initial cell is on a , we might take either of the cycles a D b C d A c B , or a D c B d A b C. By following these rules we always can connect the routes into one path, but in general it will not be re-entrant. It is convenient to take the cells in each circuit in one and the same direction, but a circuit in the outer annulus must not end in a corner cell, and to avoid this we may have to alter the direction in which a circuit is taken.
Moon's rule can be modified to cover the case of any doubly even square board, and the path can be made to begin and end on any two given squares, but I do not propose to go further into details.
tocsubsectionMethod of Jaenisch The method which Jaenisch gives as the most fundamental is not very different from that of Roget. It leads to eight forms, similar to that in the diagram printed Jaenisch, in which the sum of the numbers in every column and every row is 260 ; but although symmetrical it is not in my opinion so easy to reproduce as that given by Roget.
tocsubsectionNumber of possible routes It is as yet impossible to say how many solutions of the problem exist. Legendre (Théorie des Nombres, Paris, 2nd edition, 1830, vol. ii, p. 165.) mentioned the question, but Minding (Cambridge and Dublin Mathematical Journal, 1852, vol. vii, pp. 147--156; and Crelle's Journal, 1853, vol. xliv, pp. 73--82.) was the earliest writer to attempt to answer it. More recent investigations have shown that on the one hand the number of possible routes is less (Jaenisch, vol. ii, p. 268.) than the number of
combinations of 168 things taken 63 at a time, and on the other hand is greater than 31,054144 --since this latter number is the number of re-entrant paths of a particular type (Bulletin de la Société Mathématique de France, 1881, vol. ix, pp. 1--17.).
Paths of other Chess-Pieces There are many similar problems in which it is required to determine routes by which a piece moving according to certain laws ( a chess-piece such as a king, knight, &c.) can travel from a given cell over a board so as to occupy successively all the cells, or certain specified cells, once and only once, and terminate its route in a given cell.
Euler's method can be applied to find routes of this kind: for instance, he applied it to find a re-entrant route by which a piece that moved two cells forward like a castle and then one cell like a bishop would occupy in succession all the black cells on the board. As another instance, a castle, placed on a chess-board of n^2 cells, can always be moved in such a manner that it shall move successively on to every cell once and only once; moreover, starting on any cell, its path can be made to terminate, if n be even, on any other cell of a different colour, and, if n be odd, on any other cell of the same colour (L'Intermédiaire des mathématiciens, Paris, July, 1901, p. 153.). But it will suffice to have discussed the classical problem of the determination of a knight's path on an ordinary chess-board, and I need not enter on the discussion of other similar problems
.
"No man of science should think it a waste of time to learn something of the history of his own subject; nor is the investigation of laborious methods now fallen into disuse, or of errors once commonly accepted the least valuable of mental disciplines."
"The most worthless book of a bygone day is a record worthy of preservation. Like a telescopic star, its obscurity may render it unavailable for most purposes; but it serves, in hands which know how to use it, to determine the places of more important bodies." -100 (De Morgan.)
toc
· · ·
End of part 8 of 16
Continue readingChapter VII: The Mathematical Tripos
Starvard