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.