

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

Missionaries and Infidels

We illustrate the notion of a search problem with the following example, which is also known as the missionaries and cannibals problem: Three missionaries and three infidels have to cross a river that runs from the north to the south. Initially, both the missionaries and the infidels are on the western shore. There is just one small boat and that boat can carry at most two passengers. Both the missionaries and the infidels can steer the boat. However, if at any time the missionaries are confronted with a majority of infidels on either shore of the river, then the missionaries have a problem.

$\texttt{problem}(m, i)$ is True if there is a problem on a shore that has $m$ missionaries and $i$ infidels.



In [ ]:

    
problem = lambda m, i: 0 < m < i

$\texttt{noProblemAtAll}(m, i)$ is true if there is no problem on either side. $m$ and $i$ are the number of missionaries and infidels on the left shore.



In [ ]:

    
noProblem = lambda m, i: not problem(m, i) and not problem(3 - m, 3 - i)

A state is represented as a triple. The triple $(m, i, b)$ specifies that there are

$m$ missionaries,
$i$ infidels, and
$b$ boats

on the western shore of the river. This implies that there are $3 - m$ missionaries, $3 - i$ infidels, and $1 - b$ boats on the eastern shore.



In [ ]:

    
def nextStates(state):
    m, i, b = state
    if b == 1:
        return { (m-mb, i-ib, 0) for mb in range(m+1)
                                 for ib in range(i+1)
                                 if 1 <= mb + ib <= 2 and 
                                    noProblem(m-mb, i-ib) 
               }
    else:
        return { (m+mb, i+ib, 1) for mb in range(4-m)
                                 for ib in range(4-i)
                                 if 1 <= mb + ib <= 2 and 
                                    noProblem(m+mb, i+ib) 
               }

We have to %run the notebook Breadth-First-Search.iypnb in order to make the function search available that is defined in this notebook.

Printing the Solution

To begin with, we display the transition relation that is generated by the function nextStates. To this end, we need the module graphviz.



In [ ]:

    
import graphviz as gv



In [ ]:

    
def tripleToStr(t):
    return '(' + str(t[0]) + ',' + str(t[1]) + ',' + str(t[2]) + ')'

The function dot_graph(R) turns a given binary relation R into a graph.



In [ ]:

    
def dot_graph(R):
    """This function takes binary relation R as inputs and shows this relation as
       a graph using the module graphviz.
    """
    dot = gv.Digraph()
    dot.attr(rankdir='LR', size='12,8')
    Nodes = { tripleToStr(a) for (a,b) in R } | { tripleToStr(b) for (a,b) in R }
    for n in Nodes:
        dot.node(n)
    for (x, y) in R:
        dot.edge(tripleToStr(x), tripleToStr(y))
    return dot

The function call createRelation(start) computes the transition relation. It assumes that all states are reachable from start.



In [ ]:

    
def createRelation(start):
    oldM = set()
    M    = { start }
    R    = set()
    while True:
        oldM = M.copy()
        M |= { y for x in M
                 for y in nextStates(x)
             }
        if M == oldM:
            break
    return { (x, y) for x in M
                    for y in nextStates(x)
           }

The function call printPath(Path) prints the solution of the search problem.



In [ ]:

    
def printPath(Path):
    print("Solution:\n")
    for i in range(len(Path) - 1):
        m1, k1, b1 = Path[i]
        m2, k2, b2 = Path[i+1]
        printState(m1, k1, b1)
        printBoat(m1, k1, b1, m2, k2, b2)
    m, k, b = Path[-1]
    printState(m, k, b)



In [ ]:

    
def printState(m, k, b):
     print( fillCharsRight(m * "M", 6) + 
            fillCharsRight(k * "K", 6) + 
            fillCharsRight(b * "B", 3) + "    |~~~~~|    " + 
            fillCharsLeft((3 - m) * "M", 6) + 
            fillCharsLeft((3 - k) * "K", 6) + 
            fillCharsLeft((1 - b) * "B", 3) 
          )



In [ ]:

    
def printBoat(m1, k1, b1, m2, k2, b2):
    if b1 == 1:
        if m1 < m2:
            print("Fehler in printBoat: negative Anzahl von Missionaren im Boot!")
            return
        if k1 < k2:
            print("Fehler in printBoat: negative Anzahl von Kannibalen im Boot!")
            return
        print(19*" " + "> " + fillCharsBoth((m1-m2)*"M" + " " + (k1-k2)*"K", 3) + " >")
    else:
        if m1 > m2:
            print("Fehler in printBoat: negative Anzahl von Missionaren im Boot!")
            return
        if k1 > k2:
            print("Fehler in printBoat: negative Anzahl von Kannibalen im Boot!")
            return
        print(19*" " + "< " + fillCharsBoth((m2-m1)*"M" + " " + (k2-k1)*"K", 3) + " <")



In [ ]:

    
def fillCharsLeft(x, n):
    s = str(x)
    m = n - len(s)
    return m * " " + s



In [ ]:

    
def fillCharsRight(x, n):
    s = str(x)
    m = n - len(s)
    return s + m * " "



In [ ]:

    
def fillCharsBoth(x, n):
    s  = str(x)
    ml = (n     - len(s)) // 2
    mr = (n + 1 - len(s)) // 2
    return ml * " " + s + mr * " "



In [ ]: