The “15 puzzle” is a grid of numbered sliding tiles where one can continue to slide tiles up, down, left or right into an unoccupied blank space until a solution state is achieved, e.g.:
1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 |
13 | 14 | 15 |
Not all initial configurations are solvable. That is, there may not be a series of tile-slides that result in the solution state. How can you determine if a given state is solvable?
4 | 14 | 2 | |
5 | 9 | 15 | 1 |
11 | 12 | 3 | 10 |
8 | 7 | 13 | 6 |