The A* (A-star) algorithm

We want to find the path from a given state of the puzzle in the 8-puzzle game to the final state, by using the A* algorithm.

We supply the computer with the A* algorithm, few heuristic functions and a definition of the "world". The world is represented by:
State space: All the optional 8-puzzles 3x3 with the numbers 0 through 8 when 0 represents the empty Tile.

Rules:

We can move only into the empty tileat most 2 (for corner states), 3 (for . That means for each state there are edge statescenter) options of different moves. As the algorithm goes, we ) or 4 (when the empty tile is in the will have less OP since we will not go back to states already visited, (since in this game we for sure never discover a better and shorter way to reach a visited tile since all moves cost the same(==1).

search algorithm:

We use the A* algorithm. each step as the algorithm goes we will develop the next tile with the minimal calculated f, where f = h + g. g is easy in this case since it is == 1 (the cost of one move). To calculate h we use 3 optional heuristic functions:

Manhattan distance

calculates the sum of the distances in the x and y coordinats for each tile from its current location to the goal position. For a tile in (X, Y) wanting to get to (X',Y') the Man' distance is (|X - X'| + |Y - Y'|). This func returns the sum of this calculation for all tiles.
Admissible: It is trivial to see that a tile most do at least the Man' distance to get to its goal (this is exactly the distance when the Puzzle is empty of other tiles). for this reason this heuristic function is optimistic and Admissible.
Complete : A* always finds the solution if it exists.(since we use an optimistic function and relay on the lemmas that define A* to be complete under this assumptions.
Shortest-Path : Since the function is optimistic, and we are using the A* algo. it will always find the shortest path.

air distance

Like Man' distance, here for each tile we take the air distance to the goal position. for each tile that is: SQRT((X-X')^2 + (Y-Y')^2))
Optimistic : This some is always smaller than the manhattan distance. It is like the Man distance always optimistic, and admissible.
Complete : Will always find a solution (using the A* algo.).
Shortest-Path : As above, since the function is optimistic, and we are using the A* aglo. we will always find the shortest-path.

Number of misplaced tiles

We just count the tiles that are not in the goal position.
Optimistic :For sure, since each tile not in her goal place, gets only a cost of one, which is smaller then the actual cost.
Complete : Will always find a solution (using the A* algo.).
Shortest-Path : As above, since the function is optimistic, and we are using the A* aglo. we will always find the shortest-path.

Analysis:

It is easy to see after a few runs that the Man' function gives the best results, after that the air distance, and at the end the number of misplaced tiles function. WHY??
Func2 (air-distance), is always smaller than Func1 (Man' distance), and since they are both optimistic, and Func2 is more optimistic then Func - 1 it will never give better results then Func-1. In some cases Func-1 and 2 will give the same result, but never will func 2 give better results then 1. Regarding Func-3, (number of misplaced tiles), it gives worst results most of the time, in a difference much bigger then the difference between Func-1 and 2. that is since in this Func, there is no sensitivity to differ between many states that are very different regarding the distance they are from the goal state, yet this Func will give them the same value. this thing is much more rare in the Funt-2 and almost not existing in Func-1.