Sources page biographical material

6.AK. POLYGONAL PATH COVERING N x N LATTICE OF POINTS,

QUEEN'S TOURS, ETC.
For magic circuits, see 7.N.4.

3x3 problem: Loyd (1907), Pearson, Anon., Bullivant, Goldston, Loyd (1914), Blyth, Abraham, Hedges, Evans, Doubleday - 1, Piggins & Eley

4x4 problem: King, Abraham, M. Adams, Evans, Depew, Meyer, Ripley's,

Queen's tours: Loyd (1867, 1897, 1914), Loyd Jr.

Bishop's tours: Dudeney (1932), Doubleday - 2, Obermair

Rook's tours: Loyd (1878), Proctor, Loyd (1897), Bullivant, Loyd (1914), Filipiak, Hartswick, Barwell, Gardner, Peters, Obermair

Other versions: Prout, Doubleday - 1

Trick solutions: Fixx, Adams, Piggins, Piggins & Eley

Thanks to Heinrich Hemme for pointing out Fixx, which led to adding most of the material on trick solutions.
Loyd. ??Le Sphinx (Mar 1867 -- but the Supplement to Sam Loyd and His Chess Problems corrects this to 15 Nov 1866). = Chess Strategy, Elizabeth, NJ, 1878, no. or p. 336(??). = A. C. White; Sam Loyd and His Chess Problems; 1913, op. cit. in 1; no. 40, pp. 42 43. Queen's circuit on 8 x 8 in 14 segments. (I.e. closed circuit, not leaving board, using queen's moves.) No. 41 & 42 of White give other solutions. White quotes Loyd from Chess Strategy, which indicates that Loyd invented this problem. Tit Bits No. 31 & SLAHP: Touring the chessboard, pp. 19 & 89, give No. 41.

Loyd. Chess Strategy, 1878, op. cit. above, no. or p. 337 (??) (= White, 1913, op. cit. above, no. 43, pp. 42 43.) Rook's circuit on 8 x 8 in 16 segments. (I.e. closed circuit, not leaving board, using rook's moves, and without crossings.)

Richard A. Proctor. Gossip column. Knowledge 10 (Dec 1886) 43 & (Feb 1887) 92. 6 x 6 array of cells. Prisoner in one corner can exit from the opposite corner if he passes "once, and once only, through all the 36 cells." "... take the prisoner into either of the cells adjoining his own, and back into his own, .... This puzzle is rather a sell, ...." Letter and response [in Gossip column, Knowledge 10 (Mar 1887) 115-116] about the impossibility of any normal solution.

Loyd. Problem 15: The gaoler's problem. Tit Bits 31 (23 Jan & 13 Feb 1897) 307 & 363. Rook's circuit on 8 x 8 in 16 segments, but beginning and ending on a central square. Cf The postman's puzzle in the Cyclopedia, 1914.

Loyd. Problem 16: The captive maiden. Tit Bits 31 (30 Jan & 20 Feb 1897) 325 & 381. Rook's tour in minimal number of moves from a corner to the diagonally opposite corner, entering each cell once. Because of parity, this is technically impossible, so the first two moves are into an adjacent cell and then back to the first cell, so that the first cell has now been entered.

Loyd. Problem 20: Hearts and darts. Tit Bits 31 (20 Feb, 13 & 20 Mar 1897) 381, 437, 455. Queen's tour on 8 x 8, starting in a corner, permitting crossings, but with no segment going through a square where the path turns. Solution in 14 segments. This is No. 41 in White -- see the first Loyd entry above.

Ball. MRE, 4th ed., 1905, p. 197. At the end of his section on knight's tours, he states that there are many similar problems for other kinds of pieces.

Loyd. In G. G. Bain, op. cit. in 1, 1907. He gives the 3 x 3 lattice in four lines as the Columbus Egg Puzzle.

Pearson. 1907. Part I, no. 36: A charming puzzle, pp. 36 & 152 153. 3 x 3 lattice in 4 lines.

Loyd. Sam Loyd's Puzzle Magazine (Apr 1908) -- ??NYS, reproduced in: A. C. White; Sam Loyd and His Chess Problems; 1913, op. cit. in 1; no. 56, p. 52. = Problem 26: A brace of puzzles -- No. 26: A study in naval warfare; Tit Bits 31 (27 Mar 1897) 475 & 32 (24 Apr 1897) 59. = Cyclopedia, 1914, Going into action, pp. 189 & 364. = MPSL1, prob. 46, pp. 44 & 138. = SLAHP: Bombs to drop, pp. 86 & 119. Circuit on 8 x 8 in 14 segments, but with two lines of slope 2. In White, p. 43, Loyd says an ordinary queen's tour can be started "from any of the squares except the twenty which can be represented by d1, d3 and d4." This problem starts at d1. However I think White must have mistakenly put down twenty for twelve??

Anon. Prob. 67. Hobbies 31 (No. 782) (8 Oct 1910) 39 & (No. 785) (29 Oct 1910) 94. 3 x 3 lattice in 4 lines "brought under my notice some time back".

