Past exam of the computer science course of the University of Oxford / 2020 / Artificial intelligence / 1 / c / 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^{\prime }\in D_L$. The search transition model returns that $w^{\prime }$, 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$ hasThus 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.