Problem definition:

An 8 puzzle is a simple game consisting of a 3 x 3 grid (containing 9 squares). One of the squares is empty. The object is to move to squares around into different positions and having the numbers displayed in the “goal state”.

Given an initial state of 8-puzzle game and a final state of to be reached, find the most cost-effective path to reach the final state from initial state.

Initial state:

_ 1 3
4 2 5
7 8 6

Final state:

1 2 3
4 5 6
7 8 _

Heuristic to be assumed:

Let us consider the Manhattan distance between the current and final state as the heuristic for this problem statement.

h(n) = | x - p | + | y - q |
where x and y are cell co-ordinates in the current state
      p and q are cell co-ordinates in the final state

Total cost function:

So the total cost function f(n) is given by,

f(n) = g(n) + h(n), where g(n) is the cost required to reach the current state from given initial state

Solution to example problem:

First we find the heuristic value required to reach the final state from initial state. The cost function, g(n) = 0, as we are in the initial state

h(n) = 8

The above value is obtained, as 1 in the current state is 1 horizontal distance away than the 1 in final state. Same goes for 2, 5, 6. \\_ is 2 horizontal distance away and 2 vertical distance away. So total value for h(n) is 1 + 1 + 1 + 1 + 2 + 2 = 8. Total cost function f(n) is equal to 8 + 0 = 8.

Now, the possible states that can be reached from initial state are found and it happens that we can either move \\_ to right or downwards.

So states obtained after moving those moves are: