Related Problems: N-Puzzle Type:heuristic function

h = The number of steps it would take to solve the problem if it was possible to swap any tile with the "space".

This heuristic also known as Gaschnig's heuristic. It is an admissible heuristic, since it underestimates the distance function of the problem and gives a closer approximation of the distance.

The heuristic function can be implemented by using 2 arrays:
P – represents the current permutation.
B – the location of element i in the permutation array.


The algorithm: Iteratively swap P[B[n]] with P[B[B[n]]] (for the n-puzzle)

For Example (The 8-Puzzle):

Current state: 29613478
goal state: 123456789 (9 represents the empty space)


Iteration
P
B
1
296134758
415683792
2
926134758
425683791
3
126934758
125683794
4
126439758
125483796
5
129436758
125486793
6
123496758
123486795
7
123456798
123456798
8
123456789
123456789