Chapter 3, Problem 9E

Explanation of Solution

a.

Formulation:

• The given data are,
  • There are 3 missionaries and 3 cannibals on the left bank of a river.
  • They wish to cross over the right bank using a boat that can only carry two at a river.
  • The number of cannibals on either balls must never exceed the number of missionaries on the same bank, otherwise, the missionaries will become the cannibals’ dinner.
  • Plan a sequence of crossing that will take everyone safely across.
• For solving the problem, a tuple (m,c,b) is used to present the state of one side of the river, since the other side can be easily inferred.
• Where,
  • “m” stands for number of missionaries...

Explanation of Solution

b.

Solving Missionaries and Cannibals problem:

First let us consider that both the missionaries (M) and cannibals(C) are on the same side of the river.

Left Right

Initially the positions are: 0M 0C and 3M , 3C (B)

Now let’s send 2 Cannibals to left of bank: 0M , 2C (B) and 3M , 1C

Send one cannibal from left to right: 0M , 1C and 3M , 2C (B)

Now send the 2 remaining Cannibals to left : 0M , 3C (B) and 3M , 0C

Send 1 cannibal to the right : 0M , 2C and 3M , 1C (B)

Now send 2 missionaries to the left: 2M , 2C (B) and 1M ...

Explanation of Solution

c.

Reason for people think that solving puzzle problem is very hard:

It is not obvious that al...