Optimal Sliding Puzzle

Graph Search, A*

Given a 4x4 sliding puzzle (the classic 15-puzzle) return the minimum number of blank moves needed to reach the goal configuration. The blank cell is written as 0.

Goal board:

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

Input:

4 lines of 4 integers   (one puzzle)

• Each puzzle uses every number 0-15 exactly once.
• 0 marks the blank; one move is sliding an adjacent tile into the blank.

Output:

• For each puzzle, print the smallest number of moves to solve the puzzle.

Notes:

• Optimal search without a heuristic (plain BFS/Dijkstra) is infeasible on the harder tests.
• A standard A* (see astar.png) with Manhattan-distance heuristic and a visited/closed set easily fits the 2s limit; Python needs similar care (flat arrays/tuples, no recursion).
• Starter code: starter.cpp
• Reference BFS (for comparison only; too slow on hard tests): bfs.cpp
• Every test case is solvable.

Example

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

Output:
4

This puzzle needs four blank moves to place tiles 3 and 0 back into position. The optimal moves are: move 0(empty space) down, and then right, then down, then down.