Problem 1: Word Ladder [25 points]

The player is given a start word and an end word(of equal length). In order to win the game, the player must change the start word into the end word progressively, creating an existing word at each step. Each step consists of replacing a single letter. For example, the following is a solution to the Word Ladder puzzle between words "Cold" and "Warm".

A. [10pts] Formulate the problem of solving word ladders as a search problem.

B. [10pts] Consider a restriction where the words can only use the first five letters (a-e). Draw the search graph for coverting "ad" to "be". This page may be helpful.

C. [5pts] Would you prefer to use BFS, DFS, or ID to solve the full problem (with no letter restrictions)? Briefly motivate your choice.

Problem 2: Admissibility [12 points]

A. [2 pts] h(n) = |x*-n.x| + |y*-n.y|

B. [2 pts] h(n) = min(|x*-n.x|,|y*-n.y|)

C. [2 pts] h(n) = max(|x*-n.x|,|y*-n.y|)

D. [2 pts] h(n) = shortest path distance from n to the goal in the original search graph.

E. [2 pts] h(n) = shortest path distance from n to the goal in the original search graph, with new edges added.

F. [2 pts] h(n) = shortest path distance from n to the goal in the original search graph, with some edges removed.

Problem 3: Ordering Pizza [30 points]

• Bill wants peperoni and/or sausage on the pizza
• Thomas wants sausage or green peppers but not both
• If the pizza does not have Canadian bacon, then Jill wants green peppers
• If the pizza has Canadian bacon, then Jessica wants green peppers
• Bob wants Candian bacon or peperoni but not both
• If the pizza has green peppers, then Susan also wants onions

B. [5 pts] Draw the constraint graph for this problem.

C. [5 pts] What about this constraint graph structure makes the problem easy or hard? (For this question, ignore the content of the constraints and just consider the structure of the constraint graph.)

D. [10 pts] Trace the execution of the AC3 algorithm on this problem.