Lesson 7

Programming problem. Given a configuration of the 15-puzzle as a permutation of \(\{0, 1, \dotsc, 15\}\), solve it or determine that it is unsolvable.

• Input format.  The first line contains \(16\) integers from \(0\) to \(15\) separated by spaces — the starting configuration of the 15-puzzle.


• Output format.  The first line of the output should contain a single integer \(t\) such that \(0 \le t \le 10^{5}\) — the number of moves. The next line should contain \(t\) integers separated by spaces — the moves that bring the given configuration to the goal state \((1, \dotsc, 15, 0)\). 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). If the configuration is unsolvable, output \(-1\).

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

-1