First of all I have seen this answer and yes it explains X-Y heuristic but the example board was too simple for me to understand the general heuristic.
X-Y heuristic function for solving N-puzzle
So could someone please explain the X-Y heuristic using this example?
8 1 2
7 3 6
0 5 4
The algorithm consists of 2 separate parts - for rows and columns.
1) Rows. Divide the input matrix by rows - elements from each row go to separate set.
(1, 2, 8) - (3, 6, 7) - (0, 4, 5)
The only available move is swaping 0 with an element from adjacent set. You finish, when each element is in the proper set.
swap 0 and 7 -> (1, 2, 8) - (0, 3, 6) - (4, 5, 7)
swap 0 and 8 -> (0, 1, 2) - (3, 6, 8) - (4, 5, 7)
swap 0 and 3 -> (1, 2, 3) - (0, 6, 8) - (4, 5, 7)
swap 0 and 4 -> (1, 2, 3) - (4, 6, 8) - (0, 5, 7)
swap 0 and 8 -> (1, 2, 3) - (0, 4, 6) - (5, 7, 8)
swap 0 and 5 -> (1, 2, 3) - (4, 5, 6) - (0, 7, 8)
Number of required steps = 6.
2) Similarly for columns. You start with:
(0, 7, 8) - (1, 3, 5) - (2, 4 ,6)
And then
(1, 7, 8) - (0, 3, 5) - (2, 4, 6)
(0, 1, 7) - (3, 5, 8) - (2, 4, 6)
(1, 3, 7) - (0, 5, 8) - (2, 4, 6)
(1, 3, 7) - (2, 5, 8) - (0, 4, 6)
(1, 3, 7) - (0, 2, 5) - (4, 6, 8)
(0, 1, 3) - (2, 5, 7) - (4, 6, 8)
(1, 2, 3) - (0, 5, 7) - (4, 6, 8)
(1, 2, 3) - (4, 5, 7) - (0, 6, 8)
(1, 2, 3) - (0, 4, 5) - (6, 7, 8)
(1, 2, 3) - (4, 5, 6) - (0, 7, 8)
Number of required steps = 10
3) Total number of steps: 6 + 10 = 16