#
# This is a Python program to find all solutions to the Missionary-Cannibal
# Problem using a blind depth-first search with a stack keeping track of
# the path from the root to the current state.
#
# There are 3 missionaries and 3 cannibals and a boat that holds 2 people.
# Each state is of the form(nmiss, ncann, bside).
# nmiss is the number of missionaries on the left side of the river.
# ncann is the number of cannibals on the left side of the river.
# bside is the side of the river that the boat is on: 'L' or 'R'
#
class State:
   "Missionary-Cannibal-Boat State"
#
# Finish state definition here.
#
   def __init__(self, nmiss=0, ncann=0, bside=' '):
		#WRITE SOME CODE HERE

#
# The describe method returns a string form of a State: e.g. (0, 0, L) or (3, 1, R)
#
   def describe(self):
		#WRITE SOME CODE HERE

#
# The goal method returns True if the state is the goal state (0,0,'R')
#
   def goal(self):
		#WRITE SOME CODE HERE

#
# The illegal method returns True if a state is illegal, meaning there are
# more cannibals than missionairies on either side of the rivers.
#
   def illegal(self):
		#WRITE SOME CODE HERE


# PART B starts from here

# The next 10 methods are the state change operators.
# Each one first tests that it can be applied. 
# If so, it returns the new state.
# Otherwise, it returns the bad state (-1, -1, 'M')
#
# MCR sends the boat from left to right with one missionary and one cannibal
#
   def MCR(self):
		#WRITE SOME CODE HERE

#
# MMR sends the boat from left to right with two missionaries in it
#
   def MMR(self):
		#WRITE SOME CODE HERE

#
# MR sends the boat from left to right with one missionary in it
#
   def MR(self):
		#WRITE SOME CODE HERE

#
# CCR sends the boat from left to right with two cannibals in it
#
   def CCR(self):
		#WRITE SOME CODE HERE

#
# CR sends the boat from left to right with one cannibal in it
#
   def CR(self):
		#WRITE SOME CODE HERE

#
# MCL sends the boat from right to left with one missionary and one cannibal
#
   def MCL(self):
		#WRITE SOME CODE HERE

#
# MML sends the boat from right to left with two missionaries in it
#
   def MML(self):
		#WRITE SOME CODE HERE

#
# ML sends the boat from right to left with one missionary in it
#
   def ML(self):
		#WRITE SOME CODE HERE

#
# CCL sends the boat from right to left with two cannibals in it
#
   def CCL(self):
		#WRITE SOME CODE HERE

#
# CL sends the boat from right to left with one cannibal in it
#
   def CL(self):
		#WRITE SOME CODE HERE

# PART B ends here

#
# This method miscan() is the main program that initializes variables
# and calls the recursive search procedure mcsearch
#
def miscan():
   global bad
   bad = State(-1, -1, 'M')
   start = State(3,3,'L')
   path = []
   path.insert(0, start)
   mcsearch(start, path)

#
#
# mcsearch is the recursive depth-first search procedure
#
def mcsearch(s, path):

#
# If it is at a goal state, it inserts that state in the path and
# calls on the output method, and returns
#
#
   #if it is a goal state
		#WRITE SOME CODE HERE

#
# If it is at an illegal state, just return
#
   #if it is an illegal state
		#WRITE SOME CODE HERE

#
# If it is at a repeated state, just return
#
   #if it is a repeated state
		#WRITE SOME CODE HERE

#
# Otherwise:
# 1) call expand to get the children
# 2) for each child:
#	a)push it on the path
#	b)recursively continue the search with the child
#	c)pop it off the path
#
		#WRITE SOME CODE HERE

#
# expand calls expandL when the current state is on the left
# and expandR when it is on the right
#
def expand(s):
		#WRITE SOME CODE HERE

#
# expandL expands a state that is on the left.
# It tries each of the five possible operators for the left,
# putting the states returned by those that succeed
# on a list called children, which it returns.
#
def expandL(s):
 		#WRITE SOME CODE HERE

#
# expandR expands a state that is on the right.
# It tries each of the five possible operators for the right,
# putting the states returned by those that succeed
# on a list called children, which it returns.
#
def expandR(s):
 		#WRITE SOME CODE HERE

#
miscan()