I tried solving the N puzzle problem using the A* algorithm with the heuristics manhattan distance and number of misplaced tiles. Even though the heuristic no. of misplaced tiles took considerably longer time, the number of moves given by the two methods was equal. Is the number of moves always the same with the two methods or can it be different?

CodePudding user response：

If the heuristic is admissible (i.e. it never overestimates the number of moves still to do), then the solution found by the A* algorithm is guaranteed to be optimal.

The two heuristic functions you only briefly describe seem both to be admissible, so it is expected that in both cases you get the optimal number of moves.