The sixteen puzzle is a very well-known, simple puzzle that looks
something like:
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
Fifteen numbered tiles are placed in a 4x4 grid, with one empty
slot. Tiles are moved horizontally or vertically into the empty
slot. The object is to slide the tiles to get to the above configuration.
You can then mix up the tiles and try again.
Several questions can be asked about the puzzle. Note, we can
ask the same questions about similar games on 2x2, 3x3, 2x3, 3x4
boards, etc.:
Let's try to answer these questions now.
|
|
|
DEFINITION: when we refer to the n x m game, we refer the game
played with n x m - 1 tiles placed on a grid with n columns and
m rows |
How many total configurations are there? (n x m)!
This is the simplest question. In an n x m board, there are n
x m - 1 different tiles, and 1 empty slot. The empty slot can
be thought of as the n x mth tile.
Any ordering of the numbers 1 through n x m correspond 1-to-1
with a configuration of the n x m tiles. Thus, for an n x m board
there are (n x m)! configurations.
For a 4 x 4 board, there are 16! different configurations, or
2.092279 x 10^13
Are all configurations legal? No.
In the 2x2 case, it is easy to convince yourself that the following
configuration is illegal:
No matter what you do, it's impossible to swap the 2 and 3.
How many configurations are legal?
In the degenerate n x 1 case, there are clearly only n legal configurations
out of the n! total configurations.
In the more general case, for every n x m puzzle with n, m > 1,
there are exactly (n x m)! / 2 legal configurations. (see proof
below)
Note that it is easy to show that if there are exactly (n x m)!
/ 2 legal configurations, then the (n x m)! / 2 illegal configurations
are equivalent -- if you start with one illegal configuration,
you can get them all by sliding the tiles. (You could easily create
a 1-1 mapping of the illegal and legal configurations).
See the Mathematical Proof section below.
What's the worst legal configuration?
In the n x 1 case, the worst configuration is where the hole is
on the far left and the objective is to move the hole to the far
right. This requires n - 1 moves.
In the 2x2 case, this is the worst configuration, requiring 6
moves to win:
In the 3x2 case, this is the worst configuration, requiring 21
moves to win:
In the 4x2 case, this is the worst configuration, requiring 36
moves to win:
Addendum, August 2004: In the 5x2 case, these are the worst configurations, each requiring 55
moves to win:
One easy observation in the n x 2 case is that in the worst configuration,
the kth tile and the (k + n)th tile are in the same column. Is
this always the case?
In the 3 x 3 case, the following are the worst configurations,
each requiring 31 moves to win:
No pattern is easily discernible, but this problem merits further
study.
What's the average number of moves required?
In the 2x2 case, the average number of moves required is 3.0.
In the 3x2 case, the average number of moves required is 12.6.
In the 4x2 case, the average number of moves required is 22.7.
In the 3x3 case, the average number of moves required is 22.0.
Addendum, August 2004: In the 5x2 case, the average number of moves required is 34.7.
I have not researched the existence of a formula which tells us
this number.
The computer software behind the numbers.
The computer program I wrote to solve these questions was written
in C. It uses transposition tables
to do a complete analysis.
The limiting factor in running the program is not so much time
as it is memory. The program solved the 3 x 3 case in a matter
of seconds, and the 5 x 2 case in a matter of minutes.
Solving the 6 x 2 case would require analyzing 479,001,600
different positions. It could do this in a matter of minutes,
but the problem is that the transposition table requires
479,001,600
different entries, each of which is 28 bytes, so it requires almost
13 GB
of memory. I can see a way of possibly cutting the entries
down to about 16 bytes each, but that wouldn't help much.
Another possibility is using a hard disk to store
the transposition table. This would require a very intelligent
caching algorithm; I'm not sure if it's possible to do that.
If you're interested in transposition tables, a very good book
which describes them is "How Computers Play Chess" by David Levy
and Monty Newborn (W. H. Freeman and Company, 1991).
Mathematical Proof.
Theorems 1 and 2 below combine to show that the puzzle on any
n x m board with n, m > 1 has exactly (n x m)! /2 legal configurations.
|
|
|
THEOREM 1: the puzzle on any n x m board with n, m > 1 has at
most (n x m)! /2 legal configurations. |
Proof:
- Let A[i, j] = the number of the tile on the square in row i, column
j. 1 <= i <= m and 1 <= j <= n. If that square is empty, then
A[i, j] = 0. Otherwise, 1 <= A[i, j] < n x m.
- Consider the permutation: A[1, 1], A[1, 2], ..., a[1, n], A[2,
1], A[2, 2], ..., A[2, n], ..., A[m, n]. This permutation uniquely
defines a configuration. In other words, the set of configurations
can clearly be mapped 1-to-1 with the set of these permutations.
- Let B[k] = A[1 + ((k - 1) / n), 1 + ((k - 1) mod n)]. In this
manner, B[1] = A[1, 1], B[2] = A[1, 2], ..., B[n] = A[1, n], B[n
+ 1] = A[2, 1], ..., B[n x m] = A[m, n].
- Now, let's ignore the empty square. Define C[1, ..., n x m - 1]
= B[1, ...n x m] except for the empty square. So, for example,
if n = 3 and m = 2 and B[] = 1, 2, 4, 3, 0, 5, then C[] = 1, 2,
4, 3, 5
|
|
|
DEFINITION: a permutation D[1...s] has k inversions if D[a] >
D[b] for a < b for k different pairs of a, b. |
For example, the permutation 1, 2, 4, 3 has one inversion(4 >
3). The permutation 3, 1, 2, 4 has two inversions (3 > 1, 3 >
2). 1, 2, 3, 4 has 0 inversions.
|
|
|
THEOREM 1.1a: If n is odd, then every legal configuration corresponds
to a C[] permutation with an even number of inversions. (proved
later)
THEOREM 1.1b: If n is even, then every legal configuration with
the hole in row i where m - i is even corresponds to a C[] permutation
with an even number of inversions. (proved later)
THEOREM 1.1c: If n is even, then every legal configuration with
the hole in row i where m - i is odd corresponds to a C[] permutation
with an odd number of inversions. (proved later) |
|
|
|
THEOREM 1.2: There are n! /2 permutations of size n which have
an even number of permutations. (proved later) |
Suppose n is odd. Based on Theorems 1.1a and 1.2, the illegal
configurations correspond to at least the (n x m - 1)! / 2 permutations
with an odd number of inversions. Each of these permutations corresponds
to n x m different configurations (corresponding to the placing
of the hole in any of the n x m different squares). So this means
there are at least ((n x m - 1)! / 2) x (n x m) = (n x m)! / 2
illegal configurations.
Suppose n is even. By Theorem 1.2, there are (n x m - 1)! / 2
permutations with an odd number of inversions. These correspond
to (n x m) / 2 configurations in which the hole is in row i where
i is even. By Theorem 1.1b, this corresponds to a total of ((n
x m - 1)! / 2) x ((n x m) / 2) = (n x m)! / 4 illegal configurations.
By Theorem 1.2, there are (n x m - 1)! / 2 permutations with an
even number of inversions. These correspond to (n x m) / 2 configurations
in which the hole is in row i where i is odd. By Theorem 1.1c,
this corresponds to a total of ((n x m - 1)! / 2) x ((n x m) /
2) = (n x m)! / 4 illegal configurations. So the total is (n x
m)! / 2 illegal configurations.
STILL TO PROVE: THAT there are at LEAST (n x m)! / 2 legal configurations.
|
|
|
THEOREM 1.1a: If n is odd, then every legal configuration corresponds
to a C[] permutation with an even number of inversions.
THEOREM 1.1b: If n is even, then every legal configuration with
the hole in row i where m - i is even corresponds to a C[] permutation
with an even number of inversions.
THEOREM 1.1c: If n is even, then every legal configuration with
the hole in row i where m - i is odd corresponds to a C[] permutation
with an odd number of inversions. |
Proof of Theorem 1.1:
Starting with the winning configuration, C[] = 1, 2, ..., n x
m - 1, we can reach every other legal configuration by adhering
to the rules of the game. There are only 4 moves to consider:
- Moving a tile to the left. This changes B[] by moving the hole
to the right, but clearly does not change C[] at all, and so does
not change the number of inversions.
- Moving a tile to the right. This changes B[] by moving the hole
to the left, but clearly does not change C[] at all, and so does
not change the number of inversions.
- Moving a tile up. This changes C in the following way: one value
of C[] now comes before n - 1 different values which were before
it. To illustrate:
C[] = 7, 2, 1, 4, 3, 6, 5. Moving the 4 tile up moves it past
3 tiles (n - 1 = 3) to make C[] = 4, 7, 2, 1, 3, 6, 5.
Let T = the value of the tile we're moving. (in the above this
case, T = 4)
Let's examine those n - 1 tiles we moved past. Let's say that
r of those tiles are less than T. Then (n - 1) - r of those tiles
are greater than T. If V was the number of inversions before the
move and W is the number of inversions after the move, then W
= V - ((n - 1 - r) + r = V + 2r - n + 1.
- Moving a tile down. This changes C in the following way: one value
of C[] now comes after n - 1 different vales which were after
it.
Using the same argument in the previous case, we find W = V +
((n - 1 - r) - r = V - 2r + n - 1.
(Theorem 1.1a) If n is odd, then W is clearly always even, and
we are done.
If n is even, then a move up or down always results in W = V +
1 mod 2. Let U = number of up moves and D = number of down moves
to reach a configuration from the winning configuration.
(Theorem 1.1b) If the hole is in row i and m - i is even, then
D - U = 0 mod 2. Therefore, the number of inversions is D x 1
- U x 1 = 0 mod 2. So the configuration must have an even number
of inversions.
(Theorem 1.1c) If the hole is in row i and m - i is odd, then
D - U = 1 mod 2. Therefore, the number of inversions is D x 1
- U x 1 = 1 mod 2. So the configuration must have an odd number
of inversions.
|
|
|
THEOREM 1.2: There are n! /2 permutations of size n which have
an even number of inversions. |
Proof of Theorem 1.2:
The set of permutations with an even number of inversions can
be mapped 1-to-1 with the set of permutations with an odd number
of inversions as follows:
Suppose C[1, ..., n] is a permutation with an even number of inversions.
Then we can create a permutation with an odd number of inversions
by swapping C[n - 1] and C[n]. If C[n - 1] < C[n] we increase
the number of inversions by 1, and if not then we decrease the
number of inversions by 1.
Since the mapping is 1-to-1 and there are n! different permutations,
there are clearly n! / 2 even permutations and n! / 2 odd permutations.
|
|
|
THEOREM 2: the puzzle on any n x m board with n, m > 1 has at
least (n x m)! /2 legal configurations. |
Proof:
|
|
|
THEOREM 2.1: the puzzle on any n x m board with n, m > 1 and n
is odd has at least (n x m)! /2 legal configurations. (proved
later) |
|
|
|
THEOREM 2.2: the puzzle on any n x m board with n, m > 1 and n
is even has at least (n x m)! /2 legal configurations. (proved
later) |
Theorems 2.1 and 2.2 directly prove Theorem 2. QED.
|
|
|
THEOREM 2.1: the puzzle on any n x m board with n, m > 1 and n
is odd has at least (n x m)! /2 legal configurations. |
Proof:
|
|
|
THEOREM 2.1.1: If n is odd, starting with any configuration, we
can form another configuration in which one of the tiles has moved
past two other tiles, including wraparound. (proved later) |
|
|
|
THEOREM 2.1.2: If n is odd, starting with any configuration, we
can move the hole to any square in the grid without affecting
the ordering of the other tiles (including wrapround). (proved
later) |
We will now use Theorems 2.1.1 and 2.1.2 to prove Theorem 2.1
by induction.
Theorem 2.1.2 tells us that we only need to show that we can get
all (n x m - 1)! / 2 permutations with an even number of inversions.
|
|
|
THEOREM 2.1.3: Suppose we start with a permutation with an even
number of inversions. We can move any number in the permutation
past two other numbers in the permutation. Then we can reach all
permutations with an even number of inversions. (proved later) |
From Theorem 2.1.3, we have shown that we can start with the winning
configuration (which has an even number of inversions -- 0) and
reach all the other (n x m - 1)! / 2 even permutations. Theorem
2.1.3 tells us that translates into ((n x m - 1)! / 2) x (n x
m) = (n x m)! / 2 legal configurations. (QED)
|
|
|
THEOREM 2.1.1: If n is odd, starting with any configuration, we
can form another configuration in which one of the tiles has moved
past two other tiles, including wraparound. |
To illustrate, Theorem 2.1.1 states that from the following position:
we could move the 8 past the 1 and 2 to get:
or move the 8 past the 4 and 6 to get:
Proof: Left as an exercise to the reader.
|
|
|
THEOREM 2.1.2: If n is odd, starting with any configuration, we
can move the hole to any square in the grid without affecting
the ordering of the other tiles (including wrapround). |
Proof: Left as an exercise to the reader.
|
|
|
THEOREM 2.1.3: Suppose we start with a permutation with an even
number of inversions. We can move any number in the permutation
past two other numbers in the permutation. Then we can reach all
permutations with an even number of inversions. |
Proof of Theorem 2.1.3:
Base case: Consider the permutation 1, 2, 3. We can use the movement
rule to get all 3 permutations with an even number of inversions:
1, 2, 3
3, 1, 2
2, 3, 1
If we start with an odd permutation, then we can get all the odd
permutations:
1, 3, 2
2, 1, 3
3, 2, 1
Induction case: Suppose that we can reach all the odd permutations
with n numbers from one odd permutation with n numbers, and we
can reach all the even permutations from one even permutation.
Then we can get all the odd permutations for n + 1 numbers from
one odd permutation, and we can get all the even permutations
from one even permutation. Proof:
Consider the permutation 1, 2, 3, ..., n + 1. Since we can get
all even permutations for n numbers, we can make 1 the first number
and rearrange the other numbers, getting all the permutations
with an even number of inversions which start with the number
1.
We can clearly do a series of moves to make any number the first
number. Then the remaining numbers to the right make a permutation
with n numbers with an odd or even number of permutations from
which we can get all others of the same parity. In this manner,
we can reach all permutations of n + 1 numbers with an even number
of inversions.
|
|
|
THEOREM 2.2: the puzzle on any n x m board with n, m > 1 and n
is even has at least (n x m)! /2 legal configurations. |
Proof: Left as an exercise to the reader.
|
|
|
Practical Example: This proof can be used to quickly determine
if a given configuration is legal. |
Consider the following configuration in the 3 x 2 case:
The equivalent permutation is 4, 5, 1, 3, 2. The number of inversions
is 3 + 3 + 1 = 7. n = 3, so n is odd. Therefore, the number of
inversions in a legal configuration must be even. It's not, so
this configuration is illegal.
Here's another example. Considering the following 4 x 2 case:
The equivalent permutation is 7, 2, 1, 4, 6, 3, 5. The number
of inversions is 6 + 1 + 1 + 2 = 10. In this case, n = 4, so n
is even. m = 2 and i = 1, so m - i is odd and we are in case 1.1c
of the proof -> the number of inversions must be odd. They are
not, so this configuration is illegal.
|