Manhattan distance algorithm implementation in 8 puzzle

Question

Could you please help me in implementing a Manhattan distance euristic algorithm in solving 8 puzzle or give a link where I can find a solution? Thanks in advance.

Answer 1

Manhatten distance:
d=Abs(x1-x2)+Abs(y1-y2)

If you sum this over all pieces and their respective target positions you get a heuristic for the 8 puzzle.
The nice thing about this heuristic is that it never overestimates the distance between two states, and thus makes A* emmit the optimal(i.e. fewest moves) solution.

This heuristic is easily incrementally updatable since you just need just need to subtract the piece heuristic for the old position of the moved piece, and add it for the new position. Or even just check if it got closer, then subtract 1, and if it moved away add 1.

Example code(violates a few conventions like no public fields):

class Piece
{
    public int X;
    public int Y;
    public readonly int Number;

    int TargetX{get{return (Number-1)%3;}}
    int TargetY{get{return (Number-1)/3;}}

    int CalculateDistanceFromGoal()
    {
         int dx=X-TargetX;
         int dy=Y-TargetY;
         return Math.Abs(dx)+Math.Abs(dy);
    }

    public Piece(int number,int x,int y)
    {
        Number=number;
        X=x;
        Y=y;
    }
}


}

int Heuristic(Piece[] pieces)
{
    int result=0;
    foreach(Piece piece in pieces)
    {
        result+=piece.CalculateDistanceFromGoal();
    }
    return result;
}