Project 15 Puzzle · Solving Any Configuration Optimally (Optional)
Lesson 6
Programming problem. Given an even configuration of the 15-puzzle as a permutation of \(\{0, 1, \dotsc, 15\}\), calculate the minimum number of moves needed to solve this configuration.
- Input format. The first line contains 16 integers from \(0\) to \(15\) separated by spaces — the starting configuration of the 15-puzzle. It is guaranteed that the given configuration is solvable in no more than \(30\) moves.
- Output format. The first line of the output should contain a single integer \(t\) — the minimum number of moves required to bring the given configuration to the goal state \((1, \dotsc, 15, 0)\). The next line should contain \(t\) integers separated by spaces describing the moves. Each move is specified by an index \(1 \le i \le 15\) of the piece being moved to the empty cell (the piece \(i\) must be adjacent to the empty cell).
Hint:
You can use Python’s \(\texttt{heapq}\) module to efficiently manage and prioritize puzzle states.
Public samples
Input
1 2 3 4 5 6 7 8 13 9 10 12 14 0 11 15
Expected output
6 14 13 9 10 11 15