# 8 puzzle admissible heuristic where tiles are in correct position

For the 8 puzzle problem, it has been proved that if h(n) = number of tiles on wrong place. h(n) is an admissible heuristic as every tile which is in wrong place must be moved out at least once.

But if h(n) = number of tiles on correct place. h(n) is not an admissible heuristic. Can anybody please explain.

• Try to use the definition of admissible heuristic. – Yuval Filmus Dec 9 '18 at 0:54
• can you please elaborate? – jisan Dec 9 '18 at 17:23
• To show that something is not an admissible heuristic, you need to show that it doesn’t satisfy the definition. – Yuval Filmus Dec 9 '18 at 17:24
• yeah, by definition, a heuristic to be admissible to the search problem, the estimated cost must always be lower than or equal to the actual cost of reaching the goal state. So if 7 tiles is in correct place we got h(n) =7 and 1 is in wrong place. We can move this tile by 1 move. In that case, the actual cost is less than h(n). Then it should be admissible heuristic, isn't it. – jisan Dec 11 '18 at 18:57
• An admissible heuristic is one that lower bounds the cost of all possible solutions. If you have to move only 1 tile but your heuristic says 7 tiles, then it’s not admissible. – Yuval Filmus Dec 11 '18 at 20:24