The Missionaries and Cannibals Problem

Some reading before you start: http://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem

Problem Statement:
[From the link above] "In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries.) The boat cannot cross the river by itself with no people on board."

Solution:
We will solve the generalized version of this problem, wherein there are C cannibals and M missionaries, and at most P people are allowed on the boat simultaneously.

This problem can be solved by noticing that at every stage, we can encode the state of the problem by using 3 variables, (nc, nm, shore). nc is the number of cannibals, nm is the number of missionaries and shore is either 0 or 1, which signifies whether nc and nm represent the count on the source or the destination shore respectively.

Thus, there are at most 2 x n² states that the problem can be at any point in time.

We can use BFS (breadth first search) to perform an exhaustive search on the search space to find a solution if one exists. The run-time complexity of doing so is O(CM P²). Below is the Python2.5 code that solves this problem using the BFS search method.

import sys
import string
from collections import deque


states = [[], []]
dq = deque()
nc = 0
nm = 0
c = 0
combinations = [ ]


def gen_combinations():
    global c, combinations

    for i in xrange(0,c+1):
        for j in xrange(0,c+1):
            if i+j>0 and i+j<=c:
                combinations.append((i,j))


def init_states():
    global nc, nm, states
    for i in xrange(0, nc+1):
        states[0].append([])
        states[1].append([])
        for j in xrange(0, nm+1):
            states[0][i].append(-1)
            states[1][i].append(-1)


def is_valid_state(nc, nm):
    return (nm>=nc) or (nm==0) or (nc==0)


def bfs():
    global dq, states, nc, mn, c, combinations

    while (len(dq) > 0) and states[1][nc][nm] == -1:
        (x,y,depth,boat) = dq.popleft()

        present = boat
        next = 1-boat

        if states[present][x][y] != -1:
            continue

        states[present][x][y] = depth

        for comb in combinations:
            (dx,dy) = comb

            if x>=dx and y>=dy:
                new_st = (nc-(x-dx),nm-(y-dy),depth+1,next)
                (lx,ly) = (nc-(x-dx),nm-(y-dy))
                (rx,ry) = (nc-lx,nm-ly)

                if is_valid_state(lx, ly) and is_valid_state(rx, ry) \
                       and states[next][lx][ly] == -1:
                    dq.append(new_st)



def main():
    global dq, nc, nm, c, combinations, states
    input = string.split(raw_input())
    nc = int(input[0])
    nm = int(input[1])
    c  = int(input[2])

    init_states()
    gen_combinations()

    dq.append((nc, nm, 0, 0))
    bfs()

    print states[1][nc][nm]

    return 0


if __name__ == "__main__":
    sys.exit(main())