Sources page biographical material

Hordern's B2, first known from 1973.]

Q. E. D. -- The sergeant's problem, Puzzle no. 40, pp. 106 & 178. Take a 2 x 3 board, with the centre of one long side blank. Interchange the men along one short side. He does this in 17 moves, but the blank is not in its initial position nor are the other men. [This is Hordern's B1, first known from Loyd's Cyclopedia, 1914.]

King. Best 100. 1927. No. 26, p. 15. = Foulsham's, no. 9, pp. 7 & 10. "An entertaining variation ... is to draw, and colour, if you like, a small picture; then cut it into sixteen squares and discard the lower right hand square."

G. Kowalewski. Alte und neue mathematische Spiele. Teubner, Leipzig, 1930, pp. 61 81. Gives solution of general polygonal versions.

Dudeney. PCP. 1932. The Angelica puzzle, prob. 253, pp. 76 & 167. = 435, prob. 378, pp. 136 & 340. B8. 3 x 3 problem -- convert: A C I L E G N A X to A N G E L I C A X. Requires interchanging the As. Solution in 36 moves. In the answer in 435, Gardner notes that it can be done in 30 moves.

H. V. Mallison. Note 1454: An array of squares. MG 24 (No. 259) (May 1940) 119 121. Discusses 15 Puzzle and says any legal position can be achieved in at most about 150 moves. But if one fixes cells 6, 7, 11, then a simple problem requires about 900 moves.

McKay. At Home Tonight. 1940. Prob. 44: Changing the square, pp. 73 & 88. In the usual formation, colour the pieces alternately blue and red, as on a chessboard, with the blank at the lower right position 16 being a missing red, so there are 7 reds. Move so the colours are still alternating but the blank is at the lower left, i.e. position 13. Takes 15 moves.

Sherley Ellis Stotts. US Patent 3,208,753 -- Shiftable Block Puzzle Game. Filed: 7 Oct 1963; patented: 28 Sep 1965. 4pp + 2pp diagrams. Described in Hordern, pp. 152-153, F10 12. Rectangular pieces of different sizes. One can also turn a piece.

Gardner. SA (Feb 1964) = 6th Book, chap. 7. Surveys sliding-block puzzles with non-square pieces and notes there is no theory for them. Describes a number of early versions and the minimum number of moves for solution, generally done by hand and then confirmed by computer. Pennant Puzzle, C19; L'Âne Rouge, C27d; Line Up the Quinties, C4; Ma's Puzzle, D1; a form of Stotts' Baby Tiger Puzzle, F10.

