CODEWITHSUNDEEP
algorithmheuristics
Justin Jankunas
Justin Jankunas

Reputation: 3

X-Y Heuristic on the N-Puzzle

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

Upvotes: 0

Views: 883

Answers (1)

mateuszlo
mateuszlo

Reputation: 1419

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

Upvotes: 4

Related Questions