Heuristic Search : 8-Puzzle Problem

8 puzzle problem

8 puzzle problem searches all possible solution and find the best solution to reach from initial state to goal state. Here, we can move the tiles in left, right, upward and downward direction to satisfy goal state.

Now, calculate the heuristic value.
 Count the number of tiles not in correct place comparing with goal state.
h(D)= 3   ( 2, 3 and 6 are not in place)
h(U)= 3   (8, 5 and 6 are not in place)
h(R)= 3   (4, 5 and 6 are not in place)
h(L)= 1    ( 6 is not in place)
Now, let us find second heuristic value.
Count the number of place tiles away from it's correct position comparing with goal state.
h2(D) = 0(1 is in place) + 1(2 is in one place away) + 0 (3 is in place) + 0 (4 is in place) + 1 (5 is in one place away) + 1  (6 is in one place away) + 0  (7 is in place) + 0  (8 is in place)  = 3
h2(U) = 0+0+0+0+1+1+0+1 = 3
h2(R) = 0+0+0+1+1+1+0+0 = 3
h2(L) = 0+0+0+0+0+1+0+0 = 1
Evaluating both first and second heuristic value, we came to a conclusion that the tile should be moved in left direction to get best solution.