Problem 1 (River crossing with a middle island!). On one bank of a river are four missionaries and four cannibals. There is one boat available that can hold up to two people and that they would like to use to cross the river. The river contains a middle island that can be used to assist the movement of missionaries and cannibals across the river. (Here we are allowed to cross from bank-to-bank without stopping at the middle island. If this were not allowed, we could not transport two cannibals across if a missionary were on the middle island.) If the cannibals ever outnumber the missionaries on either of the river’s banks, the missionaries will get eaten. How can the boat be used to safely carry all the missionaries and cannibals across the river? m 8 ISLAND LEFT SHORE RIGHT SHORE a. Solve the riddle by drawing a diagram indicating the movement of missionaries and cannibals. Record the number of movements used. b. (Bonus) Solve the original riddle with the assumption that shore-to-shore travel is not allowed (i.e., you must stop at the middle island). Does this change the number of movements used? c. (Bonus) Solve the riddle with N = 5 missionaries and N = 5 cannibals (without and with shore-to-shore movement) d. (Bonus) Attempts at implementing a search algorithm (in a language of your choice) to construct a path from initial state to end state in the Missionaries and Cannibals (+ Middle Island) Riddle? 1