Is Manhattan distance still an admissible heuristic in this modified n-puzzle?

Question

I successfully implemented an 8-puzzle solver using the A* algorithm and now I am adding a twist to it: there could be more than one empty space in the puzzle and the numbers on the tiles are no longer unique (there could be numbers that are the same).

While the algorithm works after I modified it to generate successor states for all empty spaces, it didn't solve the game in the smallest number of moves possible (because I actually came up with a smaller number of moves when I tried to solve it by hand, surprise!)

Question: Is Manhattan distance still a viable heuristic in this puzzle? If not, what could the heuristic be?

Answer 1

Yes, an admissible heuristic for this problem can involve Manhattan distance.

The simplest approach is just to take the Manhattan distance to the closest possible target location for each tile.

This is clearly admissible because it's impossible to take less moves to get to any location quicker than directly moving to the closest one with ignoring all obstacles.

But we can do better - for two identical tiles A and B with target positions 1 and 2, rather than calculating the distance to the closest one for each, we can calculate the distance of all possible assignments of tiles to positions, so:

min(dist(A,1) + dist(B,2), dist(A,2) + dist(B,1))

This can be generalized to any number of tiles, but keep in mind that, for n identical tiles, there are n! such possibilities, so it gets quite expensive to calculate quite quickly.

Seeing why this is admissible is still fairly easy - since we're calculating the shortest possible distance for all assignments of tiles to positions, there's no way that the actual shortest distance could be any less.