Search code examples
javaalgorithmsliding-tile-puzzle

Solving the 8 puzzle using A* - how to break ties?

Currently working on solving the 8 puzzle using an A* algorithm. The assignment asks that we use the A* algorithm with the Manhattan priority to solve the puzzle. But I can across this particular scenario where there's a tie between the two possible neighbor boards (see below), how do I proceed?

Starting with

{{2,3,5}, {1,0,4}, {7,8,6}}

Eventually we come down to choosing between these two:

enter image description here

If we choose to break the tie by using the Hamming distance, the 2nd choice would be chosen and will not lead us to the solution, but how do we know we should choose the first board?

Solution

  • Made the mistake of thinking the solution is gonna be the sequence of boards dequeued. Turns out you have to back track from the goal board when it's dequeued, problem solved!