#
# 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