I have built an 8 puzzle solver using Breadth First Search. I would now want to modify the code to use heuristics. I would be grateful if someone could answer the following two questions:

**Solvability**

How do we decide whether an 8 puzzle is solvable? (given a starting state and a goal state ) This is what Wikipedia says:

The invariant is the parity of the permutation of all 16 squares plus the parity of the taxicab distance (number of rows plus the number of columns) of the empty square from the lower right corner.

Unfortunately, I couldn't understand what that meant. It was a bit complicated to understand. Can someone explain it in a simpler language?

**Shortest Solution**

Given a heuristic, is it guaranteed to give the shortest solution using the A* algorithm? To be more specific, will the first node in the open list always have a depth ( or the number of movements made so fat ) which is the minimum of the depths of all the nodes present in the open list?

Should the heuristic satisfy some condition for the above statement to be true?

*Edit:* How is it that an admissible heuristic will always provide the optimal solution? And **how do we test whether a heuristic is admissible?**

I would be using the heuristics listed __here__

Manhattan Distance Linear Conflict Pattern Database Misplaced Tiles Nilsson's Sequence Score N-MaxSwap X-Y Tiles out of row and column

For clarification from Eyal Schneider :