Restricting Moves When Solving the NxP-Puzzle

Mohammed Almulla, Monty Newborn

Department of Mathematics and Computer Science, Kuwait University, 13060, Kuwait

School of Computer Science, McGill University, Montreal, Quebec, H3A-2A7, Canada

Abstract

This paper shows that the classic NxP-puzzle can be solved even if moves made by the blank are highly restricted.  In particular, it shows than an NxP-puzzle can be solved when the blank moves only in a clockwise direction and when there is a choice of moves by the blank on only at most minimum(N,P) – 2 squares. For example, a 3x3-puzzle can be solved when the blank moves only in a clockwise direction and when there is a choice of moves by the blank on only one square, and a 4x4-puzzle can be solved when the blank moves only in a clockwise direction and when there is a choice of moves by the blank on only two squares.

1.  Introduction

The NxP-puzzle is a generalization of the famous NxN-puzzle popularized by Sam Loyd in the late nineteenth century [1,2,3]. It is played on a rectangular grid of NxP squares, where N is the number of rows, P is the number of columns, and both N and P are greater than 1. Squares are labeled with integers from 1 to NxP as shown in Fig. 1 for the case of a 3x5-puzzle.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Fig.  1. Labeling squares of the 3x5-puzzle.

On each square but one is a tile labeled with an integer from 1 through NxP – 1.  No two tiles are labeled with the same integer. The single remaining square is blank or empty; for our purposes, it is said to contain the blank.  Fig. 2 presents an example of one possible initial configuration of a 3x5-puzzle.

A move interchanges the blank with one of its neighboring tiles. We usually say the blank moves even though it is actually the tile that moves. A move is described by the direction moved by the blank: up (U), left (L), down (D), and right (R). There are four moves if the blank is not on the edge of the grid, three moves if the blank is on the edge but not in a corner, and two moves if the blank is in a corner.

 6 1 2 4 5 7 3 14 9 11 12 8 13 10

Fig.  2. An initial configuration of a 3x5-puzzle.

When tile i is on square i, it is said to be on its destination square. The objective of the game is, starting with some initial configuration, to move the blank from one square to another until each tile is on its destination square and the blank is on square NxP. The puzzle is then solved. The goal state for the 3x5-puzzle shown in Fig. 2 is shown in Fig. 3.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Fig.   3. The goal state of the 3x5-puzzle.

A puzzle is solved in k moves if k is the number of moves by the blank.  There are, of course, many ways to solve a given puzzle.  Often one is interested in finding a solution requiring the fewest moves [4, 5, 6].  Here, solutions with other properties are of interest.

2.  Inversions and solvable puzzles

There are (NxP)! different initial configurations of an NxP-puzzle; some are solvable and some are not.  The 2x2-puzzle shown in Fig. 4, for example, cannot be solved. We now show how to determine if a puzzle is solvable, and how many of the (NXP)! configurations of an NxP-puzzle are solvable.

 2 1 3

Fig.  4. A 2x2-puzzle that cannot be solved.

We begin by listing the tiles of an NxP-puzzle from square 1 through square.  The tiles of the 3x5-puzzle in Fig. 2 are shown in the top row of Fig.  5. “B” represents the blank square.

We attribute to tile x an inversion if tile x precedes tile y but x is greater than y.  For each tile x, count the number of inversions attributed to that tile. This is done for each tile of the 3x5-puzzle of Fig. 2, and the results are shown in the second row of Fig. 5. The number of inversions for all tiles, denoted NI, of the puzzle is 20.

 Tiles 6 1 2 4 5 7 3 Inversions 5 0 0 1 1 1 0 Tiles B 14 9 11 12 8 13 Inversions - 6 1 2 2 0 1

Fig.  5. Listing of the tiles of the 3x5-puzzle of Fig. 2 and each tile’s inversion number.

Now observe that a left or right move by the blank does not change NI.  Further, if the number of columns is odd, an up or down move by the blank changes NI by an even number. If the number of columns is even, an up or down move by the blank changes NI by an odd number. Thus, for a given puzzle with an odd number of columns, a move by the blank leave the evenness or oddness on NI unchanged.  Similarly, for a puzzle with an even number of columns, a move by the blank leaves the evenness or oddness of (NI + Row of the blank) unchanged.  In the goal state, NI is 0.  This leads to the first theorem:

Theorem 1.   An NxP-puzzle with an odd number of columns can be solved only if NI is an even number.  An NxP-puzzle with an even number of columns and an even number of rows can be solved only if (NI + Row of the blank) is an even number. An NxP-puzzle with an even number of columns and an odd number of rows can be solved only if (NI + Row of the blank) is an odd number.

This theorem implies the puzzle in Fig. 2 is solvable. Observe that for any puzzle, if the tiles on square 1 and square 2 are interchanged, the resulting puzzle is unsolvable if the original puzzle is solvable and visa-versa.  Thus:

Theorem 2.  Exactly half of the (NxP)! initial configurations of an NxP-puzzle are solvable.

This theorem characterizes those puzzles that can be solved, but offers no clue on how to do so. This was done in 1879 by Johnson and Story .

3.  A characterization of moves

Let M1M2 … MS be a sequence of S moves by the blank in an NxP-puzzle; S > 1.  For i > 1, move Mi by the blank is clockwise if it is a right turn relative to its predecessor Mi-1. Counterclockwise moves and straight moves can be similarly defined. (Note: Moves of the blank from one square to another and then directly back to the original square are not considered as they provide no help in solving a puzzle.)

For example, a sequence of eleven moves that solves the 4x4-puzzle of Fig. 4 is ULUL DLDRRDR. Six moves are counter-clockwise — the 2nd, 4th, 5th, 6th, 8th, 9th, and 12th moves — three are clockwise—the 3rd, 6th, and 10th — and one is straight, the 9th.

 1 3 7 4 6 2 8 12 5 9 10 13 14 11 15

Fig.  6. A 4x4-puzzle with a solution ULULDLDRRDR

A sequence of moves by the blank is clockwise if it does not contain any counterclockwise moves —or if the blank does not make any “left turns.” A clockwise sequence of moves by the blank that starts and ends at the same square and moves along the squares of a rectangle is denoted by <s1, s2, s3, s4> where s1, s2, s3, s4 are corner squares of the rectangle.

Observe that if the blank is moved clockwise along the squares of rectangle, it eventually returns to its initial square, and furthermore, if a sufficient number of simple clockwise cycles are made, the other tiles on the cycle eventually find themselves on each square of the cycle.

4.  Solving an NxP-puzzle

A solvable NxP-puzzle can be solved using the following procedure.  For N > 2, solve the top row by first moving, in order, tiles 1, 2, ..., P – 2 to their destination squares.  Once on their destination squares, these tiles never move again. Next, tiles for the rightmost two squares in the row, tiles P – 1 and P, are moved to their destination squares.  Unlike moving tiles 1, 2, …, P – 2 to their destination squares, it may be necessary to move one of these two tiles temporarily off its destination square.  Once all tiles in this top row are on their destination squares, they never move again.

Note that the number of inversions assigned to the tiles in the top row when this step is complete is 0, and thus the number of inversions in the remaining rows must be consistent with a solvable (N – 1)xP-puzzle.

Now, solve all but the remaining rows in a similar manner until a 2xP-puzzle remains.  For the 2xP-puzzle, move tiles NxP – 2P + 1 and NxP – P + 1 to their destination squares, reducing the problem to solving a 2x(P – 1)-puzzle.  A procedure for carrying this out is presented in Section 8.  By solving the final two rows one column at a time, eventually a 2x2-puzzle will remain, which if solvable can be solved as described in Section 7.

5.  The working boundary

As an NxP-puzzle is being solved by the procedure in the previous section, the blank moves in a smaller and smaller working region. It is the tiles within this region that remain to be moved to their destination squares (although some may happen to be already on there). Define the working boundary as those squares on which the blank only has at most three moves within the working region.

 1 2 7 4 6 3 8 5 9 10 12 13 14 11 15

Fig.  7. The working boundary of a 4x4-puzzle with tiles 1 and 2 on their destination squares.

For example, the working boundary of the 4x4-puzzle in Fig. 7, once tiles 1 and 2 have been placed on their   destination   squares, consists of the lightly shaded squares 3,4,8,12,16, 15,14,13,9,5,6.  Note that on square 7, the blank has four moves and thus this square does not qualify as being on the working boundary. The corner squares of the working boundary are the top and bottom squares on the left and right columns.  In Fig. 7, the corner squares are 4,16,13,5.  The top boundary squares are those squares on the working boundary that range across the top of the working boundary.  For the puzzle in Fig. 7, the top working boundary consists of squares 5,6,3,4.

6.  Restricting moves made by the blank