C. H. Bullivant. Home Fun, 1910, op. cit. in 5.S. Part VI, Chap. IV.

No. 1: The travelling draught man, pp. 515 & 520. Rook's circuit on 8 x 8 in 16 segments, different than Loyd's.

No. 3: Joining the rings. 3 x 3 in 4 segments.

Will Goldston. More Tricks and Puzzles without Mechanical Apparatus. The Magician Ltd., London, nd [1910?]. (BMC lists Routledge & Dutton eds. of 1910.) (There is a 2nd ed., published by Will Goldston, nd [1919].) The nine dot puzzle, pp. 127 128 (pp. 90 91 in 2nd ed.).

Loyd. Cyclopedia, 1914, pp. 301 & 380. = MPSL2, prob. 133 -- Solve Christopher's egg tricks, pp. 93 & 163 (with comment by Gardner). c= SLAHP: Milkman's route, pp. 34 & 96. 3 x 3 case.

Loyd. Cyclopedia, 1914, pp. 293 & 379. Queen's circuit on 7 x 7 in 12 segments.

Loyd. The postman's puzzle. Cyclopedia, 1914, pp. 298 & 379. Rook's circuit on 8 x 8 array of points, with one point a bit out of line, starting and ending at a central square, in 16 segments. P. 379 also shows another 8 x 8 circuit, but with a slope 2 line. See also pp. 21 & 341 and SLAHP, pp. 85 & 118, for two more examples.

Loyd. Switchboard problem. Cyclopedia, 1914, pp. 255 & 373. (c= MPSL2, prob. 145, pp. 102 & 167.) Rook's tour with minimum turning.

Blyth. Match-Stick Magic. 1921. Four-way game, pp. 77-78. 3 x 3 in 4 segments.

King. Best 100. 1927. No. 16, pp. 12 & 43. 4 x 4 in 6 segments, not closed, but easily can be closed.

Loyd Jr. SLAHP. 1928. Dropping the mail, pp. 67 & 111. 4 x 4 queen's tour in 6 segments.

Collins. Book of Puzzles. 1927. The star group puzzle, pp. 95-96. 3 x 3 in 4 segments.

Dudeney. PCP. 1932. Prob. 264: The fly's tour, pp. 82 & 169. = 536, prob. 422, pp. 159 & 368. Bishop's path, with repeated cells, going from corner to corner in 17 segments.

Abraham. 1933. Probs. 101, 102, 103, pp. 49 & 66 (30 & 118). 3 x 3, 4 x 4 and 6 x 6 cases.

The Bile Beans Puzzle Book. 1933. No. 4: The puzzled milkman. 3 x 3 array in four lines.

Sid G. Hedges. More Indoor and Community Games. Methuen, London, 1937. Nine spot, p. 110. 3 x 3. "Of course it can be done, but it is not easy." No solution given.

M. Adams. Puzzle Book. 1939. Prob. C.64: Six strokes, pp. 140 & 178. 4 x 4 array in 6 segments which form a closed path, though the closure was not asked for.

J. R. Evans. The Junior Week End Book. Op. cit. in 6.AF. 1939. Probs. 30 & 31, pp. 264 & 270. 3 x 3 & 4 x 4 cases in 4 & 6 segments, neither closed nor staying within the array.

Depew. Cokesbury Game Book. 1939. Drawing, p. 220. 4 x 4 in 6 segments, not closed, not staying within the array.

Meyer. Big Fun Book. 1940. Right on the dot, pp. 99 & 732. 4 x 4 in 6 segments.

A. S. Filipiak. Mathematical Puzzles, 1942, op. cit. in 5.H.1, pp. 50 51. Same as Bullivant, but opens the circuit to make a 15 segment path.

M. S. Klamkin, proposer and solver; John L. Selfridge, further solver. Problem E1123 -- Polygonal path covering a square lattice. AMM 61 (1954) 423 & 62 (1955) 124 & 443. Shows N x N can be done in 2N 2 segments. Selfridge shows this is minimal.

W. Leslie Prout. Think Again. Frederick Warne & Co., London, 1958. Joining the stars, pp. 41 & 129. 5 x 5 array of points. Using a line of four segments, pass through 17 points. This is a bit like the 3 x 3 problem in that one must go outside the array.

R. E. Miller & J. L. Selfridge. Maximal paths on rectangular boards. IBM J. Research and Development 4:5 (Nov 1960) 479-486. They study rook's paths where a cell is deemed visited if the rook changes direction there. They find maximal such paths in all cases.

Ripley's Puzzles and Games. 1966. Pp. 72-73, item 2. 4 x 4 cases with closed solution symmetric both horizontally and vertically.

F. Gregory Hartswick. In: H. A. Ripley & F. Gregory Hartswick, Detectograms and Other Puzzles, Scholastic Book Services, NY, 1969. Prob. 4, pp. 42 43 & 82. Asks for 8 x 8 rook's circuit with minimal turning and having a turn at a central cell. Solution gives two such with 16 segments and asserts there are no others.

