= Solution
Let the input words be $s,t$, let $L$ be their common length, let $\Sigma$ be the finite <alphabet>, and let $D_L$ contain the dictionary words of length $L$. Unequal input lengths immediately make the puzzle impossible because a mutation preserves length. A <word ladder> <search problem> can use the <state space> $S=D_L\cup\{s\}$, with initial state $s$; including $s$ handles an input word not itself in the dictionary.
At word $w$, an action is a position–letter pair $(i,\ell)$ with $1\le i\le L$, $\ell\in\Sigma$ and $\ell\ne w_i$, permitted precisely when replacing $w_i$ by $\ell$ gives $w'\in D_L$. The <search transition model> returns that $w'$, and the <goal test> is $w=t$. If $s=t$, the empty sequence is accepted; if $t\notin D_L$ and $s\ne t$, no transition can reach $t$.
Assign each permitted transition cost $1$. A <search node> at <search depth> $k$ has
$$
\boxed{g(n)=\sum_{j=1}^{k}1=k.}
$$
Thus minimizing <path cost> is exactly minimizing the number of mutations. <Uniform-cost search>, with repeated states handled by <graph search> and the <goal test> on selection, finds a shortest <word ladder> if one exists. Because all costs are equal, <breadth-first search> gives the same optimal-length guarantee.
Back to article page