The material that follows shows that every solvable puzzle can be solved by (1) a clockwise sequence of moves by the blank, and (2) all moves by the blank are straight unless the blank on a corner square of the working boundary or on a non-corner square of the bottom row.  Essentially, the blank is restricted to moving clockwise around the working boundary or moving from some square on the bottom row straight up to the working boundary.  We now show how to solve a 2x2-puzzle with these move restrictions, then a 2xP-puzzle, and finally an NxP-puzzle.

7.  2x2-puzzle: move-restricted solutions

Of the 24 possible configurations of a 2x2-puzzle, 12 are solvable; they can be solved by a clockwise rotation of the blank as shown in Fig. 8.  Note that all moves by the blank are consistent with the restrictions described in the previous section.

8.  2xP-puzzle: move-restricted solutions

We now show how to solve a 2xP-puzzle.  For this purpose, we label the squares as shown in Fig. 9 and set the goal state as shown in Fig. 10. Note the tiles are numbered 1, 2, …, P, P + 2, P + 3, …, 2P; there is no tile P + 1. As before, we can list the tiles of a 2xP-puzzle from square 1 through square 2P in line. The tiles of the 2x5-puzzle of Fig. 11,

 1 2 1 2 2 2 2 3 2 3 3 3 1 3 1 3 1 1  1 1 3 1 3 1 3 3 3 2 3 2  2 2 2 1 2 1

Fig.  8. The 12 solvable 2x2-puzzle.

1

2

P – 1

P

2P

2P - 1

P + 2

P + 1

Fig.  9. Labeling of squares of a 2xP-puzzle.

 1 2 … P – 1 P 2P 2P - 1 … P + 2

Fig.  10. The goal state of a 2xP-puzzle.

when listed in a line are as shown in the top row of Fig. 12, where “B” represents the blank square.

As before, we attribute an inversion to tile x if tile x precedes tile y but x is greater than y.  For each tile x, count the total number of inversions attributed to that tile. This is done for each of the tiles of the 2x5-puzzle of Fig. 11, and the numbers are shown in the second row of Fig. 12. The total number of inversions for all tiles, NI, of the puzzle is 16.

 5 3 2 7 10 4 9 1 8

Fig.  11. An initial configuration of a 2x5-puzzle.

 Tiles 5 3 2 7 10 8 1 B 9 4 Inversions 4 2 1 2 4 2 0 - 1 0

Fig.  12. Listing of tiles of the 2x5-puzzle of Fig. 11 and the inversion number of each tile.

For a 2xP-puzzle with the squares labeled as shown here, observe that a left move or a right move by the blank does not change NI.  Further, whether the number of columns is even or odd, an up or down move by the blank changes NI by an even number.  For the goal state, TI is zero, and thus for any solvable state, TI is an even number.  When tiles 1 and 2P are on their destination squares, their inversion numbers are 0, and thus NI for the 2xP-puzzle is the sum of the inversion numbers of the tiles on the remaining 2P – 2 rightmost squares.  For a solvable puzzle, this must be an even number.   Thus for a given solvable 2xP-puzzle, if we can move the blank until tiles 1 and 2P are on their destination squares, the      2x(P – 1)-puzzle defined on the remaining right-most squares remains solvable.

We can thus solve a 2xP-puzzle one column at a time until a final solvable 2x2-puzzle remains.  As shown in the previous section, the final 2x2-puzzle can be solved by a clockwise rotation of the blank, terminating when a solution is obtained.

A procedure is now presented that transfers tiles 1 and 2P to their destination squares for an arbitrary 2xP-puzzle.  Our procedure begins and ends with the blank on square P.  Ending with the blank on square P allows this procedure to be used later in this paper as part of the procedure for solving the more general NxP-puzzle.

1.     If tile 2P is on square 2P, go to step 2.  Otherwise, tile 2P is on some square j where     1 ≤ j < 2P and j ≠ P. If j < P, move the blank clockwise j times along the rectangle <P, P + 1, 2P, 1> until tile 2P is on square 2P and the blank is back on its original square P.  If j > P, move the blank clockwise j - 1 times along the rectangle <P, P + 1, 2P, 1> until tile 2P is on square 2P and the blank is back on its original square P.

2.     If tile 1 is on square 1, the procedure is finished.  Otherwise, tile 1 is on some square k where 2 ≤ k < 2P.  If k < P, move the blank clockwise k - 2 times along the rectangle       <P, P + 1, 2P – 1, 2 > until tile 1 is on square 2 and the blank is back on its original square P. If k > P, move the blank clockwise k - 3 times along the rectangle <P, P + 1, 2P – 1, 2> until tile 1 is on square 2 and the blank is back on its original square P.

