Manhattan distance heuristic
There is an easy lower bound on #moves required
Just calculate how far each piece is from its goal
- add up this for each piece
- sum is minimum number of moves possible
This is Manhattan distance
- because pieces move according to Manhattan geometry
Can use it as heuristic as estimate of distance to solution
- makes sense to explore apparently nearest first