# How to tell if a Heuristic is monotonic

I've applied a Heuristic to a puzzle where I need to move all off the B's the the right of the W's. my Heuristic is the total distance of the B's from the right most W's. my initial state is (B,B,B,*,W,W,W), where * represents a blank space. A piece can move into a blank space and can jump over one or two other pieces into a blank space. I've attached a picture of the graph.

This Heuristic is Admissible because the distance to the goal is ALWAYS more than the distance from the B's to the rightmost W.

The thing I'm not sure of is if this Heuristic is monotonic. My understanding of Monotonic is that the cost of going to an adjacent node plus the estimate of the new node have to be less than the total distance to the goal. How would I determine if this Heuristic is monotonic?

• Although drawing the entire tree can help for a small example to get a basic idea, it is usually better use formal reasoning for the 'real' case, as it can give you an answer for the general problem, including (B,B,B,B,*,W,W,W,W), for example. As for how to show it, I think a proof by contradiction might work: what happens if $h(parent) > cost(parent,child) + h(child)$? Do we arrive at a contradiction? – Discrete lizard Apr 3 '17 at 11:34
• I do not see why the distance to the goal is always more than the distance from the B's to the rightmost W. If we move from (B,B,B,W,W,$\star$,W) to (B,B,$\star$,W,W,B,W) (jumping over 2 W's), then the heuristic function decreases by 3 in a single move. Is there a different cost for moves depending on whether they jump over 0,1, or 2 pieces? – Vincenzo Jan 16 at 13:17