50016. 15-Puzzle

I'm a slow walker, but I never walk backwards.

Problem Description

15-Puzzle is a game of moving 15 numbers in a 4 by 4 grid. There are 15 numbers from 1 to 15, each in a grid cell, and the only remaining cell is empty. One can move the number adjacent to the empty cell into it. This will exchange the positions of the empty cell and the number you just moved. Please refer to the following figure. For ease of illustration we use 0 to indicate the empty cell.

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

By moving the 15 to the left, we have the following configuration. If the configure is exactly like this, then we will stop. This is called a "winning configuration".

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

Now given a board, please determine if one can reach the winning configuration within K moves.

Subtasks

  • 10pt. $K$ is $0$.
  • 10pt. $K$ is $1$.
  • 10pt. $K$ is $2$.
  • 60pt. $K$ is no more than $10$.
  • 10pt. $K$ is no more than $15$.

Hints

You can imagine a solution of $K$ moves as a sequence of 0, 1, 2, and 3, in which 0 means moving the empty block up, 1 means down, etc. By "moving the empty block up" we actually mean moving the number above the empty block down. Now we can enumerate all sequences starting with 0, then 1, then 2, recursively. Any of these sequences reaches the winning configuration within $K$ moves is a yes.

To solve the last subtask you need to realize that one move can only move one number into the correct position. If the number of numbers in wrong positions is more than the number of moves left then there could be no solutions.

Sample Input 1

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

Sample Output 1

1
0

Sample Input 2

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

Sample Output 2

1
0

Discussion