CM. V]

MECHANICAL RECKEATiOiNb
99
long as its component normal to the sail is less than the pressure of the wind behind the sail and normal to it, the resultant of the two will be a force behind the sail and normal to it which tends to drive the boat forwards. But as the velocity of the boat increases, a time will arrive when the pressure of the wind is only just able to balance the resisting force which is caused by the sail moving throingh the air. The velocity of the boat will not increase beyond this, and the motion will be then what mathematicians describe as ''steady."
In the accompanying figure, let BAR represent the keel of a boat, B being the bow, and let SAL represent the sail. Suppose that the wind is blov/ing in the direction WA with a velocity u; and that this direction makes an angle 6 with the keel, i.e. angle V, A R= 6. Suppose that the sail is set so as to make an angle a with the keel, i.e. angle BAS = a, and therefore angle WAL = 6 -\- a. Suppose finally that v is the velocity of the boat in the direction AB.
I have already shown that the solution of the problem depends on the relative directions and velocities of the wind and the boat; hence to find the result reduce the boat to rest by impressing on it a velocity v in the direction BA. The resultant velocity of v parallel to BA and of u parallel to WA will be parallel to SL, if v sin a = w sin (^ + a) ; and in this case the resultant pressure perpendicular to the sail vaoishes.
Thus, for steady motion we have v sin a = t( sin (0 + a). Hence, whenever sin (^+ a) > sin a, we have v > u. Suppose,
7—2
100
MECHANICAL RECREATIONS
[CH. V
to take one instance, the sail to be tixed, that is, suppose a to be a constant. Then ?; is a maximum if ^ + a = Jtt, that is, if 0 is equal to the complement of o.. In this case we have i} — xi cosec a, and therefore v is greater than u. Hence, if the wind makes the same angle a abaft the beam that the sail makes with the keel, the velocity of the boat will be greater than the velocity of the wind.
Next, suppose that the boat is running close to the wind, so that the wind is before the beam (see figure below), then in the same way as before we have v sin ol — u sin {6 + a), or V sin o. — u sin 6, where = angle ^VAS = 17— 0 — a. Hence v=u sin
Let w be the component velocity of the boat in the teeth of the wind, that is, in the direction A W. Then we have w = v cos BA W = V cos {a+ is constant, this is a maximum when (f> = lir — ^a; and, if (j> has this value, then w = -^u {cosec a— 1). This formula shows that w is greater than u, if sin a can be set so that a is less than sin~^J, that is, rather less than 19° 29', and if the wind has the direction above assigned, then the component velocity of the boat in the face of the wind is greater than the velocity of the wind.
The above theory is curious, but it must be remembered that in practice considerable allowance has to be made for the fact that no boat for use on water can be constructed in which the resistance to motion in the direction of the keel can be wholly neglected, or which would not drift slightly to leeward if the wind was not dead astern Still this makes less
CH. V] MECHANICAL RECREATIONS ICl
difference than might be thouglit by a landsman. In the case of boats sailing on smooth ice the assumptions made are sub- stantially correct, and the practical results are said to agree closely with the theory.
Boat moved by a Rope. There is a form of boat-racing, occasionally used at reg.'ittas, which affords a somewhat curious illustration of certain mechanical principles. The only thing supplied to the cre^v is a coil of rope, and they have, without leaving the boat, to propel it from one point to another as rapidly as possible. The motion is given by tying one end of the rope to the after thwart, and giving the other end a series of violent jerks in a direction parallel to the keel. I am told that in still water a pace of two or three miles an hour can be thus attained.
The chief cause for this result seems to be that the friction between the boat and the water retards all relative motion, but it is not great enough to affect materially motion caused by a sufficiently big impulse. Hence the usual movements of the crew in the boat do not sensibly move the centre of gravity of themselves and the boat, but this does not apply to an impul- sive movement, and if the crew in making a jerk move their centre of gravity towards the bow n times more rapidly than it returns after the jerk, then the boat is impelled forwards at least n times more than backwards : hence on the whole the motion is forwards.
Motion of Fluids and Motion in Fluids. The theories of motion of fluids and motion in fluids involve considerable difficulties. Here I will mention only one or two instances — mainly illustrations of Hauksbee's Law.
Haiihshees Law. When a fluid is in motion the pressure is less than when it is at rest*. Thus, if a current of air is
* See BesJint, Hydromechanics, Cambridge, 18G7, art. 119, where however it is assumed that the pressure is proportional to the density. Hauksbee was the earliest writer who called attention to the problem, but I do not know who first explained the phenomenon; some references to it are given by Willis, Camhridije PhilowpJdcal Traiiaactiona, 1830, vol. in, pp. 129 — 140.
102 MECHANICAL RECREATIONS [CH. V
moving in a tube, the pressure on the sides of the tube is less than when the air is at rest — and the quicker the air moves the smaller is the pressure. This fact was noticed by Hauksbee nearly two centuries ago. In an elastic perfect fluid in which the pressure is proportional to the density, the law connecting the pressure, 'p, and the steady velocity, v, is ^ = Tla"'^, where n and a are constants : the establishment of the corresponding formula for gases where the pressure is proportional to a power of the density presents no difficulty.
The principle is illustrated by a twopenny toy, on sale in most toy-shops, called the pneumatic mystery. This consists of a tube, with a cup-shaped end in which rests a wooden ball. If the tube is held in a vertical position, with the mouthpiece at the upper end and the cup at the lower end, then, if anyone blows hard through the tube and places the ball against the cup, the ball will remain suspended there. The explanation is that the pressure of the air below the ball is so much greater than the pressure of the air in the cup that the ball is held up.
The same effect may be produced by fastening to one end of a tube a piece of cardboard having a small hole in it. If a piece of paper is placed over the hole and the experimenter blows through the tube, the paper will not be detached from the card but will bend so as to allow the egress of the air.
An exactly similar experiment, described in many text- books on hydromechanics, is made as follows. To one end of a straight tube a plane disc is fitted which is capable of sliding on wires projecting from the end of the tube. If the disc is placed at a small distance from the end, and anyone blows steadily into the tube, the disc will be drawn towards the tube instead of being blown off the wires, and will oscillate about a position near the end of the tube.
In the same way we may make a tube by placing two books on a table with their backs parallel and an inch or so apart and laying a sheet of newspaper over them. If anyone blows steadily through the tube so formed, the paper will be sucked in instead of being blown out.
CH. V] MECHANiCAL RECREATIONS 103
The following experimeQt is explicable by the same aigii- ment. On the top of a vertical axis balance a thin horizontal rod. At each end of this rod fasten a small vertical square or sail of thin cardboard — the two sails being in the same plane. If anyone blows close to one of these squares and in a direction parallel to its plane, the square will move towards the side on which one is blowing, and the rod with the two sails will rotate about the axis.
The experiments above described can be performed so as to illustrate Hauksbee's Law ; but unless care is taken other causes will be also introduced which affect the phenomena : it is however unnecessary for ray purpose to go into these details.
Cut on a Tennis-Bail. Racquet and court-tennis players know that if a strong cut is given to a ball it can be made to rebound off a vertical wall and then (without striking the floor or any other wall) return and hit the wall again. This affords another illustration of Hauksbee's Law The effect had been noticed by Isaac Newton, who, in his letter to Oldenburg, February, 1672, N.S., says "I remembered that I had often seen *'a tennis-ball struck with an oblique racket describe such "a curve line. For, a circular as well as a progressive motion " being communicated to it by that stroke, its parts on that side " where the motions conspire, must press and beat the contiguous "air more violently than on the other; and there excite a "reluctancy and re-action of the air proportionably greater. " And. . .globular bodies," thus acquiring " a circulating motion. . . " ought to feel the greater resistance from the ambient aether " on that side where the motions conspire, and thence be con- " tinually bowed to the other."
The question was discussed by Magnus in 1837 and by Tait in various papers from 1887 to 1896. The explanation* is that the cut causes the ball to rotate rapidly about an axis through
* See Magnus on ^ Die Abiveichung der Geschosse^ in the Ahliandlungen der Alcademie der Wissenschajten, Berlin, 1852, pp. 1 — 23; Lord Rayleigh, ' On the irregular flight of a tennis ball,' Messenger of Mathematics, Cambridge, 1878, vol. vn, pp. 14 — 16; and P. G. Tait, Transactions Royal Society, Edinburgh, vol. xxTii, 1893; or Collected Scientific Papers^ Cambridge, vol. u, 1900, pp. 356—387, and references therein.
104 MECHANICAL RECREATIONS [CH. V
its centre of fio^ure, and the friction of the surface of the ball on the air produces a sort of whirlpool. This rotation is in addition to its motion of translation. Suppose the ball to be spherical and rotating about an axis through its centre perpendicular to the plane of the paper in the direction of the arrow-head, and at the same time moving through still air from left to right parallel to FQ. Any motion of the ball perpendicular to PQ will be produced by the pressure of the air on the surface of the ball, and this pressure will, by Hauksbee's Law, be greatest where the velocity of the air relative to the ball is least, and vice versa. To find the velocity of the air relative to the ball we may reduce the centre of the ball to rest, and suppose a stream of air to impinge on the surface of the ball moving with a velocity equal and opposite to that of the centre of the ball.
The air is not frictionless, and therefore the air in contact with the surface of the ball will be set in motion by the rotation of the ball and will form a sort of whirlpool rotating in the direction of the arrow-head in the figure. To find the actual velocity of this air relative to the ball we must consider how the motion due to the whirlpool is affected by the motion of the stream of air parallel to QP. The air at A in the whirlpool is moving against the stream of air there, and therefore its velocity is retarded : the air at B in the whirlpool is moving in the same direction as the stream of air there, and therefore its velocity is increased. Hence the relative velocity of the air at A is less than at B, and, since the pressure of the air is greatest where the velocity is least, the pressure of the air on the surface of the ball at A is greater than on that at B. Hence the ball is forced by this pressure in the direction from the line PQ, which we may
CH. V] MECHANICAL RECREATIONS 105
suppose to represent the section of the vertical wall in a racquet- court. In other words, the ball tends to move at right angles to the line in which its centre is movincr and in the direction in which the surface of the front of the ball is being carried by the rotation. Sir J. J. Thomson has pointed out that if we consider the direction in which the nose (or foremost point) of the ball is travelling, we may sum up the results by saying that the ball always follows its nose. Lord Rayleigh has shown that the line of action of resulting force on the ball is perpendicular to the plane containing the direction (m) of motion of the centre of the ball and the axis (s) of spin, and its magnitude varies directly as the velocity of translation, the velocity of spin, and the sine of the angle between the lines m and s.
In the case of a lawn tennis-ball, the shape of the ball is altered by a strong cut, and this introduces additional compli- cations.
Sp{7i on a Cricket-Ball. The curl of a cricket-ball in its flight through the air, caused by a spin given by the bowler in delivering the ball, is explained by the same reasoning.
Thus suppose the ball is delivered in a direction lying in a vertical plane containing the middle stumps of the two wickets. A spin round a horizontal axis parallel to the crease in a direction which the bowler's umpire would describe as positive, namely, counter clock- wise, will, in consequence of the friction of the air, cause it to drop, and therefore decrease the length of the pitch. A spin in the opposite direction will cause it to rise, and therefore lengthen the pitch. A spin round a vertical axis in the positive direction, as viewed from above, will make it curl sideways in the air to the left, that is, from leg to off. A spin in the opposite direction will make it curl to the right. A spin given to the ball round the direction of motion of the centre of the ball will not sensibly affect the motion through the air, though it would cause the ball, on hitting the ground, to break. Of course these various kinds of spin can be combined.
Flight of Golf-Balls. The same argument explains the effect of the spin given to a golf-ball by impact with the club. Here the motion takes place for a longer interval of time^ and
106 MECHANICAL RECREATIONS [CH. V
additional complications are introduced by the fact that the velocities of translation and rotation are retarded at different rates and that usually there will be some wind blowing in a cross direction. But generally we may say that the effect of the under-cut given by a normal stroke is to cause the ball to rise, and therefore to lengthen the carry. Also, if a wind is blowing across the line to the hole from right to left, a drive, if the player desires a long carry and has sufficient command over his club, should be pulled ; but an approach shot, if it is desired that the ball should fall dead, should be sliced because then the ball as soon as it meets the wind will tend to fall dead. Con- versely, if the wind is blowing across the course from left to right, the drive should be sliced if a long carry is desired, and an approach shot sViould be pulled if it is desired that the ball should fall dead.
The questions involving the application of Hauksbee's Law are easy as compared with many of the problems in fluid motion. The analysis required to attack most of these problems is beyond the scope of this book, but one of them may be worth mentioning even though no explanation is given.
The Theory of the Flight of Birds. A mechanical problem of great interest is the explanation of the means by which birds are enabled to fly for considerable distances with no (perceptible) motion of the wings. Albatrosses, to take an instance of special difficulty, have been known to follow for some days ships sailing at the rate of nine or ten knots, and sometimes for considerable periods there is no motion of the wings or body which can be detected, while even if the bird moved its wings it is not easy to understand how it has the muscular energy to propel itself so rapidly and for such a length of time. Of this phenomenon various explanations* have been suggested. Notable among these are Sir Hiram Maxim's of upward air- currents. Lord Rayleigh's of variations of the wind velocity at different heights above the ground, Dr S. P. Langley's of the
* See G. H. Bi-yan in the Transactions of the British Association for 1896, vol. Lxvi, pp. 726—723.
CH. V] MECHANICAL RECREATIONS 107
incessant occurrence of crusts of wind separated by lulls, and Dr Br3'-an's of vortices in the atmosphere.
It now seems reasonably certain that the second and third of these sources of energy account for at least a portion of the observed phenomena. The effect of the third cause may be partially explained by noting that the centre of gravity of the bird with extended wings is slightly below the aeroplane or wing surface, so that the animal forms a sort of parachute. The effect of a sudden gust of wind upon such a body is that the aeroplane is set in motion more rapidly than the suspended mass, causing the structure to heel over so as to receive the wind on the under surface of the aeroplane, and this lifts the suspended mass giving it an upward velocity. When the wind falls the greater inertia of the mass carries it on upwards causing the aeroplane to again present its under side to the air; and if while the parachute is in this position the wind is still blowing from the side, the suspended mass is again lifted. Thus the more the bird is blown about, the more it rises in the air ; actually birds in flight are carried up by a sudden side gust of wind as we should expect from this theory.
The fact that the bird is in motion tends also to keep it up, for it has been recently shown that a horizontal plane under the action of gravity falls to the ground more slowly if it is travelling through the air with horizontal velocity than it would do if allowed to fall vertically, hence the bird's forward motion causes it to fall through a smaller height between successive gusts of wind than it would do if it were at rest. Moreover it has been proved experimentally that the horse-power required to support a body in horizontal flight by means of an aeroplane is less for high than for low speeds : hence when a side-wind (that is, a wind at right angles to the bird's course) strikes the bird, the lift is increased in consequence of the bird's lor ward velocity.
Curios A Physica. When I was writing the first edition of these Recreations, I put together a chapter, following this one, on " Some Piiysical Questions," dealing with problems such as, in the Theory of Sound, the explanation of the fact that in
108 MECHANICAL RECREATIONS [CH. V
some of Captain Parry's experiments the report of a cannon, when fired, travelled so much more rapidly than the sound of the human voice that observers heard the report of the cannon when fired before that of the order to fire it* : in the Kinetic Theory of Gases, the complications in our universe that might be produced by "Maxwell's demon "f : in the Theory of Optics, the explanation of the Japanese "magic mirrors/'J which reflect the pattern on the back of the mirror, on which the light does not fall : to which I might add the theory of the " spectrum top," by means of which a white surface, on which some black lines are drawn, can be moved so as to give the impression§ that the lines are coloured (red, green, blue, slate, or drab), and the curious fact that the colours change with the direction of rotation : it has also been recently shown that if two trains of waves, whose lengths are in the ratio m — 1 : ??i + 1, be superposed, then every mth wave in the system will be big — thus the current opinion that every ninth wave in the open sea is bigger than the other waves may receive scientific confirma- tion. There is no lack of interesting and curious phenomena in physics, and in some branches, notably in electricity and magnetism, the difficulty is rather one of selection, but I felt that the connection with mathematics was in general either too remote or t(jo technical to justify the insertion of such a collection in a work on elementary mathematical recreations, and therefore I struck out the chapter. I mention the fact now partly to express the hope that some physicist will one day give us a collection of the kind, partly to suggest these questions to those who are interested in such matters.
* The fact is well authenticated. Mr Earnshaw (Philosophical Transactions, London, 1860, pp. 133 — 148) explained it by the acceleration of a wave caused by the formation of a kind of bore, a view accepted by Clerk Maxwell and most physicists, but Sir George Airy thought that the explanation was to be found in physiology; see Airy's Sound, second edition, London, 1871, pp. 141, 142.
t See Theory of Heat, by J. Clerk Maxwell, second edition, London, 1872, p. 308.
X See a mei-uoir by W. E. Ayrton and J. Perry, Proceedings of the Royal Society of London, part i, 1879, vol. xxviii, pp. 127—148.
§ See letters from Mr C. E. Benham and others in Nature, 1894-5; and a paper read by Prof. G. D. Liveing before the Cambridge Philosophical Society, November 26, 1894.
10^
CHAPTER Yl,
CHESS BOARD RECREATIONS.
A chess-board and chess-men lend themselves to recreations many of which are geometrical. The problems are, however, of a distinct type, and sufficiently numerous to deserve a chapter to themselves. A few problems which might be included in this chapter have been already considered in chapter I v.
The ordinary chess-board consists of 64 small squares, known as cells, arranged as shown below in 8 rows and 8 columns. Usually the cells are coloured alternately white and black, or white and red. The cells may be defined by the numbers 11, 12, &c., where the first digit denotes the number of the column.
18
28
38
48
58
68
78
88
17
27
37
47
57
67
77
87
16
26
36
46
56
66
76
86 85 84
15
25
35
45
55
65
75
14
24
34
44
54
64
74
13
23
33
43
53
63
73
83
32
12
22
32
42
52
62
72
11
21
31
41
51
61
71
81
and the second digit the number of the row — the two digits representing respectively the abscissa and ordinate of the mid- points of the cells. I use this notation in the following pages. A generalized board consists of n^ cells arranged in n rows and
110 CHESS-BOARD RECREATIONS [CH. VI
n columns. Most of the problems which I shall describe can be extended to meet the case of a board of n^ cells.
The usual chess-pieces are Kings, Queens, Bishops, Knights, and Rooks or Castles; there are also Pawns. I assume that the moves of these pieces are known to the reader.
With the game itself and with chess problems of the usual type I do not concern myself Particular positions of the pieces may be subject to mathematical analysis, but in general the moves open to a player are so numerous as to make it im- possible to see far ahead. Probably this is obvious, but it may emphasize how impossible it is to discuss the theory of the game effectively if I add that it has been shown that there may be as many as 197299 ways of playing the first four moves, and nearly 72000 different positions at the end of the first four moves (two on each side), of which 16556 arise when the players move pawns only*.
Relative Value of Pieces. The first question to which I will address myself is the determination of the relative values of the different chess-pieces f.
If a piece is placed on a cell, the number of cells it com- mands depends in general on its position. We may estimate the value of the piece by the average number of cells which it commands when placed in succession on every cell of the board. This is equivalent to saying that the value of a piece may be estimated by the chance that if it and a king are put at random on the board, the king will be in check : if no other re- striction is imposed this is called a simple check. On whatever cell the piece is originally placed there will remain 63 other cells on which the king may be placed. It is equally probable that it may be put on any one of them. Hence the chance that it will be in check is 1/63 of the average number of cells commanded by the piece.
♦ Vlntermediaire des Mathematiciens, Paris, December, 1903, vol. x, pp. 305 — 308 : also Royal Engineers Journal, London, August — November, 1889 ; or British Association Transactions, 1890, p. 745.
t H. M. Taylor, Philosophical Magazine^ March, 1876, series 5, vol. i, pp. 221—229.
CH. Vl] CHESS-BOARD RECREATIONS 111
A rook put on any cell commands 14 other cells. Wherever the rook is placed there will remain 63 cells on which the king may be placed, and on which it is equally likely that it will be placed. Hence the chance of a simple check is 14/63, that is, 2/9. Similarly on a board of rt? cells the chance is 2 (n - \)l{n' - 1), that is, 2/(n + 1).
A knight when placed on any of the 4 corner cells like
11 commands 2 cells. When placed on any of the 8 cells like
12 and 21 it commands 3 cells. When placed on any of the 4 cells like 22 or any of the 16 boundary cells like 13, 14, 15, 16, it commands 4 cells. When placed on any of the 16 cells like 23, 24, 25, 26, it commands 6 cells. And when placed on any of the remaining 16 middle cells it commands 8 cells. Hence the average number of cells commanded by a knight put on a chess-board is (4x2-1-8x3-1- 20 x4-|- 16x6 + 16 x 8)/64, that is, 336/64. Accordingly if a king and a knight are put on the board, the chance that the king will be in simple check is 336/64 X 63, that is 1/12. Similarly on a board of n^ cells the chance is 8 (n — 2)/n'^ (n + 1).
A bishop when placed on any of the ring of 28 boundary cells commands 7 cells. When placed on any ring of the 20 cells next to the boundary cells, it commands 9 cells. When placed on any of the 12 cells forming the next ring, it commands 11 cells. When placed on the 4 middle cells it commands 13 cells. Hence, if a king and a bishop are put on the board the chance that the king will be in simple check is (28 X 7 -h 20 X 9 -i- 12 X ll-f 4 X 13)/64 x 63, that is, 5/36. Similarly on a board of n^ cells, when n is even, the chance is 2 (2n — l)/3n (n + 1). When n is odd the analysis is longer, owing to the fact that in this case the number of white cells on the board differs from the number of black cells. I do not give the work, which presents no special difficulty.
A queen when placed on any cell of a board commands all the cells which a bishop and a rook when placed on that cell would do. Hence, if a king and a queen are put on the board, the chance that the king will be in simple check is 2/9 + 5/36, that is, 13/36. Similarly on a board of n^ cells, when n is even, the chance is 2 {5n — l)/3?i (w + 1).
112 CHESS-BOARD RECREATIONS [CH. VI
On the above assumptions the relative vahies of the rook, knight, bishop, and queen are 16, 6, 10, 26. According to Staunton's Chess-Player s Handbook the actual values, estimated empirically, are in the ratio of 548, 305, 350, 994 ; according to Von Bilguer the ratios are 540, 350, 360, 1000 — the value of a pawn being taken as 10.
There is considerable discrepancy between the above results as given by theory and practice. It has been, however, sug- gested that a better test of the value of a piece would be the chance that w^hen it and a king were put at random on the board it would check the king without giving the king the opportunity of taking it. This is called a safe check as distin- guished from a simple check.
Applying the same method as above, the chances of a safe check work out as follows. For a rook the chance of a safe check is (4 X 12 + 24 X 11 + 36 X 10)/64 x 63, that is, 1/6 ; or on a board of n^ cells is 2{n — 2)/n (/i + 1). For a knight all checks are safe, and therefore the chance of a safe check is 1/12 ; or on a. board of ?i^ cells is 8(n — 2)ln^{n + 1). For a bishop the chance of a safe check is 364/64 x 63, that is, 13/144; or on a board of n^ cells, when n is even, is 2 (n — 2) {2n — S)ISn^ (n + 1). For a queen the chance of a safe check is 1036/64 x 63, that is, 37/144 ; or on a board of ri" cells, is 2 {n - 2) {5n - 3)/3?i2 {n + 1), when n is even.
On this view the relative values of the rook, knight, bishop, queen are 24, 12, 13, 37 ; while, according to Staunton, experi- ence shows that they are approximately 22, 12, 14, 40, and according to Von Bilguer, 18, 12, 12, 33.
The same method can be applied to compare the values of combinations of pieces. For instance the value of two bishops (one restricted to white cells and the other to black cells) and two rooks, estimated by the chance of a simple check, are respectively 35/124 and 37/93. Hence on this view a queen in general should be more valuable than two bishops but less valuable than two rooks. This agrees with experience.
An analogous problem consists in finding the chance that two kings, put at random on the board, will not occupy adjoin- ing cells, that is, that neither would (were such a move possible)
CH. Vl]
CHESS-BOARD RECREATIONS
113
check the other. The chance is 43/48, and therefore the chance that they will occupy adjoining cells is 5/48. If three kings are put on the board, the chance that no two of them occupy adjoining cells is 1061/1488. The corresponding chances* for a board of n^ cells are (n -l){n- 2) (n^ + Sn- 2)ln^ (n^ - 1) and (n - 1) (n - 2) (n' + 371^ - 20^1^ - 30n + lS2)/n' (n' - 1) (n^ - 2).
The Eight Queens Problem f. One of the classical problems connected with a chess-board is the determination of the number of ways in which eight queens can be placed on a chess-board — or more generally, in which n queens can be placed on a board of n" cells — so that no queen can take any other. This was proposed originally by Franz Nauck in 1850.
In 1874 Dr S. GUntherJ suggested a method of solution by means of determinants. For, if each symbol represents the cor- responding cell of the board, the possible solutions for a board of 71- cells are given by those terms, if any, of the determinant
Ch
0,
Ci
0.
tts
h
78
13.
a.
^4
7b
A
di
a.
^2n— 3 P2n— 2
^2n— I
in which no letter and no suffix appears more than once.
The reason is obvious. Every term in a determinant con- tains one and only one element out of every row and out of every column : hence any term will indicate a position on the board in which the queens cannot take one another by moves rook-wise. Again in the above determinant the letters and suffixes are so arranged that all the same letters and all the
* V Intcrmidiaire des Mathematiciens, Paris, 1897, vol. rv, p. 6, and 1901, vol. VIII, p. 140.
t On the history of this problem see W. Ahrens, Mathematische Unter- haliungen und Spiele, Leipzig, 1901, chap. ix.
X Grunert's Archiv der Mathematik und Physik, 1874, vol. LVi, pp. 281 — 202.
B. R.
8
114
CHESS-BOARD RECREATIONS
[CH. VI
same suffixes lie along bishop's paths : hence, if we retain only those terms in each of which all the letters and all the suffixes are different, they will denote positions in which the queens cannot take one another by moves bishop- wise. It is clear that the signs of the terms are immaterial.
In the case of an ordinary chess-board the determinant is of the 8th order, and therefore contains 8!, that is, 40320 terms, so that it would be out of the question to use this method for the usual chess-board of 64 cells or for a board of larger size unless some way of picking out the required terms could be discovered.
A way of effecting this was suggested by Dr J. VV.L. Glaisher* in 1874, and so far as I am aware the theory remains as he left it. He showed that if all the solutions of n queens on a board of n^ cells were known, then all the solutions of a certain type for n + 1 queens on a board of {n-{-Vf cells could be deduced, and that all the other solutions of w + 1 queens on a board of {n + Xf cells could be obtained without difficulty. The method will be sufficiently illustrated by one instance of its application.
It is easily seen that there are no solutions when n = 2 and ?i = 3. If n = 4 there are two terms in the determinant which give solutions, namely, b^c^js/Ss and c^^jb^'y^. To find the solutions when 71 = 5, Glaisher proceeded thus. In this case, Gllnther's determinant is
di h Cs (h 65
13.2 as h C5 de
78 ^A «5 ^6 C7 ^4 75 ^6 CI7 bs ^5 Se 77 A Ctg
To obtain those solutions (if any) which involve a^ it is sufficient to append a^ to such of the solutions for a board of 16 cells as do not involve a. As neither of those given above involves an a we thus get two solutions, namely, h^c^y^^^a^ and CsfizhyzCto-
* Philosophical Magazine^ London, December, 1874, series 4, vol. xLvin, pp. 457—487.
CH. Vl]
CHESS-BOARD KECEEATIUNS
115
The solutions which involve a^ e^ and 65 can be written down by symmetry. The eight sohitions thus obtained are all dis- tinct ; we may call them of the first type.
The above are the only solutions which can involve elements in the corner squares of the determinant. Hence the remaining solutions are obtainable from the determinant
0
h
Cz
d.
0
13.
«8
Ih
C5
da
7»
/54
(
h
C7
^.
75
/3.
Clr
hs
0
8e
77
13s
0
If, in this, we take the minor of h.2 and in it replace by zero every term involving the letter b or the suffix 2 we shall get all solutions involving 63. But in this case the minor at once reduces to d^a^Bi^s- We thus get one solution, namely, bodss^ilSs- The solutions which involve ,8.2, B^, 8^, ^s, ^s, dg, and d^ can be obtained by symmetry. Of these eighfc solutions it is easily seen that only two are distinct : these may be called solutions of the second type.
Similarly the remaining solutions must be obtained from the determinant
0
0
Cs
0
0
0
a.
h
C5
0
78
/3.
a.
be
C7
0
75
A
a,
0
0
0
77
0
0
If, in this, we take the minor of Cg, and in it replace by zero every term involving the letter c or the suffix 3, we shall get all the solutions which involve Cj. But in this case the minor vanishes. Hence there is no solution involving Cs, and therefore by symmetry no solutions which involve 73, 77, or C7. Had there been any solutions involving the third element in the first or last row or column of the determinant we should have described them as of the third type.
8—2
116 CHESS-BOARD RECREATIONS [CH. VI
Thus in all there are ten and only ten solutions, namely, eight of the first type, two of the second type, and none of the third type.
Similarly, if n = 6, we obtain no solutions of the first type, four solutions of the second type, and no solutions of the third type ; that is, four solutions in all. If n = 7, we obtain sixteen solutions of the first type, twenty-four solutions of the second tj^pe, no solutions of the third type, and no solutions of the fourth type ; that is, forty solutions in all. If ?z = 8, we obtain sixteen solutions of the first type, fifty-six solutions of the second type, and twenty solutions of the third type, that is, ninety- two solutions in all.
It will be noticed that all the solutions of one type are not always distinct. In general, from any solution seven others can be obtained at once. Of these eight solutions, four consist of the initial or fundamental solution and the three similar ones obtained by turning the board through one, two, or three right angles ; the other four are the reflexions of these in a mirror : but in any particular case it may happen that the reflexions reproduce the originals, or that a rotation through one or two right angles makes no difference. Thus on boards of 4^, 5^, 6^ 7^ 8^ 92, 102 cells there are respectively 1, 2, 1, 6, 12, 46, 92 fundamental solutions ; while altogether there are respectively 2, 10, 4, 40, 92, 352, 724 solutions.
The following collection of fundamental solutions may in- terest the reader. Each position on the board of the queens is indicated by a number, but as necessarily one queen is on each column I can use a simpler notation than that explained on page 109. In this case the first digit represents the number' of the cell occupied by the queen in the first column reckoned from one end of the column, the second digit the number in the second column, and so on. Thus on a board of 4* cells the solution 3142 means that one queen is on the 3rd square of the first column, one on the 1st square of the second column, one on the 4th square of the third column, and one on the 2nd square of the fourth column. If a fundamental solution gives rise to only four solutions the number which indicates it is placed
CH. VI]
CHESS-BOARD RECREATIONS
117
in curved brackets, ( ) ; if it gives rise to only two solutions the number which indicates it is placed in square brackets, [ ] ; the other fundamental solutions give rise to eight solutions each.
On a board of 4^ cells there is 1 fundamental solution : namely, [3142].
On a board of 5* cells there are 2 fundamental solutions : namely, 14253, [25314]. It may be noted that the cyclic solutions 14253, 25314, 31425, 42531, 53142 give five super- posable arrangements by which five white queens, five black queens, five red queens, five yellow queens, and five blue queens can be put simultaneously on the board so that no queen can be taken by any other queen of the same colour.
On a board of 6^ cells there is 1 fundamental solution: namely, (246135). The four solutions are superposable. The puzzle for this case is sold in the streets of London for a penny, a small wooden board being ruled in the manner shown in the diagram and having holes drilled in it at the points marked by dots. The object is to put six pins into the holes so that no two are connected by a straight line.
On a board of 7^^ cells there are 6 fundamental solutions : namely, 1357246, 3572461, (5724613), 4613572, 3162574, (2574136). It may be noted that the solution 1357246 gives by cyclic permutations seven superposable arrangements.
On a board of 8- cells there are 12 fundamental solutions : namely, 25713864, 57138642, 71386425, 82417536, 68241753, 36824175,64713528,36814752,36815724, 72418536, 26831475, (64718253). The arrangement in this order is due to Mr Oram. It will be noticed that the 10th, 11th, and 12th solutions some- what resemble the 4th, 6th, and 7th respectively. The 6th
118
CHESS-BOARD RECREATIONS
[CH. VI
solution is the only one in which no three queens are in a straight line. It is impossible* to find eight superposable so- lutions ; but we can in five typical ways pick out six solutions which can be superposed, and to some of these it is possible to add 2 sets of 7 queens, thus filling 62 out of the 64 cells with 6 sets of 8 queens and 2 sets of 7 queens, no one of which can take another of the same set. Here is such a solution : 16837425, 27368514, 35714286, 41586372, 52473861, 68241753, 73625140, 04152637. Similar superposition problems can be framed for boards of other sizes.
On a board of 9^ cells there are 46 fundamental solutions, and on a board of 10- cells there are 92 fundamental solutions ; these were given by Dr A. Peinf. On a board of 11=* cells there are 341 fundamental solutions ; these have been given by Dr T. B. SpragueJ.
On any board empirical solutions may be found with but little difiiculty, and Mr Derrington has constructed the following table of solutions :
2.4.1 2.4.1
3 3
for a board of 4? cells
2.4.6.1.3.5
2.4.6.1.8.5.7
2.4.6.8.3.1.7.5
2.4.1.7.9.6.3.5.8
2. 4. 6. 8. 10. 1.3. 5. 7. 9
2. 4. 6. 8. 10. 1.3. 5. 7. 9. 11
2. 4. 6. 8. 10. 12. 1.3. 5. 7. 9. 11
2 . 4 . 6 . 8 . 10 . 12 . 1 . 3 . 5 . 7 . 9 . 11 . 13
9 . 7 . 5 . 3. 1 . 13 . 11 . 6 . 4 . 2 . 14 . 12 . 10 . 8
15 . 9 . 7 . 5 . 3 . 1 . 13 . 11 . 6 . 4 . 2 . 14 . 12 . 10 . 8
2 . 4 . 6 . 8 . 10 . 12 . 14 . 16 . 1 . 3 . 5 . 7 . 9 . 11 . 13 . 15
2 . 4 . 6 . 8 . 10 . 12 . 14 . 16 . 1 . 3 . 5 . 7 . 9 . 11 . 13 . 15 . 17
2 . 4 . 6 . 8 . 10 . 12 . 14 . 16 . 18 . 1 . 3 . 5 . 7 . 9 . 11 . 13 . 15 . 17
2 . 4 . 6 . 8 . 10 . 12 . 14 . 16 . 18 . 1 . 3 . 5 . 7 . 9 . 11 . 13 . 15 . 17 . 19
12 . 10 . 8 . 6 . 4 . 2 . 20 . 18 . 16 . 14 . 9 . 7 . 5 . 3 . 1 . 19 . 17 . 15 . 13
21 . 12 . 10 . 8 . 6 . 4 . 2 . 20 . 18 . 16 . 14 . 9 . 7 . 5 . 3 . 1 . 19 . 17 . 15
11 13.11
62 72
8-^ 92
102 11"
12-
13- 142
152
1G2 172
182
192
20- 212
•t
i> »» >> >i >» >» »> »> >» »> >> )» »)
* See G. T. Bennett, The Messenger of Mathematics, Cambridge, June, 1909, vol. XXXIX, pp. 19 — 21.
t Aufstellung von n Koniginnen auf einem Schachbrett von n^ Feldern,
Leipzig, 1889.
X Proceedings of the Edinburgh Mathematical Society, vol. xvii, 1898-9,
pp. 43—68.
CH. Vl] CHESS-BOARD RECREATIONS 119
and so on. The rule is obvious except when n is of the form 6m 4- 2 or Qin + 3.
Maximum Pieces Problem*. The Eight Queens Problem suggests the somewhat analogous question of finding the maximum number of kings — or more generally of pieces of one t3rpe — which can be put on a board so that no one can take any other, and the number of solutions possible in each case.
In the case of kings the number is 16; for instance, one solution is when they are put on the cells 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77. For queens, it is obvious that the problem is covered by the analysis already given, and the number is 8. For bishops the number is 14, the pieces being put on the boundary cells; for instance one solution is when they are put on the cells 11, 12, 13, 14, 15, 16, 17, 81, 82, 83, 84, 85, 86, 87, there are 256 fundamental solutions. For knights the number is 32 ; for instance, they can be put on all the white or on all the black cells, and there are 2 fundamental solutions. For rooks it is obvious that the number is 8, and there are in all 8 ! solutions.
Minimum Pieces Problem*. Another problem of a some- what similar character is the determination of the minimum number of kings — or more generally of pieces of one type — which can be put on a board so as to command or occupy all the cells.
For kings the number is 9 ; for instance, they can be put on the cells 11, 14, 17, 41, 44, 47, 71, 74, 77. For queens the number is 5; for instance, they can be put on the cells 18, 35, 41, 76, 82. For bishops the number is 8; for instance, they can be put on the cells 41, 42, 43, 44, 45, 46, 47, 48. For knights the number is 12; for instance, they can be put on the cells 26, 32, 33, 35, 36, 43, 56, 63, 64, 66, 67, and 73— constituting four triplets arranged symmetrically. For rooks the number is 8, and the solutions are obvious.
* Mr H. E. Dudcney has written on these problems m the WeeJdy Dispatch.
120 CHESS-BOARD RECREATIONS [CH. VI
For queens the problem has been also discussed for a board of n^ cells where n has various values*. One queen can be placed so as to command all the cells when n = 2 or 3, and there is only 1 fundamental solution. Two queens are required when 71 = 4 ; and there are 3 fundamental solutions, namely, when they are placed on the cells 11 and 33, or on the cells 12 and 42, or on the cells 22, 23: these give 12 solutions in all. Three queens are required when ?i = 5 ; and there are 37 funda- mental solutions, giving 186 solutions in all. Three queens are also required when n = 6, but there is only 1 fundamental solution, namely, when the}?- are put on the cells 11, 35, and 53, giving 4 solutions in all. Four queens are required when 71 = 7, one solution is when they are put on the cells 12, 26, 41, 55.
Jaenisch proposed also the problem of the determination of the minimum number of queens which can be placed on a board of n^ cells so as to command all the unoccupied cells, subject to the restriction that no queen shall attack the cell occupied by any other queen. In this case three queens are required when 71 = 4, for instance, they can be put on the cells 11, 23, 42 ; and there are 2 fundamental solutions, giving 16 solutions in all. Three queens are required when ti = 5, for instance, they can be put on the cells 11, 24, 43, or on the cells 11, 34, 53 ; and there are 2 fundamental solutions in all. Four queens are required when w = 6, for instance, when they are put on the cells 13, 36, 41, 64; and there are 17 fundamental solutions. Four queens are required when n=*I, and there is only 1 fundamental solu- tion, namely, that already mentioned, when they are put on the cells 12, 26, 41, 55, which gives 8 solutions in all. Five queens are required when n=8, and there are no less than 91 funda- mental solutions ; for instance, one is when they are put on the cells 11, 23, 37, 62, 76.
I leave to any of my readers who may be interested in such questions the discussion of the corresponding problems for the
* C. F. de Jaenisch, Applications de VAnalyse Mathematique au Jeu des Echecs, St Petersburg, 1862, Appendix, p. 244 et seg.; see also L' Inter mediaire des MatkcmaticienB, Paris, 1901, vol. viii, p. 88.
CH. Vl] CHESS-BOARD RECREATIONS 121
other pieces *, and of the number of possible solutions in each case.
A problem of the same nature would be the determination of the minimum number of queens (or other pieces) which can be placed on a board so as to protect one another and command all the unoccupied cells. For queens the number is 5 ; for instance, they can be put on the cells 24, 34, 44, 54 and 84. For bishops the number is 10; for instance, they can be put on the cells 24, 25, 34, 35, 44, 45, 64, 65, 74, and 75. For knights the number is 14; for instance, they can be put on the cells 32, 33, 36, 37, 43, 44, 45, 46, 63, 64, 65, 66, 73, and 76: the solution is semi-symmetrical. For rooks the number is 8, and a solution is obvious. I leave to any who are interested in the subject the determination of the number of solutions in each case.
In connexion with this class of problems, I may mention two other questions, to which Captain Turton first called my attention, of a somewhat analogous character.
The first of these is to place eight queens on a chess-board so as to command the fewest possible squares. Thus, if queens are placed on cells 21, 22, 62, 71, 73, 77, 82, 87, eleven cells on the board will not be in check; the same number can be obtained by other arrangements. Is it possible to place the eight queens so as to leave more than eleven cells out of check? I have never succeeded in doing so, nor in showing that it is impossible to do it.
The other problem is to place m queens (m being less than 5) on a chess-board so as to command as many cells as possible. For instance, four queens can be placed in several ways on the board so as to command 58 cells besides those on which the queens stand, thus leaving only 2 cells which are not com- manded; for instance, queens may be placed on the cells 35, 41,
* The problem for knights was discussed in Ulntermidiaire des Mathe- maticiens, Paris, 189G, vol. in, p. 58; 1897, vol. iv, pp. 15—17, 254; 1898, vol. V, pp. 87, 230—231.
122 CBESS-BOARD RECREATIONS [CH. VI
76, and 82. Analogous problems with other pieces will suggest themselves.
There are endless similar questions in which combinations of pieces are involved. For instance, if queens are put on the cells 35, 41, 76, and 82 they command or occupy all but two cells, and these two cells may be commanded or occupied by a queen, a king, a rook, a bishop, or a pawn. If queens are put on the cells 22, 35, 43, and 54 they command or occupy all but three cells, and two of these three cells may be commanded by a knight which occupies the third of them.
Re- Entrant Paths on a Chess-Board. Another problem connected with the chess-board consists in moving a piece in such a manner that it shall move successively on to every pos- sible cell once and only once.
KnigMs Re-Entrant Path. I begin by discussing the classical problem of a knight's tour. The literature* on this subject is so extensive that I make no attempt 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.
* For a bibliography see A. van der Linde, Geschichte und Literatur des Schachspiels, Berlin, 1874, vol. ii, pp. 101 — 111. On the problem and its history see a memoir by P. Volpicelli in Atti della Reale Accademia dei Linceiy Rome, 1872, vol. xxv, pp. 87 — 162 : also Applications de V Analyse Mathematique au Jeu des Echecs, by C. F. de Jaenisch, 3 vols., St Petersburg, 1862-3; and General Parmentier, Association Franraise pour I'avancement des ScienceSf 1891, 1892, 1894.
CH. Vl]
CHESS-BOARD RECREATIONS
123
The earliest solutions of which I have any knowledge are those given at the beginning of the eighteenth century by De Montmort and De Moivre*. 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, where the numbers
34
49
22
11
36
39
24
"
21
10
35
50
23
12
37
40
48
33
62
57
38
25
2
13
'
20
51
54
63
60
41
26
I32 1
47
58
61
56
53r
14
3
|l9
8
55
52
59
64
27
42
46
31
6
17
44
29
4
15
7
18
45
30
5
16
A 0
28
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
De Moivre^* Solution.
Euler^s Thirty-six Cell Solution.
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.
The earliest serious attempt to deal with the subject by
* They were sent by their authors to Brook Taylor who seems to huve previously suggested the problem. I do not know where they were first pub- lished ; they were quoted by Ozanam and Moutucla, see Ozanam, 1803 edition, vol. I, p. 178 ; 1840 edition, p. 80.
124
CHESS-BOARD RECREATIONS
[CH. VI
mathematical analysis was made by Euler* in 1759 : it was due to a suggestion made by L. Bertrand of Geneva, who sub- sequently (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, h, — His method consists in establishing certain rules by which these vacant cells can be interpolated into various parts of the circuit, and by ^vhich the circuit can be made re-entrant.
The following example, mentioned by Legendre as one of exceptional difficulty, illustrates the method. Suppose that
55
58
29
40
27
44
19
22
22
25
50
39
52
35
60
"I
60
39
56
43
30
21
26
46
27
40
23
36
49
58
53
34
57
54
59
28
41
18
23
20
24
21
26
51
38
61
56
59
38
61
42
31
8
25
46
17
41
28
37
48
3
54
33
62
53
32
37
a
47
16
9
24
20
47
42
13
32
63
4
55
50
3
52
33
36
7
12
15
29
16
19
46
43
2
7
10
1
34
5
48
b
14
c
10
18
45
14
31
12
9
64
5
4
49
2
35
6
11
d
13
15
30
17
44
1
6
11
8
Figure i. Figure ii.
Example of Euler^s Method.
we have formed the route given in figure i above; 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
' MSmoires de Berlin for 1759, Berlin, 1766, pp. 310 — 337 ; or Commentationes Arithmeticae Collectae, St Petersburg, 1849, vol. i, pp. 337 — 355.
CH. Vl] CHESS-BOARD RECREATIONS 125
re-entrant. This is the case here ii 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 numl)ers 60, 59, ..., 52 by 52, 53, . . . , 60, the steps will be numbered consecutively. I recom- mend 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 proceed to 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 in- different 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 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 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, 2, 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.
126
CHESS-BOARD RECREATIONS
[CH. VI
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 above. 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. The order of the first 32 moves
58
43
60
37
52
41
62
35
49
46
67
42
61
36
63
40
44
59
48
51
38
55
34
63
47
50
45
56 T
33
64
39
54
22
7
32
31
2
23
6
19
16
27
12
8
21
4
29
10
25
14
17
3
80
9
20
5
28
11
26
50
45
62
41
60
39
54
35
63 46
42
51
48
53
36
57
88
49
44
61
40
59
34
65
43
64 5
47
52
1
33
56
37
68
23
2
27
8
29
12
17
14
6
25
4
21
19
10
81
Is
3
22
7
28
9
30
13
Euler's Half-hoard Solution.
Eogefs Half-board Solution,
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 con- taining 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
CH. Vl] CHRSS-BOARD RECREATIONS 127
whose distances are respectively x and y from the opposite sides a complementary cell. Thus the cells (a?, 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 b}^ 25.
Roget's method, which is described later, can be also applied to give half-board solutions. The result is indicated above. 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 sym- metrical solution for a square of 100 cells.
The next attempt of any special interest is due to Vander- monde*, 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 corre- sponding differences 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 Vander- monde 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,
* L'Hiistoire de VAcadeniie des Sciences for 1771, Paris, 1774, pp. 5GG— 574.
128 CHESS-BOARD RECREATIONS [CH. VI
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 trans- ferred 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 con- sidered 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 con- nected in such a manner as to permit of our starting from it. This is the foundation of the modem manner of attacking the problem. The method was re-invented in 1825 by Prattf, 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.
One of the most ingenious of the solutions of the knight's path is that given in 1823 by Warnsdorff|. His rule is that the knight must be always moved 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.
Wamsdorff 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.
* Solution du Probleme du Cavalier au Jeu des Echecs, Mannheim, 1778. + Studies of Chess, sixth edition, London, 1825.
X H. C. Wamsdorff, Des Rosselsprunges einfachste und allgemeinste Losung, Schmalkalden, 1823 : see also Jaenisch, vol. ii, pp. 56—61, 273 — 289.
CH. Vl] CHESS-BOARD RECREATIONS 129
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 re- strictions : such as to require that the route shall be re-en- trant, or more generally that it shall begin and terminate on given cells.
The simplest solution with which I am acquainted — and one which I believe is not generally known — is due to Rogetf. It divides the whole route into four circuits, which can be combined so as to enable us to begin on any cell and termi- nate 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 (4ny cells: for example, it could not be used on the board of the French jeu des dames J 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 Z, e, a, or p, as the case may be. The path of 4 cells indicated by the consonants I 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.
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 mav make the circuit re-entrant, and
* See ex. gr. T. Ciccolini's work Del Cavallo degli Scacchi, Paris, 1836.
t 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 Eoget's method, are given in the Leisure Hour^ Sept. 13, 1873, pp. 587—590 ; see also Ibid., Dec. 20, lt)73, pp. 813-815.
b. u. 9
130
CHESS-BOARD KECREATIONS
[CH. VI
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 below. Similarly all the cells marked a can be combined into the circuit indicated by the numbers 17 to 32 ; all the I 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.
/
€
a
P
I
e
a
P
a
P
1
e
a
P
I
e
e
I
P
a
e
I
P
a
P
a
e
I
P
a
e
I
I
e
a
P
I
e
a
P
a
P
I
e
a
P
I
e
e
I
P
a
e
I
P
a
P
a
e
I
V
a
€
I
34
51
32
16
38
63
18
3
31
14
35
52
17
2
39
54
50
33
16
29
56
37
4
19
13
30
49
36
1
20 17
65
40
48
63
28
9
44
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 (i).
RogeVs Solution (ii).
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 64th 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 F. This is always possible. Then, leaving
CH. Vl] CHESS-BOARD RECREATIONS 131
out the cells Z and F, 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 64th 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 above, 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 jo, next the 16 cells marked a, then the 16 cells marked I, 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* and by Laquieref, 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.
* Comptes Rendiis, April, 1861 ; and Bulletin de la SorigtS Mathfmatique de France, 1881, vol. ix, pp. 17 — 24.
t Bulletin de la Society Matlieinatique de France, 1880, vol. viii, pp. 82 — 102, 132—158.
9—2
132
CHESS-BOARD RECREATIONS
[CH. VI
Roget's method can be also applied to two half-boards, as- indicated in the figure given above on page 126.
The method v^^hich 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 below, 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. Other solutions, notably those by Moon and by Wenzelides, were given in former editions of this work. The two re-entrant routes printed below, each covering 32 cells, and together covering the board, are remarkable as constituting a magic square*.
63 22
15
40
1
42
59
18
U
39
64
21
60
17
2
43
37
62
23
16
41
4
19
58
24
13
38
61
20
57
44
3
11
36
25
52
29
46
5
56
26
51
12
33
8
55
30
45
35
10
49
28
53
32
47
6
50
27
34
9
48
7
54
31
15
20
17
36
13
64
61
34
18
37
14
21
60
35
12
63
25
16
19
44
5
62
33
56
38
45
26
59
22
55
4
11
27
24
39
6
43
10
57
54
40
49
46
23
58
3
32
9
47
28
51
42
7
30
53
2
50
41
48
29
52
1
8
31
Jaenischh Solution.
Two Half Board Solutions.
It is as yet impossible to say how many solutions of the problem exist. Legendref mentioned the question, but Minding J 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§ 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||.
♦ See A. Billy, Le Probleme du Cavalier des Echecs, Troyes, 1905. + Theorie des Nomhres, Paris, 2nd edition, 1880, vol. ii, p. 165. X Cambridge and Dublin Mathematical Journal^ 1852, vol. vii, pp. 147 — 156; and Crelle's Journal, 1853, vol. xliv, pp. 73—82. § Jaenisch, vol. ii, p. 268. II Bulletin de la Societe Mathematique de France, 1881, vol. ix, pp. 1—17.
CH. Vl]
CHESS-BOARD RECREATIONS
133
Analogous Problems. Similar problems can be constructed in which it is required to determine routes by which a piece moving according to certain laws {ex. gr. a chess-piece such as a king, &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.
King's Re- Entrant Path. As one example here is a re- entrant tour of a king which moves successively to every cell
61
62
63
64
1
2
3
4
60
11
58
57
8
7
54
5
12
59
10
9
56
55
G
63
13
14
15
16
49
60
51
52
20
19
18
17
48
47
40
45
21
38
23
24
41
42
27
44
37
22
39
40
25
20
43
28
30
35
34
33
32
31
30
L!i
King's Magic Tour on a Chess-Board.
of the board. I give it because the numbers indicating the cells successively occupied form a magic square. Of course this also gives a solution of a re-entrant route of a queen covering the board.
Book's Re-Entrant Path. There is no difficulty in con- structing re-entrant tours for a rook which moves successively to every cell of the board. For instance, if the rook starts from the cell 11 it can move successively to the cells 18, 88, 81, 71, 77, 67, 61, 51, 57, 47, 41, 31, 37, 27, 21, and so back to 11: this is a symmetrical route. Of course this also gives a solution of a re-entrant route for a kiiig or a queen covering the board.
134 CHESS-BOARD RECREATIONS [CH. VI
If we start from any of the cells mentioned above, the rook takes sixteen moves. If we start from any cell in the middle of one of these moves, it will take seventeen moves to cover this route, but I believe that in most cases wherever the initial cell be chosen sixteen moves will suffice, though in general the route will not be symmetrical. On a board of n^ cells it is possible to find a route by which a rook can move successively from its initial cell to every other cell once and only once. Moreover* starting on any cell its path can be made to termi- nate, 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.
Bishop's Re-Entrant Path. As yet another instance, a bishop can traverse all the cells of one colour on the board in seven- teen moves if the initial cell is properly chosen f; for instance, starting from the cell 11, it may move successively to the cells 55, 82, 71, 17, 28, 46, 13, 31, 86, 68, 57, 48, 15, 51, 84, m, 88. One more move will bring it back to the initial cell. From the nature of the case, it must traverse some cells more than once.
Miscellaneous Problems. We may construct numerous such problems concerning the determination of routes which cover the whole or part of the board subject to certain conditions. I append a few others which may tax the ingenuity of those not accustomed to such problems.
Routes on a Chess-Board. One of the simplest is the determination of the path taken by a rook, placed in the cell 11, which moves, one cell at a time, to the cell 88, so that in the course of its path it enters every cell once and only once. This can be done, though I have seen good mathematicians puzzled to effect it. A hasty reader is apt to misunderstand the conditions of the problem.
Another simple problem of this kind is to move a queen from the cell 33 to the cell 66 in fifteen moves entering every cell once
* L'Intermediaire des Mathematiciens, Paris, 1901, vol. viii, pp. 153 — 154. t H. E. Dudeney, The Tribune, Dec. 3, 1906.
CH. Vl] CHESS-BOARD RECREATIONS 135
and only once, and never cro.sying its own track or entering a cell more than once*.
A somewhat similar, but more difficult, question is the determination of the greatest distance which can be travelled by a queen starting from its own square in five consecutive moves, subject to the condition that it never crosses its own track or enters a cell more than oncef. In calculating the distance it may be assumed that the paths go through the centres of the cells. If the length of the side of a cell is one inch, the distance exceeds 33"95 inches.
Another familiar problem can be enunciated as follows. Construct a rectangular board of vm cells by ruling in + 1 vertical lines and n + 1 horizontal lines. It is required to know how many routes can be taken from the top left-hand corner to the bottom right-hand corner, the motion being along the ruled lines and its direction being always either vertically doTNTiwards or horizontally from left to right. The answer is the number of permutations of m -I- n things, of which m are alike of one kind and n are alike of another kind: this is equal to {m-\-n)\ I mini. Thus on a square board containing 16 cells (i.e. one-quarter of a chess-board), where m = n = 4, there are 70 such routes ; while on a common chess-board, where m = n = 8, there are no less than 12870 such routes. A rook, moving ac- cording to the same law, can travel from the top left-hand cell to the bottom right-hand cell in (m-\-n — 2)! / (m— 1)! (?i — 1)! ways. Similar theorems can be enunciated for a parallele- piped.
Another question of this kind is the determination of the number of closed routes through mn points arranged in m rows and n columns, following the lines of the quadrilateral net- work, and passing once and only once through each point |.
Guarinis Problem. One of the oldest European problems connected with the chess-board is the following which was
• H. E. Dudeney, The Trihune, Oct. 3, 1906. + Ibid., Oct. 2, 1906.
+ See C. F. Sainte-Marie in L^Intermediaire de$ Mathematiciens, Paris, vol. XI, March, 19U4, pp. 86—88.
136
CHESS-BOARD RECREATIONS
[CH. VI
propounded in 1512. It was quoted by Lucas in 1894, but I believe has not been published otherwise than in his works and the earlier editions of this book. On a board of nine cells, such as that drawn below, the two white knights are placed on the
a D
b
C A
d
B c
two top corner cells (a, d), and the two black knights on the two bottom corner cells (6, c) : the other cells are left vacant. It is required to move the knights so that the white knights shall occupy the cells b and c, while the black shall occupy the cells a and d.
The solution is tolerably obvious. First, move the pieces from a to ^, from b to B, from c to C, and from d to D. Next, move the pieces from A to d, from B to a, from C to 6, and from D to c. The effect of these eight moves is the same as if the original square had been rotated through one right angle. Repeat the above process, that is, move the pieces successively from a to ^, from b to B, from c to G, from d to D; from A to d, from B to a, from G to 6, and from D to c. The required result is then attained.
Queens' Problem. Another problem consists in placing sixteen queens on a board so that no three are in a straight line*. One solution is to place them on the cells 15, 16, 25, 26, 31, 32, 41, 42, 57, 58, 67, 68, 73, 74, 83, 84. It is of course assumed that each queen is placed on the middle of its cell.
» H. E. Dudeney, The Tribune, November 7, 1906.
137