# Checking consistency and admissibility of heuristic functions

Consider the following question:

n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n × n grid. The vehicles must be moved to the top row but in reverse order; so the vehicle i that starts in (i, 1) must end up in (n − i + 1, n). On each time step, every one of the n vehicles can move one square up, down, left, or right, or stay put; but if a vehicle stays put, one other adjacent vehicle (but not more than one) can hop over it. Two vehicles cannot occupy the same square.

Suppose that each heuristic function $$h_i$$ is both admissible and consistent. Now what I want to know is to check the admissibility and consistency of the following heuristics:

1. $$h= \Sigma_i h_i$$

2. $$h= min_i (h_i)$$

3. $$h= max_i (h_i)$$

4. $$h = \frac{\Sigma_i h_i}{n}$$

P.S: As a lemma, we now that consistency implies the admissibility of the heuristic function .

## Problem Explanation:

From this link, I have found that the first heuristic is neither admissible, nor consistent.

I know that the second and the fourth heuristics are either consistent, or admissible.

I have faced with one contradiction in the third heuristic: Here we see that if car 3 hops twice, the total cost of moving all the cars to their destinations is 3, whereas the heuristic $$max(h_1, ..., h_n) = 4$$.

Problem:

As a lemma we now that, consistency of a heuristic function implies the admissibility. We now that all heuristics are both admissible and consistent. So $$max(h_1, ..., h_n)$$ must be consistent and admissible, but the above example shows that it's not. What is my mistake?