Generalized solution to the cannibals and missionaries problem.

cannibals_and_missionaries.py

class State:
    def __init__(self, left_m=5, right_m=0, left_c=5, right_c=0, boat='left', parent=None, couples=5, boat_holds=3):
        if parent == None:
            assert left_m == left_c == couples, "Invalid root state lefts must equal couples"

        self.left_m = left_m
        self.right_m = right_m
        self.left_c = left_c
        self.right_c = right_c
        self.boat = boat
        self.parent = parent
        self.boat_holds = boat_holds
        self.couples = couples
        

    def is_valid(self):
        valid = True
        if self.left_m > 0 and self.left_m < self.left_c:
            valid = False
        if self.right_m > 0 and self.right_m < self.right_c:
            valid = False
        return valid
        
    def is_final(self):
        if self.right_m == self.couples and self.right_c == self.couples and self.boat == 'right':
            return True


    def __repr__(self):
        return str([self.left_m, self.left_c, self.right_m, self.right_c, self.boat])


def actions(state, boat_holds=3):
    actions = []
    if state.boat == 'left':
        for x in range(0, state.left_m+1):
            for y in range(0, state.left_c+1):
                if x+y > boat_holds or x+y == 0:
                    continue
                else:
                    actions.append((x, y))
        return actions
    else:
        for x in range(0, state.right_m+1):
            for y in range(0, state.right_c+1):
                if x+y > boat_holds or x+y == 0:
                    continue
                else:
                    actions.append((x, y))
        return actions

                





def next_states(state):
    new_states = []
    acts = actions(state, state.boat_holds)
    if state.boat == 'left':
        for action in acts:
            new_left_m = state.left_m - action[0]
            new_right_m = state.right_m + action[0]
            new_left_c = state.left_c - action[1]
            new_right_c = state.right_c + action[1]
            new_state = State(new_left_m, new_right_m, 
                              new_left_c, new_right_c, 
                              'right', state)
            if new_state.is_valid():
                new_states.append(new_state)
        return new_states
    else:
        for action in acts:
            new_left_m = state.left_m + action[0]
            new_right_m = state.right_m - action[0]
            new_left_c = state.left_c + action[1]
            new_right_c = state.right_c - action[1]
            new_state = State(new_left_m, new_right_m, 
                              new_left_c, new_right_c, 
                              'left', state)
            if new_state.is_valid():
                new_states.append(new_state)
        return new_states


def breadth_first_search(state):
    initial_state = state
    if initial_state.is_final():
        return initial_state
    frontier = list()
    explored = set()
    frontier.append(initial_state)
    while frontier:
        state = frontier.pop(0)
        if state.is_final():
            return state
        explored.add(state)
        children = next_states(state)
        for child in children:
            if (child not in explored) or (child not in frontier):
                frontier.append(child)
    return None



if __name__ == "__main__":
  
  ## Each state is in the following form when printed: 
  ## [Missionaries(L), Cannibals(L), Missionaries(R), Cannibals(R), Boat_side]
  
    solution = breadth_first_search(State(5, 0, 5, 0, 'left', couples=5))
    node = solution
    steps = [node]
    while node.parent:
        steps.append(node.parent)
        node = node.parent
    steps.reverse()
    print(steps)
    

Solution for 5 Cannibals, 5 Missionaries, and a boat holding 3

[5, 5, 0, 0, 'left'],
[5, 3, 0, 2, 'right'],
[5, 4, 0, 1, 'left'],
[5, 1, 0, 4, 'right'],
[5, 2, 0, 3, 'left'],
[2, 2, 3, 3, 'right'],
[3, 3, 2, 2, 'left'],
[0, 3, 5, 2, 'right'],
[0, 4, 5, 1, 'left'],
[0, 2, 5, 3, 'right'],
[0, 3, 5, 2, 'left'],
[0, 0, 5, 5, 'right']