Doubleday - 1. 1969. Prob. 60: Test case, pp. 75 & 167. = Doubleday - 4, pp. 83-84. Two 3 x 3 arrays joined at a corner, looking like the Fore and Aft board (cf 5.R.3), to be covered in a minimum number of segments. He does it in seven segments by joining two 3 x 3 solutions.

Brian R. Barwell. Arrows and circuits. JRM 2 (1969) 196 204. Introduces idea of maximal length rook's tours. Shows the maximal length on a 4 x 4 board is 38 and finds there are 3 solutions. Considers also the 1 x n board.

Solomon W. Golomb & John L. Selfridge. Unicursal polygonal paths and other graphs on point lattices. Pi Mu Epsilon J. 5 (1970) 107 117. Surveys problem. Generalizes Selfridge's 1955 proof to M x N for which MIN(2M, M+N 2) segments occur in a minimal circuit.

Doubleday - 2. 1971. Path finder, pp. 95-96. Bishop's corner to corner path, same as Dudeney, 1932.

James F. Fixx. More Games for the Superintelligent. (Doubleday, 1972); Muller, (1977), 1981. 6. Variation on a variation, pp. 31 & 87. Trick solution in three lines, assuming points of finite size.

M. Gardner. SA (May 1973) c= Knotted, chap. 6. Prob. 1: Find rook's tours of maximum length on the 4 x 4 board. Cites Barwell. Knotted also cites Peters, below.

Edward N. Peters. Rooks roaming round regular rectangles. JRM 6 (1973) 169 173. Finds maximum length on 1 x N board is N²/2 for N even; (N 1)²/2 + N 1 for N odd, and believes he has counted such tours. He finds tours on the N x N board whose length is a formula that reduces to 4 BC(N+1, 3)   2[(N 1)/2]. I am a bit unsure if he has shown that this is maximal.

James L. Adams. Conceptual Blockbusting. Freeman, 1974, pp. 16-22. 3rd ed., (A-W, 1986), Penguin, 1987, pp. 24-33. Trick solution of 3 x 3 case in three lines, assuming points of finite size, which he says was submitted anonymously when he and Bob McKim used the puzzle on an ad for a talk on problem-solving at Stanford. Also describes a version using paperfolding to get all nine points into a line. The material is considerably expanded in the 3rd ed. and adds several new versions. From the references in Piggins and Eley, it seems that these all appeared in the 2nd ed of 1979 -- ??NYS.

Cut out the 3 x 1 parts and tape them into a straight line.

Take the paper and roll it to a cylinder and then draw a slanting line on the cylinder which goes through all nine, largish, points.

Cut out bits with each point on and skewer the lot with a pencil.

Place the paper on the earth and draw a line around the earth to go through all nine points. One has to assume the points have some size.

Wodge the paper, with large dots, into a ball and stick a pencil through it. Open up to see if you have won -- if not, try again!

Use a very fat line, i.e. as thick as the spacing between the edges of the array.

David J. Piggins. Pathological solutions to a popular puzzle. JRM 8:2 (1975-76) 128-129. Gives two trick solutions.

Three parallel lines, since they meet at infinity.

Put the figure on the earth and use a slanting line around the earth. This works in the limit, but otherwise requires points of finite size, a detail that he doesn't mention.

No references for these versions.

David J. Piggins & Arthur D. Eley. Minimal path length for covering polygonal lattices: A review. JRM 14:4 (1981 82) 279 283. Mostly devoted to various trick solutions of the 3 x 3 case. They cite Piggins' solution with three parallel lines. They say that Gardner sent them the trick solution in 1973 and then cite Adams, 1979. They give solutions using points of different sizes, getting both three and two segment solutions and mention a two segment version that depends on the direction of view. They then give the solution on a sphere, citing Adams, 1979, and Piggins. They give several further versions using paper folding, including putting the surface onto a twisted triangular prism joined at the ends to make the surfaces into a Möbius strip -- Zeeman calls this a umbilical bracelet or a Möbius bar.

Obermair. Op. cit. in 5.Z.1. 1984.

Prob. 19, pp. 23 & 50. Bishop's path on 8 x 8 in 17 segments, as in Dudeney, PCP, 1932.

Prob. 41, p. 72. Rook's path with maximal number of segments, which is 57. [For the 2 x 2, 3 x 3, 4 x 4 boards, I get the maximum numbers are 3, 6, 13.]

Nob Yoshigahara. Puzzlart. Tokyo, 1992. Section: The wisdom of Solomon, pp. 40-47, abridged from an article by Solomon W. Golomb in Johns Hopkins Magazine (Oct 1984). Classic 3 x 3 problem. For the 4 x 4 case: 1) find four closed paths; 2), says there are about 30 solutions and gives 19 beyond the previous 4. Find the unique 5 segment closed path on the 3 x 4. Gives 3 solutions on 5 x 5. 10-segment solution on 6 x 6 which stays on the board. Loyd's 1867? Queen's circuit. Queen's circuit on 7 x 7, attributed to Dudeney, though my earliest entry is Loyd, 1914 -- ??CHECK.