= Solution
\b[The proposed <Hamming distance> is both an <admissible heuristic> and a <consistent heuristic>.] Write
$$
h(w)=|\{i:w_i\ne t_i\}|.
$$
Every position differing from the target must change at least once along any successful <word ladder>. One mutation changes only one position, so every solution from $w$ has at least $h(w)$ steps. This proves $h(w)\le h^*(w)$, including an unreachable target with $h^*(w)=\infty$. Dictionary restrictions may force extra changes, but cannot remove that lower bound.
Adjacent words differ in one position, so their <Hamming distances> to $t$ differ by at most one. Since every transition costs one,
$$
h(w)\le1+h(w'),\qquad h(t)=0.
$$
These are exactly the <consistent heuristic> conditions. Equivalently, allowing all length-$L$ words gives a <relaxation heuristic> whose exact distance is the <Hamming distance>; restoring the dictionary can only increase the minimum required number of steps.
Back to article page
