CS101 - Assignment 7

In this assignment, you will use a search strategy to solve a puzzle. First, let’s describe the puzzle.

Six frogs are trying to cross a pond by jumping between stones. Alma, Ben, and Carl are heading East; while Xavier, Yolanda, and Zora are heading West. Their initial positions are illustrated in the image.

Each frog can jump onto an adjacent stone, or jump over one other frog if there is an empty stone on the other side. The frogs are stubborn, however, and are not willing to change direction!

Start state for the frog puzzle

Is there a strategy the frogs can use to cross the pond? The final (goal) state should have Xavier, Yolanda, and Zora (in any order) on the three leftmost stones, and Alma, Ben, and Carl (in any order) on the three rightmost stones.

Describe a method to compactly represent a single state of the frog world. Use it to write the start state and one possible goal state.
Identify the two types of actions that a frog can take. For each action, describe the precondition – what must be true to allow the frog to take that action.
Because the frogs travel in only one direction, the state graph for this problem is a tree. For each state, the possible actions lead to child states. If there are no possible actions from some state, then it is a leaf and we say that the frogs are stuck. (The goal state is also a leaf.)

Use your state representation to write down two leaf states – ones where no action is possible for any frog.
The solution to this puzzle takes 15 steps! To simplify it a bit, let’s exclude two frogs: Carl and Zora. Write down the start state with Alma, Ben, Xavier, and Yolanda on just 5 stones. Write down the corresponding goal state.
Now, to solve the problem! Starting with the start state, write all possible moves (one per line), indented under the goal state. Next to each move, write the new state that would result from making that move. Here is the format:
```
State0:
   Move1 → State1
   Move2 → State2
```
Next, you apply the same technique to any new states that have been generated:
```
State2:
   Move1 → State3
```
If a states is stuck, there will be no possible moves, so note that instead:
```
State3 STUCK
```
As you continue analyzing states, you will eventually encounter a goal state. Circle the goal state, and then reconstruct the sequence of moves that led you there. You’re done!

The solution with 4 frogs should require 8 moves. To simplify a little further, there are two ways to reach the goal: one starts with a right-facing frog (A or B) moving right, the other with a left-facing frog (X or Y) moving left. So ignore the solutions starting with X or Y. This will cut the search space in half.

Write your answers to these questions into a text document – the formats doc, docx, txt, or odt are all fine. Upload the document to this dropbox for assignment 7.

PDF version

Assignment 7 – AI