(Solved): 3. (5 points) Word Search Consider a word search puzzle. Given a starting word, and ending word, ge ...

3. (5 points) Word Search Consider a word search puzzle. Given a starting word, and ending word, generate a sequence of steps between the two by changing a single letter each time. All intermediate words must be real (in the dictionary). For example, with the start and end word pair of (boat, gold), a possible sequence is: $\text{ boat }?\text{ coat }?\text{ colt }?\text{ cold }?\text{ gold. }$ Which search strategy would be better for this problem: depth-first search or breadth-first search? Why? Explain your answer in terms of branching factor and the size of the total state space. Hint: It may help to draw part of the search space.