solve
Returns the sequence of states from the current puzzle state to the goal state, as determined using the A* search algorithm with Manhattan distance as the heuristic.
A* is an informed search algorithm introduced by Peter E. Hart, Nils J. Nilsson, and Bertram Raphael in the 1968 paper "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," which was published in the IEEE Transactions on System Science and Cybernetics (Volume 4, Issue 2).
The implementation of A* in this function is based on the discussion and pseudocode in the third edition of Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig (2010).
Note that, although the position of the blank tile can be inferred from the puzzle state, it is passed as a parameter in the interest of efficiency (that is, to avoid linear searching).
Return
Sequence of states from the current puzzle state to the goal state.
Parameters
Current puzzle state (flattened into one dimension, following row-major order) and the position of the blank tile in the puzzle grid (zero-based, following row-major order).
Goal state.
Number in columns in the puzzle grid.
Indicator that the tile is blank.