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 [1].
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.
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.
[2] F. R. W. Karlemo and P. R. J.
Ostergard, On sliding block puzzles, Journal of Combinatorial Mathematics and
Combinatorial Computing 34 (2000), 97-107.
[3] A. Bogomolny, http://www.cut-the-knot.com/pythagoras/fifteen.html.
[4] R. E. Korf, Depth-first
iterative-deepening: An optimal admissible tree search, Artificial Intelligence
27, N. 1, (1985), 97-109.
[5] 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.
[6] 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.