a simple proof on the solvability of the 15 puzzle (and the extended ones)

We shall show that the 15 puzzle has a (theoretical) solution if the permutation on the pieces is even.

Slide 15 pieces along the loop shown below.

→↓→↓
↑↓↑↓
↑→↑↓
↑←←←

We can replace the aim of this game by the following: Arrange the pieces 1, 2, 3, ..., 15 in this order along this loop.

Move the piece "c" to the right.

ba••
c ••
••••
••••
→
ba••
 c••
••••
••••

Then, the sequence "...abc..." is changed to "...cab...".

Use the move above twice. Then, "...abcd..." → "...adbc..." → "...badc...".

Use this move twice. Then, "...abcdef..." → "...badcef..." → "...bacdfe...". Thrice. "...abcdefgh..." → "...badcefgh..." → "...bacdfegh..." → "...bacdefhg...".

Consider "...ab...cd...". If the number of the pieces after "ab" and before "cd" is odd, then the number of the pieces after "cd" and before "ab" is even, because the total number of the pieces is odd. (Or, ...abxcd... → ...abdxc... → ...axbdc... → ...baxdc..., and so on.)

Now we know that we can transpose arbitrary pairs of adjacent pairs simultaneously. i.e. "...ab...cd..." → "...ba...dc...".

The rest is almost clear for the readers who are familiar with the symmetric group and the sign of its elements. First, use these moves and make the pieces 14 and 15 adjacent. Then, transpose the pair {14, 15} and the adjacent pairs in {1, 2, 3, ..., 13} which you want to transpose simultaneously. Repeat it until you have the sequence 1, 2, ..., 14, 15 (succeeded) or the sequence 1, 2, ..., 15, 14 (failed).

3×3 - 1 puzzle

First, fix the piece 1.

1••
•••
•••

Then, move along the loop below.

1→↓
→↑↓
↑←←

Note that the number of the pieces moving along the loop is odd.

N×N - 1 puzzle (N odd, > 3)

First, fix the center piece (shown by "*").

•••••••
•••••••
•••••••
•••*•••
•••••••
•••••••
•••••••

Then, move along the loop below.

→→↓→→→↓
↑↓←↑←←↓
↑↓→→↓↑↓
↑↓↑*↓↑↓
↑↓↑↓←↑↓
↑→↑→→↑↓
↑←←←←←←
=
→→→→→→↓
↑     ↓
↑     ↓
↑     ↓
↑     ↓
↑     ↓
↑←←←←←←
+
↓←←←←
↓   ↑
↓   ↑
↓   ↑
→→→→↑
+
→→↓
↑*↓
↑←←

or

*→→→→→↓
→↑↓←↓←↓
↑←←↑↓↑↓
→→→↑↓↑↓
↑←←←←↑↓
→→→→→↑↓
↑←←←←←←
=
*→↓    
→↑↓    
↑←←    
       
       
       
       
+
   →↓  
   ↑↓  
   ↑↓  
→→→↑↓  
↑←←←←  
       
       
+
     →↓
     ↑↓
     ↑↓
     ↑↓
     ↑↓
→→→→→↑↓
↑←←←←←←

2×N - 1 puzzle (N ≥ 2)

Move along the loop below.

→→→→↓
↑←←←←

M×N - 1 puzzle (N even, ≥ 4)

Move along the loop below.

→↓→↓→↓
↑↓↑↓↑↓
↑↓↑↓↑↓
↑→↑→↑↓
↑←←←←←

M×N - 1 puzzle (M, N odd, ≥ 3, M ≠ N)

We may assume that M < N. Note that N - M is even.

→↓→→↓
↑↓↑←↓
↑↓*↑↓
↑→→↑↓
↑←←←←
 +
→↓→↓→↓
↑↓↑↓↑↓
↑↓↑↓↑↓
↑→↑→↑↓
↑←←←←←
 =
→↓→→↓→↓→↓→↓
↑↓↑←↓↑↓↑↓↑↓
↑↓*↑→↑↓↑↓↑↓
↑→→↑↓←→↑→↑↓
↑←←←←↑←←←←←

cf. (123)(234) = (12)(34), (123)(234)(345) = (12)(45).

See «a strange sort algorithm related to the 15 puzzle (and the extended ones)» for a little bit more practical solution.

See also «a C program solving the 15 puzzle».

Sunomono