CS63 Spring 2004
Lab 1: State Space Search
Due: Friday, January 30, by 11am

CONTENTS

INTRODUCTION

For this lab you will begin to learn the Python programming language and then use Python to implement the missionaries and cannibals puzzle for state space search. Recall that in this puzzle there are three missionaries and three cannibals who need to cross a river. There is a boat, but it can only hold two people. An additional constraint is that there should never be more missionaries than cannibals on either side of the river.

LAB INSTRUCTIONS

  1. Read through and try the examples in PyroModulePythonIntro.
  2. I have implemented a general state space search algorithm in Python. Save search.py to your own directory. Read through the class definitions to understand how search is implemented.
  3. I have implemented an example problem domain to be used in conjunction with state space search called the water pitcher puzzle. In this puzzle you are given a three-quart pitcher and a four-quart pitcher. Either pitcher can be filled from a faucet. The contents of either pitcher can be poured down a drain. Water may be poured from one pitcher to the other. When pouring, as soon as the pitcher being poured into is full, the pouring stops. There is no additional measuring device and and the pitchers have no markings to show partial quantities. A typical problem might be, what actions would you need to do in order to go from two empty pitchers, to exactly two quarts in the four-quart pitcher?

    Save pitcher.py to your own directory. Read through the class definition to understand how the PitcherState class works in conjunction with the Search class.

  4. Using the PitcherState class as a model, write a MissionaryState class that implements the missionaries and cannibals problem. Once implemented, you should be able to conduct a search using the following command: 
    Search(MissionaryState(3,3,1), MissionaryState(0,0,0))

HAND IN

Use cs63handin to submit your missionary.py file.