Kevin's Math Page    
     

Analysis of the Sixteen Puzzle

Kevin Gong

March 28th, 2000; updated August 28th, 2004; updated December 19th, 2005

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:

1
3
2
 

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:

 
3
2
1

In the 3x2 case, this is the worst configuration, requiring 21 moves to win:

4
5
 
1
2
3

In the 4x2 case, this is the worst configuration, requiring 36 moves to win:

 
7
  2
1
4
3
6
5

Addendum, August 2004: In the 5x2 case, these are the worst configurations, each requiring 55 moves to win:

 
5
3
2
1
9
4
8
7
6

 
9
3
7
1
5
4
8
2
6

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:

8
6
7
2
5
4
3
 
1

6
4
7
8
5
 
3
2
1

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:

 
7
  2
1
4
3
6
5

    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:

 
7
  2
1
8
4
6
3
5
9

we could move the 8 past the 1 and 2 to get:

 
7
  8
2
1
4
6
3
5
9

or move the 8 past the 4 and 6 to get:

 
7
  2
1
4
6
8
3
5
9

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:

4
5
 
1
3
2

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:

 
7
  2
1
4
6
3
5

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.

 

 

 Kevin's Math Page    
Copyright © 1996-2016 Kevin L. Gong