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 |