# Heuristics for the $n$-puzzle

An admissible heuristic for an n-puzzle is the Manhattan distance. Now if the cost of a transition is equal to the number of the piece that is moved, is it true that the Manhattan distance is still an admissible heuristic?

In my opinion yes, because during the search, for any node, we won't have any overestimation as a misplaced tile will have to move at least the number of spots between itself and the correct position. Is this correct?

And also, would it be correct to say that the Manhattan distance multiplied by the mean of all tiles (eg 8-puzzle -> 4.5) is a heuristic that dominates the Manhattan distance in this case?

Thank you,

(Having troubles with my 1st AI class)

• You already seem to have answered your first question: if you want to check your answers, ask your TA or your fellow students. For the second part, what do you think? What are you stuck on that's stopping you answer the question yourself? – David Richerby Jan 18 '17 at 20:05

First of all, a heuristic is said to be admissible if and only if $h(n)\leq h^*(n)$ for every state $n$, where $h(n)$ is your heuristic function and $h^*(n)$ is the cost of an optimal path from $n$ to the goal.

Now, when considering the sliding-tile puzzle, the Manhattan distance can be shown to be an admissible heuristic function as it results from a constraint relaxation [1].

From here, consider your first question: if the Manhattan distance is an admissible heuristic function for the sliding-tile puzzle where the cost of each movement is 1, it is also an admissible heuristic function for the case where the cost of each movement is strictly greater or equal than 1 (because all tiles are numbered 1 onwards).

Regarding your second question, a heuristic function $h_1(n)$ is said to dominate another heuristic function $h_2(n)$ if and only if $h_1(n)\geq h_2(n)$ for all states $n$. For some restrictive models (a unique goal, constant branching factor, no duplicates, etc.) it can be shown that more informed heuristics (i.e., $h_1(n)$ in the previous definition) expand less nodes when using A$^*$. From here, if you enhance your heuristic function with the average of all tiles, then it is necessarily more informed than pure Manhattan but watch out, it should be easy for you to note that this second heuristic function is not necessarily admissible as it can very easily overestimate the effort to reach the goal. Thus, using this second heuristic it is very likely that you will expand less nodes but you cannot guarantee that the solution returned is optimal.

Hope this helps,

Bibliography

[1] Pearl, Judea. Heuristics - Intelligent Search Strategies for Computer Problem Solving. Addison Wesley, 1984.