3.     Move the blank clockwise 2P - 1 times along the rectangle <P, P + 1, 2P, 1> until tile 1 is on square 3, tile 2P is on square 1 and the blank is back on its original square P.

4.     Move the blank clockwise one time along the rectangle <P, P + 1, 2P – 1, 2> until tile 1 is on square 2 and the blank is back on its original square P.

5.     Move the blank clockwise one time along the rectangle <P, P + 1, 2P, 1> until tile 1 is on square 1, tile 2P is on square 2P and the blank is back on its original square P.  The procedure is now finished.

Note that in carrying out this procedure, there is no choice of moves by the blank except when it is on square 2P – 1.  When on square 2P – 1, the blank moves left or right depending on circumstances.  On all other squares, the blank has no choice of moves.  Thus:

Lemma 1:  Tiles 1 and 2P can be placed on squares 1 and 2P, respectively, of a 2xP-puzzle by a sequence of clockwise moves by the blank where the blank has no choice of moves except on square 2P – 1.  On that square, it moves left or up depending on circumstances.

Theorem 3:  A 2xP-puzzle can be solved by a sequence of clockwise moves by the blank where the blank has no choice of moves except on square P + 2, P + 3, … , 2P – 1.  On these squares, the blank moves left or up depending on circumstances.

9.  NxP-puzzle: move-restricted solutions

Theorem 4.  Every solvable NxP-puzzle can be solved by a clockwise sequence of moves by the blank, and moves by the blank not on the working boundary can be restricted to being straight.  In addition, moves by the blank on the left and right boundary can be restricted to being straight unless the blank is on a boundary corner square.  Lastly, moves by the blank on the top working boundary can be restricted to being straight unless the blank is on a corner square of the working boundary.

A five-step proof by construction follows.

(1) Move the blank to square 1.  Move the blank from its initial square to square 1 by a sequence of clockwise moves.  There are two cases.  If the blank is on the working boundary, move the blank around the squares on the working boundary until it reaches square 1.  If the blank is not on the working boundary, move it up to the working boundary and then move it around the squares of the working boundary until it reaches square 1.     Figs 13 and 14 illustrate these two cases for a 4x4-puzzle.  In Fig. 13, the blank, initially on square 4, is moved to square 1 by the sequence of moves DDDLLLUUU.  In Fig. 14 where the blank is on square 7, the sequence of moves is URDDDLLLUUU.  There are other clockwise sequences of moves — some even shorter — that could move the blank to square 1, but these two sequences satisfy Theorem 4.

After moving the blank to square 1, place tiles 1, 2, … , P on their destination squares in the top row, then place tiles P + 1, P + 2, … , 2P on their destination squares in the second row, and so on in the same order as indicated in procedure presented in Section 4 where an arbitrary NxP-puzzle is solved without move restrictions.

 1 2 3 6 12 10 5 7 8 4 11 15 14 13 12

Fig.  13. Sequence of moves to move the blank from square 4 to square 1: DDDLLLUUU

 1 2 3 10 6 12 5 7 8 4 11 15 14 13 12

Fig.  14. Sequence of moves to move the blank from square 7 to square 1: URDDDLLLUUU

(2) Place tile 1 on square 1.  The blank is now on square 1 after having made a clockwise sequence of moves.  If tile 1 is on the working boundary, move the blank clockwise along the working boundary until tile 1 is on square 1 and the blank is on square 2.  If tile 1 is not on the working boundary but say, in column k, first move the blank counterclockwise along the working boundary until it is on the bottom row on square NxP – P + k.  Then move the blank clockwise along the rectangle <NxP – P + k, k, P, NxP> until tile 1 is on square NxP – P + k and the blank is on square k + 1.  Then move the blank clockwise along the working boundary until tile 1 is on square 1 and the blank is on square 2.

Figs 15 and 16 illustrate these two cases for a 4x4-puzzle.  In Fig. 15, tile 1 is on the working boundary, square 4, and the blank on square 1. The sequence of clockwise moves, (RRRDDDLLLUUU)2R, moves tile 1 to square 1 and leaves the blank on square 2. Note that the sequence uses parentheses to indicate the number of  simple clockwise cycles made by the  blank.  In Fig. 16, tile 1 is on square 11, and the blank is on square 1. The sequence of clockwise moves, RRRDDDLUUUR(DDDLLLUUURRR)5DDDLUUUR, moves tile 1 to square 1 and leaves the blank on square 2. There are other clockwise sequences of moves that could move the blank to square 1, but these two are consistent with the theorems that follow.

 2 3 1 6 12 10 5 7 8 4 11 15 14 13 12