Gardner. SA (Mar & Jun 1965) c= 6th Book, chap. 20. Prob. 9: The eight-block puzzle. B5. 3 x 3 problem -- convert: 8 7 6 5 4 3 2 1 X to 1 2 3 4 5 6 7 8 X. Compares it with Dudeney's Angelica puzzle (1932, B8) but says it can be done if fewer than 36 moves. Many readers found solutions in 30 moves; two even found all 10 minimal solutions by hand! Says Schofield (see next entry) has been working on this and gives the results below, but this did not quite resolve Gardner's problem. William F. Dempster, at Lawrence Radiation Laboratory, programmed a IBM 7094 to find all solutions, getting 10 solutions in 30 moves; 112 in 32 moves and 512 in 34 moves. Notes it is unknown if any problem with the blank in a side or corner requires more than 30 moves. (The description of Schofield's work seems a bit incorrect in the SA solution, and is changed in the book.)

Peter D. A. Schofield. Complete solution of the 'Eight Puzzle'. Machine Intelligence 1 (1967) 125 133. This is the 3 x 3 version of the 15 Puzzle, with the blank space in the centre. Works with the corner twists which take the blank around a 2 x 2 corner in four moves. Shows that the 5-puzzle, which is the 3 x 2 version, has every position reachable in at most 20 moves, from which he shows that an upper bound for the 8-puzzle is 48 moves. Since the blank is in the middle, the 8!/2 = 20160 possible positions fall into 2572 equivalence classes. He also considers having inverse permutations being equivalent, which reduces to 1439 classes, but this was too awkward to implement. An ATLAS program found that the maximum number of moves required was 30 and 60 positions of 12 classes required this maximum number, but no example is given -- but see previous entry.

A. L. Davies. Rotating the fifteen puzzle. MG 54 (No. 389) (Oct 1970) 237 240. Studies versions where the numbers are printed diagonally so one can make a 90^o turn of the puzzle. Then any pattern can be brought to one of two 'natural' patterns. He then asks when this is true for an m x n board and obtains a complicated solution. For an n x n board, n must be divisible by 4.

R. M. Wilson. Graph puzzles, homotopy and the alternating group. J. Combinatorial Thy., Ser. B, 16 (1974) 86 96. Shows that a sliding block puzzle, on any graph of n + 1 points which is non separable and not a cycle, has at least A_n as its group -- except for one case on 7 points.

Alan G. & Dagmar R. Henney. Systematic solutions of the famous 15 14 puzzles. Pi Mu Epsilon J. 6 (1976) 197 201. They develop a test value which significantly prunes the search tree. Kraitchik gave a problem which took him 114 moves -- the authors show the best solution has 58 moves!

David Levy. Computer Gamesmanship. Century Publishing, London, 1983. [Most of the material appeared in Personal Computer World, 1980 1981.] Pp. 16 29 discusses 8 puzzle and uses the Henney's test value as an evaluation function. Cites Schofield.

Nigel Landon & Charles Snape. A Way with Maths. CUP, 1984. Cube moving, pp. 23 & 46. Consider a 9-puzzle in the usual arrangement: 1 2 3, 4 5 6, 7 8 x. Move the 1 to the blank position in the minimal number of moves, ignoring what happens to the other pieces. Generalise. Their answer only says 13 is minimal for the 3 x 3 board.

My student Tom Henley asked me the m x n problem in 1993 and gave a conjectural minimum, which I have corrected to: if m = n, then it can be done in 8m   11 moves; but if n < m, then it can be done in 6m + 2n - 13 moves, using a straightforward method. However, I don't see how to show this is minimal, though it seems pretty clear that it must be. I call this a one-piece problem. See also Ransom, 1993.

Len Gordon. Sliding the 15 1 [sic, but 15 14 must have been meant] puzzle to magic squares. G&PJ 4 (Mar 1988) 56. Reports on computer search to find minimal moves from either ordinary or 15 14 forms to a magic square. However, he starts with the blank before the 1, i.e. as a 0 rather than a 16.

Leonard J. Gordon. The 16 15 puzzle or trapezeloyd. G&PJ 10 (1989) 164. Introduces his puzzle which has a trapezoidal shape with a triangular wedge in the 2nd and 3rd row so the last row can hold 5 pieces, while the other rows hold four pieces. Reversing the last two pieces can be done in 85 moves, but this may not be minimal.

George T. Gilbert & Loren C. Larson. A sliding block problem. CMJ 23:4 (Sep 1992) 315 319. Essentially the same results as obtained by R. Wilson (1974). Guy points this out in 24:4 (Sep 1993) 355-356.

P. H. R. [Peter H. Ransom]. Adam's move. Mathematical Pie 128 (Spring 1993) 1017 & Notes, p. 3. Considers the one piece problem of Langdon & Snape, 1984. Solution says the minimal solution on a n x n board is 8n - 11, but doesn't give the answer for the m x n board.

Bernhard Wiezorke. Sliding caution. CFF 32 (Aug 1993) 24-25 & 33 (Feb 1994) 32. In 1986, the German games company ASS (Altenburg Stralsunder Spielkarten AG) produced a game called Vorsicht (= Caution). Basically this is a 3 x 3 board considered as a doubly crossed square. It has pieces marked with + or x. The + pieces can only move orthogonally; the x pieces can only move diagonally. The pieces are coloured and eight are placed on the board to be played as a sliding piece puzzle from given starts to given ends. The diagonal moves are awkward to make and Wiezorke suggests the board be spread out enough for diagonal moves to be made. A note at the end says he has received two similar games made by Y. A. D. Games in Israel.

Bala Ravikumar. The Missing Link and the Top-Spin. Report TR94-228, Department of Computer Science and Statistics, University of Rhode Island, Jan 1994. The Missing Link is a cylindrical form of the Fifteen Puzzle, with four layers and four pieces in each layer. The middle two layers are rigidly joined, but that makes little difference in solving the puzzle. After outlining the relevant group theory and solving the Fifteen Puzzle, he shows the state space of the Missing Link is S₁₅.

Richard E. Korf & Ariel Felner. Disjoint pattern database heuristics. Artificial Intelligence 134 (2002) 9-22. Discusses heuristic methods of solving the Fifteen Puzzle, Rubik's Cube, etc. The authors applied their method to 1000 random positions of the Fifteen Puzzle. The optimal solution length averaged 52.522 and the average time required was 27 msec. They also did 50 random positions of the Twenty-Four Puzzle and found an average optimal solution length of 100.78, with average time being two days on a 440MHz machine.
5.A.1. NON SQUARE PIECES
S&B, pp. 130 133, show many versions.

See Kinsey, 1878, above, for mention of triangular and diamond shaped pieces.

Henry Walton. US Patent 516,035 -- Puzzle. Applied: 14 Mar 1893; patented: 6 Mar 1894. 1p + 1p diagrams. Described in Hordern, pp. 27 & 68 69, C1. 4 x 4 area with five 1 x 2 & two 2 x 1 pieces.

Lorman P. Shriver. US Patent 526,544 -- Puzzle. Applied: 28 Jun 1894; patented: 25 Sep 1894, 2pp + 1p diagrams. Described in Hordern, p. 27. 4 x 5 area with two 2 x 1 & 15  1 x 1 pieces. Because there is only one vacant space, the rectangles can only move lengthwise and so this is a dull puzzle.

Frank E. Moss. US Patent 668,386 -- Puzzle. Applied: 8 Jun 1900; patented: 19 Feb 1901. 2pp + 1p diagrams. Described in Hordern, pp. 27 28 & 75, C14. 4 x 4 area with six 1 x 1, two 1 x 2 & two  2 x 1 pieces, allowing sideways movement of the rectangles.

William H. E. Wehner. US Patent 771,514 -- Game Apparatus. Applied: 15 Feb 1904; patented: 4 Oct 1904. 2pp + 1p diagrams. First to use L-shaped pieces. Described in Hordern, pp. 28 & 107, D5.

Lewis W. Hardy. US Patent 1,017,752 -- Puzzle. Applied: 14 Dec 1907; patented: 20 Feb 1912. 3pp + 1p diagrams. Described in Hordern, pp. 29 & 89 90, C43-45. 4 x 5 area with one 2 x 2, two 1 x 2, three 2 x 1 & four 1 x 1 pieces.

L. W. Hardy. Pennant Puzzle. Copyright 1909. Made by OK Novelty Co., Chicago. No known patent. Described in Gardner, SA (Feb 1964) = 6th Book, chap. 7 and in Hordern, pp. 28 29 & 78-79, C19. 4 x 5 area with one  2 x 2, two 1 x 2, four 2 x 1, two  1 x 1 pieces.

Nob Yoshigahara designed Rush Hour in the late 1970s and it was produced in Japan as Tokyo Parking Lot. Binary Arts introduced it to the US in 1996 and it became very popular.

Winning Ways. 1982. Pp. 769-777: A trio of sliding block puzzles. This covers Dad's Puzzler (c19, with piece 8 moved two places to the right), The Donkey (C27d, with all the central pieces moved down one position) and The Century (C42), showing how one can examine partial problems which allow one to consider many positions the same and much reduce the number of positions to be studied. This allows the graph to be written on a large sheet and solutions to be readily found.

Andrew N. Walker. Checkmate and other sliding-block puzzles. Mathematics Preprint Series, University of Nottingham, no. 95-32, 1995, 8pp + covers. Describes a version by W. G. H. [Wil] Strijbos made by Pussycat. 4 x 4 with an extra position below the left column. Pieces are alternately black and white and have a black king, a white king and a white rook on them and the object is to produce checkmate, but all positions must be legal in chess, except that the black and white markings do not have to be correct in the intermediate positions. However, one soon finds that one tile is fixed in place and two other tiles are joined together. He discusses general computer solving techniques and finds there are five optimal solutions in 68 moves. He then discusses other problems, citing Winning Ways, Hordern and my Sliding Block Puzzle Circulars. He gives the UNIX shell scripts that he used.

Ivars Peterson. Simple puzzles can give computers an unexpectedly strenuous workout. Science News 162:7 (17 Aug 2002) 6pp PO from their website, http:''sciencenews.org . Reports on recent work by Gary W. Flake & Eric B. Baum that Nob Yoshigahara's Rush Hour puzzle is PSPACE complete, but is not polynomial time. Robert A. Hearn and Erik D. Demaine have verified and extended this, showing other sliding block puzzles are PSPACE complete, including the case where all pieces are dominoes and can slide sideways as well as front and back.

5.A.2. THREE DIMENSIONAL VERSIONS
See Hordern, pp. 27, 156 160 & plates IX & X.
P. G. Tait. Note on the Theory of the "15 Puzzle". Proc. Roy. Soc. Edin. 10 (1880) 664 665. "... conceivable, but scarcely realisable ..."

Charles I. Rice. US Patent 416,344 -- Puzzle. Applied: 9 Sep 1889; patented: 3 Dec 1889. 2pp + 1p diagrams. Described in Hordern, pp. 27 & 157 158, G2. 2 x 2 x 2 version with peepholes in the faces.

Ball. MRE, 1st ed., 1892, p. 78. Mentions possibility.

Hoffmann. 1893. Chap. X, No. 1: The John Bull political puzzle, pp. 331 & 357-358 = Hoffmann-Hordern, pp. 215-216. A 3 x 3 board in the form of a cylinder, with an extra cell attached to one bottom cell. Pieces can move back and forth around each level, but the connections from one level to the next are all parallel to one of the diagonals -- though this isn't really a complication compared to having vertical connections. The pieces have two markings: three colours and three letters. When they are randomly placed on the board, you have to move them so they form a pair of orthogonal 3 x 3 Latin squares. Fortunately there are such arrangements which differ by an odd permutation, so the puzzle can be solved from any random starting point. Two examples done. Says the game is produced by Jaques & Son.

Addison Coe. US Patent 785,665 -- Puzzle or Game Apparatus. Applied: 17 Nov 1904; patented: 1 Mar 1905. 4pp + 3pp diagrams. Mentioned in Hordern, pp. 158 159, G3. Gives a 3 x 5 flat version and a 3 x 3 x 3 cubical version with 3 x 3 arrays of holes in the six faces (in order to push the pieces) and a 3 x 5 cylindrical version.

Burren Loughlin & L. L. Flood. Bright-Wits Prince of Mogador. H. M. Caldwell Co., NY, 1909. The nine disks, pp. 29-34 & 60. Same as Hoffmann except pieces have colour and shape.

Guy thinks Hein patented Bloxbox, but I have not found any US patent of it -- ??CHECK.

Gardner. SA (Feb 1973). First mention of Hein's Bloxbox.

Daniel Kosarek. US Patent 3,845,959 -- Three-Dimensional Block Puzzle. Filed: 14 Nov 1973; patented: 5 Nov 1974. 3pp + 1p diagrams (+ 1p abstract). Mentioned in Hordern, pp. 158 159, G3. 3 x 3 x 3 box with 3 x 3 array of portholes on each face. Mentions 4 x 4 x 4 and larger versions.

Gabriel Nagorny. US Patent 4,428,581 -- Tri-dimensional Puzzle. Filed: 16 Jun 1981; patented: 31 Jan 1984. Cover page + 3pp + 3pp diagrams. Three dimensional sliding cube puzzles with central pieces joined together. A 3 x 3 x 3 version was made in Hungary and marketed as a Varikon Box. Inventor's address is in France and he cites earlier French applications of 19 Jun 1980 and 19 Nov 1980. He also describes a 3 x 4 x 4 version with the central areas of each face joined to a 1 x 2 x 2 block in the middle.

5.A.3. ROLLING PIECE PUZZLES
Here one has a set of solid pieces in a tray and one tilts or rolls a piece into the blank space.
Thomas Henry Ward.

UK Patent 2,870 -- Apparatus for Playing Puzzle or Educational Games. Provisional: 8 Jun 1883; Complete as: An Improved Apparatus to be Employed in Playing Puzzle or Educational Games, 6 Dec 1883. 3pp + 1p diagrams.

US Patent 287,352 -- Game Apparatus. Applied: 13 Sep 1883; patented: 23 Oct 1883. 1p + 1p diagrams. Hexagonal board of 19 triangles with 18 tetrahedra to tilt.

George Mitchell & George Springfield. UK Patent 6867 -- A novel puzzle, and improvements in the construction of apparatus therefor. Applied: 16 Mar 1897; accepted: 5 Jun 1897. 2pp + 1p diagrams. Rolling cubes puzzle, where the cube faces are hollowed and fit onto domes in the tray. Basic form has four cubes in a row with two extra spaces above the middle cubes, but other forms are shown.

Sven Bergling invented the rolling ball labyrinth puzzle/game and they began to be produced in 1946. [Kenneth Wells; Wooden Puzzles and Games; David & Charles, Newton Abbot, 1983, p. 114.]

Ronald Sprague. Unterhaltsame Mathematik. Vieweg, Braunschweig, 1961. Translated by T. H. O'Beirne as: Recreations in Mathematics, Blackie, London, 1963. Problem 3: Schwere Kiste, pp. 3-4 & 22-23 (= Heavy boxes, pp. 4-5 & 25-26). Three problems with 5 boxes some of which are so heavy that one has to tilt or roll them.

Gardner. SA (Dec 1963). = Sixth Book, chap. 8. Gives Sprague's first problem.

Gardner. SA (Nov 1965). c= Carnival, chap. 9. Prob. 1: The red-faced cube. Two problems of John Harris involving one cube with one red face rolling on a chessboard. Gardner says that the field is new and that only Harris has made any investigations of the problem. The book chapter cites Harris's 1974 article, below, and a 1971 board game called Relate with each player having four coloured cubes on a 4 x 4 board.

Charles W. Trigg. Tetrahedron rolled onto a plane. JRM 3:2 (Apr 1970) 82-87. A tetrahedron rolled on the plane forms the triangular lattice with each cell corresponding to a face of the tetrahedron. He also considers rolling on a mirror image tetrahedron and rolling octahedra.

John Harris. Single vacancy rolling cube problems. JRM 7:3 (1974) 220-224. This seems to be the first appearance of the problem with one vacant space. He considers cubes rolling on a chessboard. Any even permutation of the pieces with the blank left in place is easily obtained. From the simple observation that each roll is an odd permutation of the pieces and an odd rotation of the faces of a cube, he shows that the parity of the rotation of a cube is the same as the parity of the number of spaces it has moved. He shows that any such rotation can be achieved on a 2 x 3 board. Rotating one cube 120^o about a diagonal takes 32 moves. If the blank is allowed to move, the the parity of the permutation of the pieces is the parity of the number of spaces the blank moves, but each cube still has to have the parity of its rotation the same as the parity of the number of spaces it has moved. If the identical pieces are treated as indistinguishable, the parity of the permutation is only shown by the location of the blank space. He suggests the use of ridges on the board so that the cube will roll automatically -- this was later used in commercial versions. He gives a number of problems with different colourings of the cubes.

Gardner. SA (Mar 1975). = Time Travel, chap. 9. Prob. 8: Rolling cubes. This is the first of Harris's problems. Computer analysis has found that it can be done in fewer moves than Harris had. Gardner also reports on the last of Harris's problems, which has also been resolved by computer.

A 3 x 3 array with 8 coloured cubes was available from Taiwan in the early 1980s. It was called Color Cube Mental Game -- I called it 'Rolling Cubes'. The cubes had thick faces, producing grooved edges which fit into ridges in the bottom of the plastic frame, causing automatic rolling quite nicely. I wonder if this was inspired by Harris's article.

John Ewing & Czes Kośniowski. Puzzle it Out -- Cubes, Groups and Puzzles. CUP, 1982. The 8 Cubes Puzzle, pp. 58-59. Analysis of the Rolling Cubes puzzle. The authors show how to rotate a single cube about a diagonal in 36 moves.
5.A.4. PANEX PUZZLE
Invented by Toshio Akanuma (??SP). Manufactured by Tricks Co., Japan, in 1983. Described in Hordern, pp. 144-145 & 220, E35, and in S&B, p. 135. This looks like a Tower of Hanoi (cf 7.M.2) with two differently coloured piles of 10 pieces on the outside two tracks of three tracks of height 12 joined like a letter E. This is made as a sliding block puzzle, but with blockages -- a piece cannot slide down a track further than its original position.
Mark Manasse, Danny Sleator & Victor K. Wei. Some Results on the Panex Puzzle. Preprint sent by Jerry Slocum, 23pp, nd [1983, but S&B gives 1985]. For piles of size n, the minimum number of moves, T(n), to move one pile to the centre track is determined by means of a 2nd order, non-homogeneous recurrence which has different forms for odd and even n. Compensating for this leads to a 2nd order non homogeneous recurrence, giving T(10) = 4875 and T(n) ~  C(1 + 2)ⁿ. This solution doesn't ever move the other pile. The minimum number of moves, X(n), to exchange the piles is bounded above and below and determined exactly for n  6 by computer search. X(5) = 343, compared to bounds of 320 and 343. X(6) = 881, compared to the bounds of 796 and 881. For n = 7, the bounds are 1944 and 2189, For n = 10, the bounds are 27,564 and 31,537. The larger bounds are considered as probably correct.

Christoph Hausammann. US Patent 5,261,668 -- Logic Game. Filed: 6 Aug 1992; patented: 16 Nov 1993. 1p abstract + 2pp text + 3pp diagrams. Essentially identical to Panex.

Vladimir Dubrovsky. Nesting Puzzles -- Part I: Moving oriental towers. Quantum 6:3 (Jan/Feb 1996) 53-59 & 49-51. Says Panex was produced by the Japanese Magic Company in the early 1980s. Discusses it and cites S&B for the bounds given above. Sketches a number of standard configurations and problems, leading to "Problem 9. Write out a complete solution to the Panex puzzle." He says his method is about 1700 moves longer than the upper bound given above.

Nick Baxter. Recent results for the Panex Puzzle. 4pp handout at G4G5, 2002. Describes the puzzle and its history. David Bagley wrote a program to implement the Manasse, Sleator & Wei methods. On 7 Feb 2002, this confirmed the conjecture that X(7) = 2189. On 26 Mar 2002, it obtained X(8) = 5359, compared to bounds of 4716 and 5359. It is estimated that the cases n = 9 and 10 will take 10 and 1200 years! If Moore's Law on the increase of computing power continues for another 20 years, the latter answer may be available by then. He gives a simplified version of the algorithm for the upper bound, which gets 31,544 for n = 10. He has a Panex page: www.baxterweb.com/puzzles/panex/ and will be publishing an edited and annotated version of the Manasse, Sleator & Wei paper on it.

5.B. CROSSING PROBLEMS
See MUS I 1-13, Tropfke 658 and also 5.N.
Wolf, goat and cabbages: Alcuin, Abbot Albert, Columbia Algorism, Munich 14684, Folkerts, Chuquet, Pacioli, Tartaglia, van Etten, Merry Riddles, Ozanam, Dilworth, Wingate/Dodson, Jackson, Endless Amusement II, Boy's Own Book, Nuts to Crack, Taylor; The Riddler, Child, Fireside Amusements, Magician's Own Book, Book of 500 Puzzles, Boy's Own Conjuring Book, Secret Out (UK), Mittenzwey, Carroll 1873, Kamp, Carroll 1878, Berg, Lemon, Hoffmann, Brandreth Puzzle Book, Carroll 1899, King, Voggenreiter, Stein, Stong, Zaslavsky, Ascher, Weismantel (a film),

Verse version: Taylor,

Version with only one pair of incompatibles: Voggenreiter

Extension to four items: Gori, Phillips, M. Adams, Gibbs, Ascher

Adults and children: Alcuin, Kamp, Hoffmann, Parker?, Voggenreiter, Gibbs

Three jealous husbands: Alcuin, Abbot Albert, Columbia Algorism, Munich 14684, Folkerts, Rara, Chuquet, Pacioli, Cardan, Tartaglia, H&S   Trenchant, Gori, Bachet, van Etten, Wingate/Kersey, Ozanam, Minguét, Dilworth, Les Amusemens, Wingate/Dodson, Jackson, Endless Amusement II, Nuts to Crack, Young Man's Book, Family Friend, Magician's Own Book, The Sociable, Book of 500 Puzzles, Boy's Own Conjuring Book, Vinot, Secret Out (UK), Lemon, Hoffmann, Fourrey, H. D. Northrop, Mr. X, Loyd, Williams, Clark, Goodstein, O'Beirne, Doubleday, Allen,

Verse mnemonic: Abbot Albert, Munich 14684,

Verse solution: Ozanam, Vinot,

Four or more jealous husbands: Pacioli, Filicaia, Tartaglia, Bachet, Delannoy, Ball, Carroll-Collingwood, Dudeney, O'Beirne

Jealous husbands, with island in river: De Fontenay, Dudeney, Ball, Loyd, Dudeney, Pressman & Singmaster

Missionaries and cannibals: Jackson, Mittenzwey, Cassell's, Lemon, Pocock, Hoffmann, Brandreth Puzzle Book, H. D. Northrop, Schubert, Arbiter, H&S, Abraham, Bile Beans, Goodstein, Beyer, O'Beirne, Pressman & Singmaster.

With only one cannibal who can row: Brandreth Puzzle Book, Abraham, Beyer.

Bigger boats: Pacioli, Filicaia?, Bachet(-Labosne), Delannoy, Ball, Dudeney, Abraham?, Goodstein, Kaplan, O'Beirne,
Alcuin. 9C.

Prob. 17: Propositio de tribus fratribus singulas habentibus sorores. 3 couples, rather earthily expressed.

Prob. 18: Propositio de lupo et capra et fasciculo cauli. Wolf, goat, cabbages.

Prob. 19: Propositio de viro et muliere ponderantibus plaustrum. Man, wife and two small children.

Prob. 20: Propositio de ericiis. Rewording of Prob. 19.

Ahrens. MUS II 315 318, cites many sources, mostly from folklore and riddle collections, with one from the 12C and several from the 14C. ??NYS.

Abbot Albert. c1240.

Prob. 5, p. 333. Wolf, goat & cabbages.

Prob. 6, p. 334. 3 couples, with verse mnemonic.

Columbia Algorism. c1350.

No. 122, pp. 130 131 & 191: wolf, goat, bundle of greens. See also Cowley 402 & plate opposite. P. 191 and the Cowley plate are reproductions of the text with a crude but delightful illustration. P. 130 gives a small sketch of the illustration. I have a colour slide from the MS.

No. 124, p. 132: 3 couples. See also Cowley 403 & plate opposite. The plate shows another crude but delightful illustration. I have a colour slide from the MS.

Munich 14684. 14C.

Prob. XXVI, pp. 82 83: 3 couples, with verse mnemonic.

Prob. XXVII, p. 83: wolf, goat, cabbage.

Folkerts. Aufgabensammlungen. 13-15C. 11 sources with wolf, goat, cabbage. 12 sources with three jealous couples.

Rara, 459 465, cites two Florentine MSS of c1460 which include 'the jealous husbands'. ??NYS.

Chuquet. 1484.

Prob. 163: wolf, goat & cabbages. FHM 233 says that a 12C MS claims that every boy of five knows this problem.

Prob. 164: 3 couples. FHM 233.

Pacioli. De Viribus. c1500.

Ff. 103v - 105v. LXI. C(apitolo). de .3. mariti et .3. mogli gelosi (About 3 husbands and 3 wives). = Peirani 146-148. 3 couples. Says that 4 or 5 couples requires a 3 person boat.

F. IIIv. = Peirani 6. The Index lists the above as Problem 66 and lists a Problem 65: Del modo a salvare la capra el capriolo dal lupo al passar de un fiume ch' non siano devorati (How to save the goat and the kid from the wolf in crossing a river so they are not eaten).

Piero di Nicolao d'Antonio da Filicaia. Libro dicto giuochi mathematici. Early 16C -- ??NYS, mentioned in Franci, op. cit. in 3.A. Franci, p. 23, says Pacioli and Filicaia deal with the case of four or five couples and that Pacioli considers bigger boats, but I'm not clear if Filicaia also does so.

Cardan. Practica Arithmetice. 1539. Chap. 66, section 73, f. FF.v.v (p. 157). (The 73 is not printed in the Opera Omnia). Three jealous husbands.

Tartaglia. General Trattato, 1556, art. 141 143, p. 257r  257v.

Art. 141: wolf, goat and cabbages.

Art. 142: three couples.

Art. 143: four couples -- erroneously -- see Bachet.

H&S 51 says 3 couples occurs in Trenchant (1566), ??NYS.

Gori. Libro di arimetricha. 1571.

Ff. 71r 71v (p. 77). 3 couples.

F. 80v (p. 77). Dog, wolf, sheep, horse to cross river in boat which holds 2, but each cannot abide his neighbours in the given list, so each cannot be alone with such a neighbour.

Bachet. Problemes. 1612. Addl. prob. IV: Trois maris jaloux ..., 1612: 140-142; 1624: 212 215; 1884: 148 153. Three couples; four couples -- notes that Tartaglia is wrong by showing that one can never get five persons on the far side. Labosne gives a solution with a 3 person boat and does n couples with an n 1 person boat.

van Etten. 1624.

Prob. 14: Des trois maistres & trois valets, p. 14. 3 men and 3 valets. (The men hate the other valets and will beat them if given a chance.) (Not in English editions.)

Prob. 15: Du loup, de la chevre & du chou, pp. 14 15. Wolf, goat & cabbages. (Not in English editions.)

Book of Merry Riddles. 1629 72 Riddle, pp. 43-44. "Over a water I must passe, and I must carry a lamb, a woolfe, and a bottle of hay if I carry any more than one at once my boat will sink." Tony Augarde; The Oxford Guide to Word Games; OUP, 1984; p. 6 says wolf, goat, cabbage appears in the 1629 ed.

Wingate/Kersey. 1678?. Prob. 6., p. 543. Three jealous couples. Cf 1760 ed.

Ozanam. 1725.

Prob. 2, 1725: 3 4. Prob. 18, 1778: 171; 1803: 171; 1814: 150. Prob. 17, 1840: 77. Wolf, goat and cabbage.

Prob. 3, 1725: 4 5. Prob. 19, 1778: 171-172; 1803: 171-172; 1814: 150-151. Prob. 18, 1840: 77. Jealous husbands. Latin verse solution. He also discusses three masters and valets: "none of the the masters can endure the valets of the other two; so that if any one of them were left with any of the other two valets, in the absence of his master, he would infallibly cane him."

Minguet. 1733. Pp. 158-159 (1755: 114-115; 1822: 175-176; 1864: 151). Three jealous couples.

Dilworth. Schoolmaster's Assistant. 1743. Part IV: Questions: A short Collection of pleasant and diverting Questions, p. 168.

Problem 6: Fox, goose and peck of corn. = D. Adams; Scholar's Arithmetic; 1801, p. 200, no. 8.

Problem 7: Three jealous husbands. (Dilworth cites Wingate for this -- but this is in Kersey's additions -- cf Wingate/Kersey, 1678? above.) = D. Adams; Scholar's Arithmetic; 1801, p. 200, no. 9.

Les Amusemens. 1749. Prob. 14, p. 136: Les Maris jaloux. Solution is incorrect and has been corrected by hand in my copy.

Edmund Wingate (1596-1656). A Plain and Familiar Method for Attaining the Knowledge and Practice of Common Arithmetic. .... 19th ed., previous ed. by John Kersey (1616-1677) and George Shell(e)y, now by James Dodson. C. Hitch and L. Hawes, et al., 1760.

Art. 749. Prob. VI. P. 379. Three jealous husbands. As in 1678? ed.

Art. 750. Prob. VII. P. 379. Fox, goose and corn.

Jackson. Rational Amusement. 1821. Arithmetical Puzzles.

No. 7, pp. 2 & 52. Fox, goose and corn. One solution.

No. 13, pp. 4 & 54. Three jealous husbands.

No. 21, pp. 5 & 56. Three masters and servants, where the servants will murder the masters if they outnumber them -- i.e. missionaries and cannibals. First appearance of this type.

Endless Amusement II. 1826?

Prob. 17, pp. 198-199. Wolf, goat and cabbage.

Prob. 25, pp. 201-202. Three jealous husbands.

Boy's Own Book. The wolf, the goat and the cabbages. 1828: 418 419; 1828-2: 423; 1829 (US): 214; 1855: 570; 1868: 670.

Nuts to Crack III (1834).

No. 209. Fox, goose and peck of corn.

No. 214. Three jealous husbands.

The Riddler. 1835. The wolf, the goat and the cabbages, pp. 5-6. Identical to Boy's Own Book.

Young Man's Book. 1839. Pp. 39-40. Three jealous Husbands ..., identical to Wingate/Kersey.

Child. Girl's Own Book. 1842: Enigma 49, pp. 237-238; 1876: Enigma 40, p. 200. Fox, goose and corn. Says it takes four trips instead of three -- but the solution has 7 crossings.

Walter Taylor. The Indian Juvenile Arithmetic, or Mental Calculator; to which is added an appendix, containing arithmetical recreations and amusements for leisure hours .... For the author at the American Press, Bombay, 1849. [Quaritch catalogue 1224, Jun 1996, says their copy has a note in French that Ramanujan learned arithmetic from this and that it is not in BMC nor NUC. Graves 14.c.35.] P. 211, No. 8. Wolf, goat and cabbage in verse! No solution.

Upon a river's brink I stand, it is both deep and wide;

With a wolf, a goat, and cabbage, to take to the other side.

Tho' only one each time can find, room in my little boat;

I must not leave the goat and wolf, not the cabbage and the goat.

Lest one should eat the other up, -- now how can it be done --

How can I take them safe across without the loss of one?

Fireside Amusements. 1850: No. 24, pp. 111 & 181; 1890: No. 24, p. 100. Fox, goose and basket of corn.

Family Friend 3 (1850) 344 & 351. Enigmas, charades, etc. -- No. 17: The three jealous husbands.

Magician's Own Book. 1857.

The three jealous husbands, p. 251.

The fox, goose, and corn, p. 253.

The Sociable. 1858. Prob. 33: The three gentlemen and their servants, pp. 296 & 314-315. "None of the gentlemen shall be left in company with any of the servants, except when his own servant is present" -- so this is like the Jealous Husbands. = Book of 500 Puzzles, 1859, prob. 33, pp. 14 & 32-33. = Illustrated Boy's Own Treasury, 1860, prob. 11, pp. 427-428 & 431.

Book of 500 Puzzles. 1859.

Prob. 33: The three gentlemen and their servants, pp. 14 & 32-33. As in The Sociable.

The three jealous husbands, p. 65.

The fox, goose and corn, p. 67.

Both identical to Magician's Own Book.

Boy's Own Conjuring Book. 1860.

The three jealous husbands, pp. 222 223.

The fox, goose, and corn, pp. 225.

Both identical to Magician's Own Book.

Vinot. 1860. Art. XXXVII: Les trois maris jaloux, pp. 56-57. Three jealous husbands, with verse solution taken from Ozanam.

The Secret Out (UK). c1860. A comical dilemma, p. 27. Wolf, goat and cabbage. Varies it as fox, goose and corn and then as gentlemen and servants, which is jealous husbands, rather than the same problem.

Lewis Carroll. Letter of 15 Mar 1873 to Helen Feilden. Pp. 212-215 (Collins: 154-155). Fox, goose and bag of corn. "I rashly proposed to her to try the puzzle (I daresay you know it) of "the fox, and goose, and bag of corn."" Cf Carroll-Collingwood, pp. 212-215 (Collins: 154-155); Carroll-Wakeling, prob. 28, pp. 36-37 and Carroll-Gardner, p. 51. Cf Carroll, 1878. Wakeling writes that this does not appear elsewhere in Carroll.

Bachet-Labosne. 1874. For details, see Bachet, 1612.

Jens Kamp. Danske Folkeminder, Aeventyr, Folksagen, Gaader, Rim og Folketro, Samlede fra Folkemende. R. Neilsen, Odense, 1877. Marcia Ascher has kindly sent me a photocopy of the relevant material with a translation by Viggo Andressen.

No. 18, pp. 326 327: Fox, lamb and cabbage.

No. 19, p. 327: Husband, wife and two half size sons.

Lewis Carroll. Letter of 22 Jan 1878 to Jessie Sinclair. Fox, goose and bag of corn. Cf Carroll-Collingwood, pp. 205-207 (Collins: 150); Carroll-Wakeling, prob. 26: The fox, the goose and the bag of corn, pp. 34 & 72. Cf Carroll. 1872.

Mittenzwey. 1880. Prob. 227-228, pp. 42 & 92; 1895?: 254-255, pp. 46 & 94; 1917: 254 255, pp. 42 & 90. Bear, goat and cabbage, mentioning second solution; three kings and three servants, where the servants will rob the kings if they outnumber them, i.e. like missionaries and cannibals.

Cassell's. 1881. P. 105: The dishonest servants. The servants are rogues who will murder masters if they outnumber them, so this is equivalent to the missionaries and cannibals version.

Lucas. RM1. 1882. Pp. 1-18 is a general discussion of the problem.

De Fontenay. Unknown source and date -- 1882?? Described in RM1, 1882, pp. 15 18 (check 1st ed.??). n > 3 couples, 2 person boat, island in river, can be done in 8n   8 passages. Lucas says this was suggested at the Congrès de l'Association française pour l'avancement des sciences at Montpellier in 1879, ??NYS. (De Fontenay is unclear -- sometimes he permits bank to bank crossings, other times he only permits bank to island crossings. His argument really gives 8n - 6 if bank to bank crossings are prohibited. See Pressman & Singmaster, below, for clarification.)

Albert Ellery Berg, ed. Op. cit. in 4.B.1. 1883. P. 377: Fox, goose & peck of corn.

Lemon. 1890.

Gentlemen and their servants, no. 101, pp. 17 18 & 101. This is the same as missionaries and cannibals.

The three jealous husbands, no. 151, pp. 24 & 103 (= Sphinx, no. 478, pp. 66 & 114.) The solution mentions Alcuin.

Crossing the river, no. 450, pp. 59 & 114. English travellers and native servants = missionaries and cannibals.

Don Lemon. Everybody's Pocket Cyclopedia. Revised 8th ed., 1890. Op. cit. in 5.A. P. 136, no. 14. Fox, goose and corn. No solution.

Herbert Llewelyn Pocock. UK Patent 15,358 -- Improvements in Toy Puzzles. Applied: 29 Sep 1890; complete specification: 29 Jun 1891; accepted: 22 Aug 1891. 2pp + 1p diagrams. Three whites and three blacks and the blacks must never outnumber the whites, i.e. same as missionaries and cannibals. He describes the puzzle as "well known".

Delannoy. Described in RM1, 1891, Note 1: Sur le jeu des traversées, pp. 221 222. ??check 1882 ed. Shows n couples can cross in an x person boat in N trips, for n, x, N  =  2, 2, 5; 3, 2, 11; 4, 3, 9; 5, 3, 11; n > 5, 4, 2n   3. (He has 2n   1 by mistake. Simple modification shows we also have 5, 4, 7; 6, 5, 9; 7, 6, 5; 8, 7, 7; n > 8, n   1, 5.)

Ball. MRE, 1st ed., 1892, pp. 45 47, says Lucas posed the problem of minimizing x for a given n and quotes the Delannoy solution (with erroneous 2n   1) and also gives De Fontenay's version and solution. (He spells it De Fonteney as does his French translator, though Ahrens gives De Fontenay and the famous abbey in Burgundy is Fontenay -- ??)

The Ballybunnion and Listowel Railway in County Kerry, Ireland, was a late 19C railway using the Lartigue monorail system. This had a single rail, about three feet off the ground, with a carriage hanging over both sides of the rail. The principle job of the conductor/guard to make sure the passengers and goods were equally distributed on both sides. Kerry legend asserts that a piano had to be sent on this railway and there were not enough passengers or goods to balance it. So a cow was sent on the other side. At the far end, the piano was unloaded and replaced with two large calves and the carriage sent back. The cow was then unloaded and one calf moved to the other side, so the carriage could be sent back to the far end and everyone was happy.

Hoffmann. 1893. Chap. IV, pp. 157 158 & 211 213 = Hoffmann-Hordern, pp. 136-138, with photos.

No. 56: The three travellers. Masters and servants, equivalent to missionaries and cannibals. Solution says Jaques & Son make a puzzle version with six figures, three white and three black. Photos in Hoffmann-Hordern, pp. 136 & 137 -- the latter shows Caught in the Rain, 1880-1905, where Preacher, Deacon, Janitor and their wives have to get somewhere using one umbrella.

No. 57: The wolf, the goat, and the cabbages. Photo on p. 136 of La Chevre et le Chou. with box, by Watilliaux, 1874-1895. Hordern Collection, p. 72, and S&B, p. 134, show the same puzzle.)

No. 58: The three jealous husbands.

No. 59: The captain and his company. This is Alcuin's prop. 19 with many adults.

Brandreth Puzzle Book. Brandreth's Pills (The Porous Plaster Co., NY), nd [1895].

P. 7: The wolf, the goat and the cabbages. Identical to Hoffmann No. 57, with nice colour picture. No solution.

P. 9: The missionaries' and cannibals' puzzle. Usual form, with nice colour picture, but only one cannibal can row. No solution. This seems to be the first to use the context of missionaries and cannibals and the first to restrict the number of rowers.

Lucas. L'Arithmétique Amusante. 1895. Les vilains maris jaloux, pp. 125-144 & Note II, pp. 198-202.

Prob. XXXVI: La traversée des trois ménages, pp. 125-130. 3 couples. Gives Bachet's 1624 reasoning for the essentially unique solution -- but attributes it to 1613.

Prob. XXXVII: La traversée des quatre ménages, pp. 130-132. 4 couples in a 3 person boat done in 9 crossings.

L'erreur de Tartaglia, pp. 133-134. Discusses Tartaglia's error and Bachet's notice of it and gives an easy proof that 4 couples cannot be done with a 2 person boat.

Prob. XXXVIII: La station dans une île, pp. 135-140. 4 couples, 2 person boat, with an island. Gives De Fontenay's solution in 24 crossings.

Prob. XXXIX: La traversée des cinq ménages, pp. 141-143. 5 couples, 3 person boat in 11 crossings.

Énoncé général du problème des traversées, pp. 143-144. n couples, x person boat, can be done in N crossings as given by Delannoy above. He corrects 2n - 1 to 2n - 3 here.

Note II: Sur les traversées, pp. 198-202. Gives Tarry's version with an island and with n men having harems of size m, where the women are obviously unable to row. He gives solutions in various cases. For the ordinary case, i.e. m = 1, he finds a solution for 4 couples in 21 moves, using the basic ferrying technique that Pressman and Singmaster found to be optimal, but the beginning and end take longer because the women cannot row. He says this gives a solution for n couples in 4n + 5 crossings. He then considers the case of n - 1 couples and a ménage with m wives and finds a solution in 8n + 2m + 7 crossings. I now see that this solution has the same defects as those in Pressman & Singmaster, qv.

Ball. MRE, 3rd ed., 1896, pp. 61 64, repeats 1st ed., but adds that Tarry has suggested the problem for harems -- see above.

Dudeney. Problem 68: Two rural puzzles. Tit Bits 33 (5 Feb & 5 Mar 1898) 355 & 432. Three men with sacks of treasure and a boat that will hold just two men or a man and a sack, with additional restrictions on who can be trusted with how much. Solution in 13 crossings.

Carroll-Collingwood. 1899. P. 317 (Collins: 231 or 232 (missing in my copy)) Cf Carroll-Wakeling II, prob. 10: Crossing the river, pp. 17 & 66. Four couples -- only posed, no solution. Wakeling gives a solution, but this is incorrect. After one wife is taken across, he has another couple coming across and from Bachet onward, this is considered improper as the man could get out of the boat and attack the first, undefended, wife.

E. Fourrey. Op. cit. in 4.A.1, 1899. Section 211: Les trois maîtres et les trois valets. Says a master cannot leave his valet with the other masters for fear that they will intimidate him into revealing the master's secrets. Hence this is the same as the jealous couples.

H. D. Northrop. Popular Pastimes. 1901.

No. 5: The three gentlemen and their servants, pp. 67 & 72. = The Sociable.

No. 12: The dishonest servants, pp. 68 & 73. "... the servants on either side of the river should not outnumber the masters", so this is the same as missionaries and cannibals.

Mr. X [cf 4.A.1]. His Pages. The Royal Magazine 10:2 (Jun 1903) 140-141. A matrimonial difficulty. Three couples. No answer given.

Dudeney. Problem 523. Weekly Dispatch (15 & 29 Nov 1903), both p. 10, (= AM, prob. 375, pp. 113 & 236 237). 5 couples in a 3 person boat.

Johannes Bolte. Der Mann mit der Ziege, dem Wolf und dem Kohle. Zeitschrift des Vereins für Volkskunde 13 (1903) 95-96 & 311. The first part is unaware of Alcuin and Albert. He gives a 12C Latin solution: It capra, fertur olus, redit hec, lupus it, capra transit [from Wattenbach; Neuen Archiv für ältere deutsche Geschichtskunde 2 (1877) 402, from Vorauer MS 111, ??NYS] and a 14C solution: O natat, L sequitur, redit O, C navigat ultra, / Nauta recurrit ad O, bisque natavit ovis (= ovis, lupus, ovis, caulis, ovis) [from Mone; Anzeiger für Kunde der deutschen Vorzeit 45 (No. 105) (1838), from Reims MS 743, ??NYS]. Cites Kamp and several other versions, some using a fox, a sheep, or a lamb. The addendum cites and quotes Alcuin and Albert as well as relatively recent French and Italian versions.

H. Parker. Ancient Ceylon. Op. cit. in 4.B.1. 1909. Crossing the river, p. 623.

A King, a Queen, a washerman and a washerwoman have to cross a river in a boat that holds two. However the King and Queen cannot be left on a bank with the low caste persons, though they can be rowed by the washerperson of the same sex. Solution in 7 crossings.

Ferry-man must transport three leopards and three goats in a boat which holds himself and two others. If leopards ever outnumber goats, then the goats get eaten. So this is like missionaries and cannibals, but with a ferry-man. Solution in 9 crossings.

H. Schubert. Mathematische Mussestunde. Vol. 2, 3rd ed., Göschen, Leipzig, 1909. Pp. 160 162: Der drei Herren und der drei Sklaven. (Same as missionaries and cannibals.)

Arbiter Co. (Philadelphia). 1910. Capital and Labor Puzzle. Shown in S&B, p. 134. Equivalent to missionaries and cannibals.

Ball. MRE, 5th ed., 1911, pp. 71-73, repeats 3rd ed., but omits the details of De Fonteney's solution in 8(n-1) crossings.

Loyd. Cyclopedia, 1914.

Summer tourists, pp. 207 & 366. 3 couples, 2 person boat, with additional complications -- the women cannot row and there have been some arguments. Solution in 17 crossings.

The four elopements, pp. 266 & 375. 4 couples, 2 person boat, with an island and the stronger constraint that no man is to get into the boat alone if there is a girl alone on either the island or the other shore. "The [problem] presents so many complications that the best or shortest answer seems to have been overlooked by mathematicians and writers on the subject." "Contrary to published answers, ... the feat can be performed in 17 trips, instead of 24."

Ball. MRE, 6th ed., 1914, pp. 71-73, repeats 5th ed., but adds that 6n   7 trips suffices for n couples with an island, though he gives no reference.

Williams. Home Entertainments. 1914. Alcuin's riddle, pp. 125-126. "This will be recognized as perhaps the most ancient British riddle in existence, though there are several others conceived on the same lines." Three jealous couples.

Clark. Mental Nuts. 1916, no. 67. The men and their wives. "... no man shall be left alone with another's wife."

Dudeney. AM. 1917. Prob. 376: The four elopements, pp. 113 & 237. 4 couples, 2 person boat, with island, can be done in 17 trips and that this cannot be improved. This is the same solution as given by Loyd. (See Pressman and Singmaster, below.)

Ball. MRE, 8th ed., 1919, pp. 71-73 repeats 6th ed. and adds a citation to Dudeney's AM prob. 376 for the solution in 6n   7 trips for n couples.

Hummerston. Fun, Mirth & Mystery. 1924. Crossing the river puzzles, Puzzle no, 52, pp. 128 & 180. 'Puzzles of this type ... interested people who lived more than a thousand years ago'.

No. 1: The eight travellers. Six men and two boys who weigh half as much.

No. 2: White and black. = Missionaries and cannibals.

No. 3: The fox, the goose, and the corn.

No. 4: the jealous husbands.

H&S, 1927, p. 51 says missionaries and cannibals is 'a modern variant'.

King. Best 100. 1927. No. 10, pp. 10 & 40. Dog, goose and corn.

Heinrich Voggenreiter. Deutsches Spielbuch Sechster Teil: Heimspiele. Ludwig Voggenreiter, Potsdam, 1930.

P. 106: Der Wolf, die Ziege und der Kohlkopf. Usual wolf, goat, cabbage.

Pp. 106-107: Die 100 Pfund-Familie. Parents weigh 100 pounds; the two children weigh 100 pounds together.

P. 107: Der Landjäger and die Strolche [The policeman and the vagabonds]. Two of the vagabonds hate each other so much that they cannot be left together. As far as I recall, this formulation is novel and I was surprised to realise that it is essentially equivalent to the wolf, goat and cabbage version.

Phillips. Week End. 1932. Time tests of intelligence, no. 41, pp. 22 & 194. Rowing explorer with 4 natives: A, B, C, D, who cannot abide their neighbours in this list. A can row. They get across in seven trips.

Abraham. 1933. Prob. 54 -- The missionaries at the ferry, pp. 18 & 54 (14 & 115). 3 missionaries and 3 cannibals. Doesn't specify boat size, but says 'only one cannibal can row'. 1933 solution says 'eight double journeys', 1964 says 'seven crossings'. This seems to assume the boat holds 3. (For a 2 man boat, it takes 11 crossings with one missionary and two cannibals who can row or 13 crossings with one missionary and one cannibal who can row.)

The Bile Beans Puzzle Book. 1933. No. 34: Missionaries & cannibals. Three of each but only one of each can row. Done in 13 crossings.

Phillips. Brush. 1936. Prob. L.2: Crossing the Limpopo, pp. 39 40 & 98. Same as in Week End, 1932.

M. Adams. Puzzle Book. 1939. Prob. C.63: Going to the dance, pp. 139 & 178. Same as Week End, 1932, phrased as travelling to a dance on a motorcycle which carries one passenger.

R. L. Goodstein. Note 1778: Ferry puzzle. MG 28 (No. 282) (1944) 202 204. Gives a graphical way of representing such problems and considers m soldiers and m cannibals with an n person boat, 3 jealous husbands and how many rowers are required.

David Stein. Party and Indoor Games. P. M. Productions, London, nd [c1950?]. P. 98, prob. 5: Man with cat, parrot and bag of seeds.

C. L. Stong. The Amateur Scientist. Ill. by Roger Hayward. S&S, 1960.

A puzzle-solving machine, pp. 377-384. Describes how Paul Bezold made a logic machine from relays to solve the fox, goose, corn problem.

How to design a "Pircuit" or Puzzle circuit, pp. 388-394. On pp. 391-394, Harry Rudloe describes relay circuits for solving the three jealous couples problem, which he attributes to Tartaglia, and the missionaries and cannibals problem.

Nathan Altshiller Court. Mathematics in Fun and in Earnest. Mentor (New American Library), NY, 1961. [John Fauvel sent some pages from a different printing which has much different page numbers than my copy.] "River crossing" problems, pp. 168 171. Discusses various forms of the problem and adds a problem with two parents weighing 160, two children weighing 80 and a dog weighing 12, with a boat holding 160.

E. A. Beyer, proposer; editorial solution. River crossing dilemma. RMM 4 (Aug 1961) 46 & 5 (Oct 1961) 59. Explorers and natives (= missionaries and cannibals), with all the explorers and one native who can row. Solves in 13 crossings, but doesn't note that only one rowing explorer is needed. (See note at Abraham, 1933, above.)

Philip Kaplan. Posers. (Harper & Row, 1963); Macfadden Books, 1964. Prob. 36, pp. 41 & 91. 5 men and a 3 person boat on one side, 5 women on the other side. One man and one woman can row. Men are not allowed to outnumber women on either side nor in the boat. Exchange the men and the women in 7 crossings.

T. H. O'Beirne. Puzzles and Paradoxes, 1965, op. cit. in 4.A.4, chap. 1, One more river to cross, pp. 1 19. Shows 2n   1 couples (or 2n   1 each of missionaries and cannibals ?) can cross in a n person boat in 11 trips. 2n   2 can cross in 9 trips. He also considers variants on Gori's second version.

Doubleday - 2. 1971. Family outing, pp. 49-50. Three couples, but one man has quarrelled with the other men and his wife has quarrelled with the other women, so this man and wife cannot go in the boat nor be left on a bank with others of their sex. Further men cannot be outnumbered by women on either bank. Gives a solution in 9 crossings, but I find the conditions unworkable -- e.g. the initial position is prohibited!

Claudia Zaslavsky. Africa Counts. Prindle, Weber & Schmidt, Boston, 1973. Pp. 109 110 says that leopard, goat and pile of cassava leaves is popular with the Kpelle children of Liberia. However, Ascher's Ethnomathematics (see below), p. 120, notes that this is based on an ambiguous description and that an earlier report of a Kpelle version has the form described below.

Ball. MRE, 12th ed., 1974, p. 119, corrects Delannoy's 2n   1 to 2n   3 and corrects De Fontenay's 8n   8 to 8n   6, but still gives the solution for n = 4 with 24 crossings.

W. Gibbs. Pebble Puzzles -- A Source Book of Simple Puzzles and Problems. Curriculum Development Unit, Solomon Islands, 1982. ??NYS, o/o??. Excerpted in: Norman K. Lowe, ed.; Games and Toys in the Teaching of Science and Technology; Science and Technology Education, Document Series No. 29, UNESCO, Paris, 1988, pp. 54 57. On pp. 56 57 is a series of river crossing problems. E.g. get people of weights 1, 2, 3 across with a boat that holds a weight of at most 3. Also people numbered 1, 2, 3, 4, 5 such that no two consecutive people can be in the boat or left together.

In about 1986, James Dalgety designed interactive puzzles for Techniquest in Cardiff. Their version has a Welshman with a dragon, a sheep and a leek!

Ian Pressman & David Singmaster. Solutions of two river crossing problems: The jealous husbands and the missionaries and the cannibals. Extended Preprint, April 1988, 14pp. MG 73 (No. 464) (Jun 1989) 73 81. (The preprint contains historical and other detail omitted from the article as well as some further information.) Observes that De Fontenay seems to be excluding bank to bank crossings and that Lucas' presentation is cryptic. Shows that De Fontenay's method should be 8n   6 crossings for n > 3 and that this is minimal. If bank to bank crossings are permitted, as by Loyd and Dudeney, a computer search revealed a solution with 16 crossings for n = 4, using an ingenious move that Dudeney could well have ignored. For n > 4, there is a simple solution in 4n + 1 crossings, and these numbers are minimal. [When this was written, I had forgotten that Loyd had done the problem for 4 couples in 17 moves, which changes the history somewhat. However, I now see that Loyd was copying from Dudeney's Weekly Dispatch problem 270 of 23 Apr 1899 & 11 Jun 1899. Loyd states what appears to be a stronger constraint but all the methods in our article do obey the stronger constraint. However, one could make the constraints stronger -- e.g. our solutions have a husband taking the boat from bank to bank while his wife and another wife are on the island -- the solution of Loyd & Dudeney avoids this and may be minimal in this case --??.]

For the missionaries and cannibals problem, the 16 crossing solution reduces to 15 and gives a general solution in 4n   1 crossings, which is shown to be minimal. If bank to bank crossings are not permitted, then De Fontenay's amended 8n   6 solution is still optimal.

Marcia Ascher. A river crossing problem in cultural perspective. MM 63 (1990) 26 28. Describes many appearances in folklore of many cultures. Discusses African variants of the wolf, goat and cabbage problem in which the man can take two of the items in the boat. This is much easier, requiring only three crossings, but some versions say that the man cannot control the items in the boat, so he cannot have the wolf and goat or the goat and cabbage in the boat with him. This still only takes three crossings. Various forms of these problems are mentioned: fox, fowl and corn; tiger, sheep and reeds; jackal, goat and hay; caged cheetah, fowl and rice; leopard, goat and leaves -- see below for more details.

She also discusses an Ila (Zambia) version with leopard, goat, rat and corn which is unsolvable!

Marcia Ascher. Ethnomathematics. Op. cit. in 4.B.10. 1991. Section 4.8, pp. 109-116 & Note 8, pp. 119-121. Good survey of the problem and numerous references to the folklore and ethnographic literature. Amplifies the above article. A version like the Wolf, goat and cabbage is found in the Cape Verde Islands, in Cameroon and in Ethiopia. The African version is found as far apart as Algeria and Zanzibar, but with some variations. An Algerian version with jackal, goat and hay allows one to carry any two in the boat, but an inefficient solution is presented first. A Kpelle (Liberia) version with cheetah, fowl and rice adds that the man cannot keep control while rowing so he cannot take the fowl with either the cheetah or the rice in the boat. A Zanzibar version with leopard, goat and leaves adds instead that no two items can be left on either bank together. (A similar version occurs among African-Americans on the Sea Islands of South Carolina.) Ascher notes that Zaslavsky's description is based on an ambiguous report of the Kpelle version and probably should be like the Algerian or Kpelle version just described.

Liz Allen. Brain Sharpeners. New English Library (Hodder & Stoughton), London, 1991. Crossing the river, pp. 62 & 125. Three mothers and three sons. The sons are unwilling to be left with strange mothers, so this is a rephrasing of the jealous husbands.

Yuri B. Chernyak & Robert S. Rose. The Chicken from Minsk. BasicBooks, NY, 1995. Chap. 1, probs. 4-6: The knights and the pages; More knights and pages; Yet more knights and pages: no man is an island, pp. 4-5 & 100-102. Equivalent to the jealous couples. Prob. 4 is three couples, solved in 11 crossings. Prob. 5 is four couples -- "There is no solution unless one of the four pages is sacrificed. (In medieval times, this was not a problem.)" Prob. 6 is four couples with an island in the river, solved in general by moving all pages to the island, then having the pages go back and accompany his knight to other side, then return to the island. After the last knight is moved, the pages then move from the island to the other side. This takes 7n - 6 steps in general. It satisfies the jealousy conditions used by Pressman & Singmaster, but not those of Loyd & Dudeney.

John P. Ashley. Arithmetickle. Arithmetic Curiosities, Challenges, Games and Groaners for all Ages. Keystone Agencies, Radnor, Ohio, 1997. P. 16: The missionaries and the pirates. Politically correct rephrasing of the missionaries and the cannibals version. All the missionaries, but only one pirate, can row. Solves in 13 crossings.

Prof. Dr. Robert Weismantel, Otto-von-Guericke-Universität Magdeburg, Fakultät für Mathematik, PSF 3120, D-39016 Magdeburg, Germany; tel: [phone]; email: [e-mail]; has produced a 45 min. film: "Der Wolf, die Ziege und Kohlköpfe Transportprobleme von Karl dem Grossen bis heute", suitable for the final years of school.