My Weblog

Missionaries and cannibals problem

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. We can solve this problem using depth first search. Representing the states as number of missionaries, cannibals and boat location in following way.

```
data Side = Side { missionaries :: Int , cannibals :: Int } deriving ( Show , Eq  )
data Loc = L | R deriving ( Show , Eq  )
data State = State { left :: Side , right :: Side , bloc :: Loc } deriving ( Show , Eq  )

```

Target is to move every missionaries and cannibals from left to right so our initial state is initialState and final state is finalState.

```
initialState = State { left =  Side 3 3  , right =  Side 0 0  , bloc = L }
finalState = State  { left =  Side 0 0  , right = Side 3 3  , bloc = R }

```

Possible movements
1. move ( 2 , 0 )
2. move ( 1 , 0 )
3. move ( 1 , 1 )
4. move ( 0 , 1 )
5. move ( 0 , 2 )
where move ( M , C ) is movement of M missionaries and C cannibals from one side to other side depending on boat location. If boat location is left then move ( M , C ) is moving M missionaries and C cannibals from left to right and vice versa. Using depth first search, we can explore every possible movement

```path :: [ State ] -> [ State ] -> [ State ]
path []   vis = reverse vis
path  ( x : xs )  vis
| x  == finalState  = reverse ( x : vis )
| elem x vis = path xs vis
| otherwise = path xs'  vis'  where
vis'  = x : vis
xs' =   ( filter  isLegal  ( move x ) ) ++ xs
```

Encoding the moves and testing the legality

```
move :: State -> [ State ]
move ( State ( Side ml cl ) ( Side mr cr ) L ) =
[ State ( Side ( ml - 2 ) cl ) ( Side ( mr + 2 ) cr ) R
, State ( Side ( ml - 1 ) cl ) ( Side ( mr + 1 ) cr ) R
, State ( Side ( ml - 1 ) ( cl - 1 ) ) ( Side ( mr + 1 ) ( cr + 1 ) ) R
, State ( Side ml ( cl - 2 ) ) ( Side mr ( cr + 2 ) ) R
, State ( Side ml ( cl - 1 ) ) ( Side mr ( cr + 1 ) ) R
]
move  ( State ( Side ml cl ) ( Side mr cr ) R ) =
[ State ( Side ( ml + 2 ) cl ) ( Side ( mr - 2 ) cr ) L
, State ( Side ( ml + 1 ) cl ) ( Side ( mr - 1 ) cr ) L
, State ( Side ( ml + 1 ) ( cl + 1 ) ) ( Side ( mr - 1 ) ( cr - 1 ) ) L
, State ( Side ml ( cl + 2 ) ) ( Side mr ( cr - 2 ) ) L
, State ( Side ml ( cl + 1 ) ) ( Side mr ( cr - 1 ) ) L
]

isLegal :: State -> Bool
isLegal ( State ( Side ml cl ) ( Side mr cr ) y )
| ml == 0 = mr >= cr  && cr >= 0
| mr == 0 = ml >= cl  && cl >= 0
| otherwise = ml >= cl && mr >= cr && cl >= 0 && cr >= 0

```

Complete source code ( In case if you are lazy 🙂 )

```import Data.List

data Side = Side { missionaries :: Int , cannibals :: Int } deriving ( Show , Eq  )
data Loc = L | R deriving ( Show , Eq  )
data State = State { left :: Side , right :: Side , bloc :: Loc } deriving ( Show , Eq  )

initialState = State { left =  Side 3 3  , right =  Side 0 0  , bloc = L }
finalState = State  { left =  Side 0 0  , right = Side 3 3  , bloc = R }

path :: [ State ] -> [ State ] -> [ State ]
path []   vis = reverse vis
path  ( x : xs )  vis
| x  == finalState  = reverse ( x : vis )
| elem x vis = path xs vis
| otherwise = path xs'  vis'  where
vis'  = x : vis
xs' =   ( filter  isLegal  ( move x ) ) ++ xs

move :: State -> [ State ]
move ( State ( Side ml cl ) ( Side mr cr ) L ) =
[ State ( Side ( ml - 2 ) cl ) ( Side ( mr + 2 ) cr ) R
, State ( Side ( ml - 1 ) cl ) ( Side ( mr + 1 ) cr ) R
, State ( Side ( ml - 1 ) ( cl - 1 ) ) ( Side ( mr + 1 ) ( cr + 1 ) ) R
, State ( Side ml ( cl - 2 ) ) ( Side mr ( cr + 2 ) ) R
, State ( Side ml ( cl - 1 ) ) ( Side mr ( cr + 1 ) ) R
]
move  ( State ( Side ml cl ) ( Side mr cr ) R ) =
[ State ( Side ( ml + 2 ) cl ) ( Side ( mr - 2 ) cr ) L
, State ( Side ( ml + 1 ) cl ) ( Side ( mr - 1 ) cr ) L
, State ( Side ( ml + 1 ) ( cl + 1 ) ) ( Side ( mr - 1 ) ( cr - 1 ) ) L
, State ( Side ml ( cl + 2 ) ) ( Side mr ( cr - 2 ) ) L
, State ( Side ml ( cl + 1 ) ) ( Side mr ( cr - 1 ) ) L
]

isLegal :: State -> Bool
isLegal ( State ( Side ml cl ) ( Side mr cr ) y )
| ml == 0 = mr >= cr  && cr >= 0
| mr == 0 = ml >= cl  && cl >= 0
| otherwise = ml >= cl && mr >= cr && cl >= 0 && cr >= 0

```

``` Main> path [ initialState ] [] [State {left = Side {missionaries = 3, cannibals = 3}, right = Side {missionaries = 0, cannibals = 0}, bloc = L},State {left = Side {missionaries = 2, cannibals = 2}, right = Side {missionaries = 1, cannibals = 1}, bloc = R},State {left = Side {missionaries = 3, cannibals = 2}, right = Side {missionaries = 0, cannibals = 1}, bloc = L},State {left = Side {missionaries = 3, cannibals = 0}, right = Side {missionaries = 0, cannibals = 3}, bloc = R},State {left = Side {missionaries = 3, cannibals = 1}, right = Side {missionaries = 0, cannibals = 2}, bloc = L},State {left = Side {missionaries = 1, cannibals = 1}, right = Side {missionaries = 2, cannibals = 2}, bloc = R},State {left = Side {missionaries = 2, cannibals = 2}, right = Side {missionaries = 1, cannibals = 1}, bloc = L},State {left = Side {missionaries = 0, cannibals = 2}, right = Side {missionaries = 3, cannibals = 1}, bloc = R},State {left = Side {missionaries = 0, cannibals = 3}, right = Side {missionaries = 3, cannibals = 0}, bloc = L},State {left = Side {missionaries = 0, cannibals = 1}, right = Side {missionaries = 3, cannibals = 2}, bloc = R},State {left = Side {missionaries = 1, cannibals = 1}, right = Side {missionaries = 2, cannibals = 2}, bloc = L},State {left = Side {missionaries = 0, cannibals = 0}, right = Side {missionaries = 3, cannibals = 3}, bloc = R}] *Main> map bloc . path [ initialState ] \$ [] [L,R,L,R,L,R,L,R,L,R,L,R] ```
If you have any suggestion or comment then please let me know.