Fig.  15. Sequence of clockwise moves to move tile 1 from square 4 to square 1 and the blank to square 2: (RRRDDDLLLUUU)2R

 2 3 4 6 12 10 5 7 8 1 11 15 14 13 12

Fig.  16. Sequence of clockwise moves to move tile 1 from square 11 to square 1 and the blank to square 2:

RRRDDDLUUUR(DDDLLLUUURRR)5DDDLLLUUUR

(3) Place tiles 2, 3, …, P – 2 on their destination squares. By slightly more complicated routes, place in order tiles 2, 3, …, P – 2 on their destination squares.  The following describes how to place tile 2 on its destination square.  Placing tiles 3, …, P – 2 is done in a similar manner and is not described in this paper.

The previous step left the blank on square 2, after having been moved there by a sequence of moves satisfying Theorem 4.  When placing tile 2, there are three cases to consider depending on the location of tile 2.

(Case 1) If tile 2 is on one of the squares 3, …, P, 2P, 3P, … NxP, NxP – 1, NxP – 2, …,          NxP – P + 2, then move the blank clockwise along the rectangle <2, P, NxP, NxP – P + 2> until tile 2 is on square 2 and the blank is on square 3.

(Case 2) If tile 2 is on one of the squares in column 1, then first move the blank clockwise along the top, then right, then bottom boundaries to square NxP – P + 1.  Then move the blank clockwise along the rectangle <NxP – P + 1, P + 1, 2P, NxP> until tile 2 is on square NxP – P + 3 and the blank is on square NxP – P + 2.  Finally move the blank clockwise along the rectangle <NxP – P + 2 , 2, P, NxP> until tile 2 is on square 2 and the blank is on square 3.

(Case 3) If tile 2 is on one of the other squares in, say, column k, first move the blank clockwise along the top and then the right and then the bottom boundaries until it is on square NxP – P + k.  Then move the blank clockwise along the rectangle <NxP – P + k, k, P, NxP> until tile 2 is on square NxP – P + k and the blank is on square NxP.  Finally, move the blank clockwise along the rectangle <NxP, NxP – P + 2, 2, P> until tile 2 is on square 2 and the blank is on square 3.

Figs 17-19 illustrate these three cases for a 4x4-puzzle.  Fig. 17 illustrates the first case with tile 2 is on square 4 and the blank on square 2.  The sequence of clockwise moves, RR(DDDLLUUURR)3DDDLLUUUR, moves tile 2 to square 2 and leaves the blank on square 3. Fig. 18 illustrates the second case with tile 2 on square 5 and the blank on square 2.  The sequence of clockwise

 1 3 12 6 12 10 5 7 8 4 11 15 14 13 2

Fig.  17. Sequence of clockwise moves by the blank to move tile 2 from square 16 to square 2 and the blank to square 3: RR(DDDLLUUURR)3DDDLLUUUR

 1 3 12 2 12 10 5 7 8 4 11 15 14 13 6

Fig.  18. Sequence of clockwise moves by the blank to move tile 2 from square 16 to square 2 and the blank to square 3: RRD(DDLLLUURRR)3DDLL(UUURRDDDLL)6UUUR

 1 3 12 6 12 2 5 7 8 4 11 15 14 13 10

Fig.  19. Sequence of clockwise moves by the blank to move tile 2 from square 16 to square 2 and the blank to square 3: RR(DDDLUUUR)2(DDDLLUUURR)4DDDLLUUUR

moves, RRD(DDLLLUURRR)3 DDLL(UUURRDDDLL)6UUUR, moves tile 2 to square 2 and leaves the blank on square 3. Fig. 19 illustrates the third case with tile 2 on square 7 and the blank on square 2. The sequence of clockwise moves, RR(DDDLUUUR)2(DDLLUUURR)4 DDDLLUUUR, moves tile 2 to square 2 and the blank to square 3.

(4) Place tiles P – 1 and P on their destination squares.  The following procedure moves tiles P – 1 and P to their destination squares. It begins with the blank on square P – 1 and ends with the blank on square 2P.  Ending with the blank on square 2P allows the remainder of the puzzle to be solved using only permitted moves.

