I have a modified 8 puzzle problem such that each transition's cost is associated with the number of the piece that is moved. So, for example, if piece 3 is moved, the move would cost 3 units. I am trying to find an admissible heuristic that dominates the Manhattan distance, but am having trouble deriving one.My thoughts:Since the Manhattan distance gives us the distance of any tile from its end goal, wouldn't a heuristic that dominates the Manhattan distance not be admissible? For example, if a piece is 1 state away from its goal state, how can there be an admissible heuristic that is $>=$ 1 for that piece?
8 puzzle admissible heuristic that dominates Manhattan distance?
algorithms;search algorithms;heuristics