The 15-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The goal of this problem is to transform the arrangement of tiles from the initial arrangement to a goal arrangement.
The legal moves are the moves in which the tiles adjacent to the empty tile are moved to either left, right, up, or down.
Your goal is to find the minimum move to solve the problem.
ouo.
hint
Using BFS/DFS to find answer may exceed memory limit and time limit of some test cases, so we recommend using A* algorithm, which is more efficient. In A* algorithm, it determine the direction of searching by “steps until now + heuristic value”.
A* algorithm: https://en.wikipedia.org/wiki/A*_search_algorithm
To improve heuristic function, you can adopt manhattan distance with Linear Conflict.
Manhattan distance: https://en.wikipedia.org/wiki/Taxicab_geometry
Linear Conflict: The tile set(t1, t2) is linear conflict if they have same goal row(column), and they are now in that row(column), but they are blocked by each other. A set of lenear conflict will cause at least two extra steps.
Input contains 4 lines, each line has 4 numbers.
The given puzzle is guaranteed to contain numbers from 0 ~ 15.
The zero denotes the empty tile.
It is guaranteed that the given puzzle is solvable.
Output the minimum move to solve the puzzle.