Lab 0: State Space Search on Logic Puzzles
Due Thursday, Sept. 12 by 11:59 pm

4-layer neural network

Starting point code

For this first lab, you will work individually.

First change into your directory for this class. Then clone the GitHub repository for lab0, replacing USER with your username:

    cd cs63
    git clone


The objectives of this lab are to:

For this lab you will:

Python review

If you skipped cs21, or it has been awhile since you have programmed in Python, then I recommend that you begin with this Python tutorial.

Review the starting point code

Your lab0 repo should contain six files. Read through and familiarize yourself with each file. You do not need to implement any functionality in the first four files, however feel free to add your own test cases to them. Details on what you need to implement in the last two files are provided in the next sections.

  1. implements a Queue data structure. Make sure that you understand how it works. At the bottom of the file is some test code. Execute this file (python3 to see the test results. You will need to use a queue when implementing breadth-first search.
  2. implements a basic Node class for storing search information. You will create nodes and add them to the Queue during your search.
  3. defines an abstract class (or in other words an interface). Your search implementation will assume that all problems to be solved will inherit from this abstract class.
  4. implements a class called PitcherState that inherits from ProblemState. Once you complete your implementation of search, you can test it on this problem.
  5. contains an incomplete implementation of a search agent that uses BFS to solve logic problems. You must complete this.
  6. contains an incomplete implementation of a class called MissionaryState. You must complete this.


Open the file and complete the implementation of the class definition. You'll need to write the constructor, a search method, and a helper method for building up the path to the solution. The comments within each method provide guidance about how to proceed. You're welcome to create additional helper methods as needed.

In particular, the method executeSearch() should implement the following algorithm:

while queue not empty
   remove node from queue
   if state in node equals the goal state
      build the path
      display the path, and total number of steps taken
   end if
   apply the operators to get all valid successors
   for each successor
      if key of successor is not in unique states dictionary
         add key of successor to dictionary
         create a node for the successor
         add node to queue
      end if
   end for
end while
report failure
report number of states explored
If the search terminates because the goal was found, then the problem is solved; if the while loop terminates because of an empty queue, then problem is unsolvable.


You can execute the file to test your search agent:

At the bottom of file, two test cases have been provided. The first test case is solvable, and is the one we did in class. It can be accomplished in seven steps. The second test case is unsolvable. Ensure that your search agent produces the appropriate output for these two test cases.

Add at least three more test cases and verify the results. Once your are confident that your search agent is working correctly, you can move on to the next section.


Open the file, and complete the implementation of the class definition. Notice that the MissionaryState class inherits from the abstract class ProblemState and is therefore required to provide concrete definitions for a number of methods, in a similar way to the PitcherState class. In fact, feel free to model your solution to MissionaryState on the PitcherState class. However, there is one key difference between the operators for the Missionary and Cannibals problem and the Water Pitcher problem. The operators for the Water Pitcher problem always lead to valid next states. You'll need to determine a way to recognize invalid Missionary and Cannibal states and avoid returning them as successors.

NOTE: Be careful that you do not hard code any particular number of missionaries or cannibals into your code. You can assume that for every version of the problem the boat can hold at most two people, but the numbers of missionaries and cannibals can vary.

Comment your code clearly. Explain the purpose of every class variable that you create.


At the bottom of the file, add two test cases. The first should be the problem we discussed in class where three missionaries and three cannibals start on the left bank. This should be solvable in eleven steps. The second should be the unsolvable problem with four of each type starting on the left bank.

You can execute the file to test whether your search agent can also find solutions to this logic puzzle:


Add some additional test cases of your own invention. Try some larger numbers. For instance, can 50 missionaries and 49 cannibals make it across the river safely?

Submitting your code

To submit your code, use git to add, commit, and push the files that you modified.