(1)    If tile P – 1 is in either column P – 1 or P, move the blank clockwise along the rectangle <P – 1, P, NxP, NxP – 1> until tile P – 1 is on square P – 1 and the blank is on square 2P; then go to Step 2.  Otherwise, tile P – 1 is in column c for 1 ≤ c < P – 1.  In this case, move the blank clockwise along the working boundary to square NxP – P + c.  Then move the blank clockwise along the rectangle <NxP – P + c, P + c, 2P, NxP> until tile P – 1 is in column P – 1 and the blank is on square NxP.  Then move the blank clockwise along the rectangle <NxP, NxP – 1, P – 1, P> until tile  P – 1 is on square P – 1 and the blank is on square 2P.

(2)    If tile P is on square P, the procedure is finished.  Otherwise: (a) if tile P is on the working boundary, move the blank clockwise along the working boundary until tile P is on square NxP – 2 and the blank is on square NxP. (b) If tile P is in column c not on the working boundary and not on any of the following squares — 3P – 1, 4P – 1, …, (N – 1)P – 1 — in column P  – 1, move the blank clockwise along the rectangle <2P, NxP, NxP – P + c, P + c> until tile P is on square NxP – 2, and the blank is on square NxP.  (c) If tile P is on one of the squares 3P – 1, 4P – 1, …, (N – 1)P – 1, move the blank clockwise down column P to square NxP and then clockwise along the rectangle <NxP, NxP – 1, P – 1, P>  until tile P is on square NxP – 1 and the blank is on square NxP.  Then move the blank clockwise along the rectangle <NxP, NxP – P + 1, P + 1, 2P> until tile P is on square NxP – 2 and the blank is on square NxP.

(3)    Move the blank clockwise along the rectangle <NxP, NxP – 1, P – 1, P> until tile P – 1 is on square NxP – 1 and the blank is on square NxP.

(4)    Move the blank clockwise along the rectangle <NxP, NxP – P + 1, P + 1, 2P> until   tile P – 1 is on square 2P, tile P is on square 3P, and the blank is on square NxP.

(5)    Move the blank clockwise along the rectangle <NxP, NxP – 1, P – 1, P> until tile P – 1 is on square P – 1, tile P is on square P and the blank is on square 2P.  The procedure is now finished.

(5) Solve the bottom two rows.  The previous step, which solves the top row, can be repeated to solve all but the bottom two rows. For the bottom two rows, use the procedure in Section 8.

Theorem 4 essentially states that a solvable NxP-puzzle can be solved even if the blank is given no choice of moves except when on a bottom non-corner square.  For example, a solvable 3x3-puzzle can be solved by a sequence of clockwise moves even if there is no choice of moves except on square 8.  Similarly, a solvable 4x4-puzzle can be solved by a sequence of clockwise moves even if there is no choice of moves except on squares 13 and 14.  More generally, an NxP-puzzle can be solved even if there is no choice of moves except on minimum(N,P) – 2 squares along one bottom or side.  If N < P, simply solve the puzzle column by column instead of row by row.

10.  Conclusions

The restrictions placed on moving the blank by the above theorems do not weaken the “permuting power” of the puzzle.  Of course, solutions found when restricting moves as described usually have far more moves than when moves of the blank are not so restricted.  Programs designed to solve the NxP-puzzle will fail for moderately complex puzzles because of this [4, 5].  Solution lengths of hundreds of moves are common for 4x4-puzzles.

Acknowledgments

This research was supported, in part, by the Canadian Natural Science and Engineering Research Council.  Its support is much appreciated.

 W. W. Johnson and W. E. Story, Notes on the “15” puzzle, American Journal of Mathematics 2 (1879), 397-404.

 F. R. W. Karlemo and P. R. J. Ostergard, On sliding block puzzles, Journal of Combinatorial Mathematics and Combinatorial Computing 34 (2000), 97-107.

 A. Bogomolny, http://www.cut-the-knot.com/pythagoras/fifteen.html.

 R. E. Korf, Depth-first iterative-deepening: An optimal admissible tree search, Artificial Intelligence 27, N. 1, (1985), 97-109.

 R. E. Korf and L. A. Taylor, Finding optimal solutions to the twenty-four puzzle, Proceeding of the 13th National Conference on Artificial Intelligence, AIII Press, Menlo Park (1966) 1202-1207.

 D. Ratner and M. Warmuth, Finding a shortest solution for the (N x N)-extension of the 15-puzzle is intractable, Journal of Symbolic Computing 10, (1990), 111-137.