Compare the three 8-puzzle heuristics of Figure 4.14 with the heuristic of adding the sum of distances out of place to 2 times the number of direct reversals. Compare them in terms of:

a. Accuracy in estimating distance to a goal. This requires that you first derive the shortest path solution and use it as a standard.

b. Informedness. Which heuristic most effectively prunes the state space?

c. Are any of these three 8-puzzle heuristics monotonic?

d. Admissibility. Which of these heuristics are bounded from above by the actual cost of a path to the goal? Either prove your conclusions for the general case or give a counterexample.