CS ARTIFICIAL INTELLIGENCE HOMEWORK #1 Solution

First carefully study the problem depicted in Figure 2.1 in Chapter 2 of Winston.

Then manually solve the following puzzle (​non-credit; not to be submitted​):

A group consisting of 3 cannibals and 3 missionaries seeks to cross a river. A boat is available which will hold up to 2 people. If the missionaries on either side of the river are outnumbered at any time by the cannibals on that side, even momentarily, the cannibals will do away with the unfortunate, out-numbered missionaries. What schedule of crossings can be devised to permit the entire party to cross safely? Assume that the group and the boat are on the west bank initially and that they would like to end up on the east bank eventually.

HINT: In your solution, it may be best to formulate the puzzle as state-space search. ​xMyCb​is a good state representation, where x is the number of missionaries (M) on the west bank, y is the number of
cannibals (C) on the west bank, and b is 1 if the boat is on the west bank (and 0, if it is on the east bank).

Obviously, x and y are in the range [0, 4] . Now, considering these questions may be helpful:

    • What are the initial and goal states?

    • What are the operators?

    • What is the branching factor?

So far, we have been preparing ourselves for the actual assignment of Homework #1, which is:

Write a program which --- by exhaustively searching a space of possible solutions --- proves that 4 cannibals and 4 missionaries ​cannot ​be taken safely across a river with a boat holding only 2 people. (There is a paper about this but you do not have to read it to do the homework. In any case, the paper is at ​https://www.jstor.org/stable/pdf/2687980.pdf​)

Your program must use ​either​​Depth First Search​​or​​Breadth First Search​.​(Just implement, in a straightforward manner, ​one​of the pseudocodes given in Winston, Chapter 4, page 68.) You must check for ​repeated​states.

What should be the output of your program? An exhaustive list of paths which start at the initial state and can never reach the goal state would do the job. Thus, assume that you start with the initial state as the root. As your grow a tree downwards, you should never allow unsafe states (or to put it conversely, you should only allow safe states) and you should also avoid loops (repeated states). If you search the entire tree and cannot find a solution path, then you’ve proved (computationally) that a solution does not exist.

Your program should have a simple control for ‘single stepping’ (tracing) in your code so that you and the TAs can inspect the intermediate stages of the problem-solving process in an incremental fashion. Needless to say, this is also useful for debugging your program during the development stage.







GENERAL REMARKS (THESE ARE APPLICABLE TO ALL HOMEWORK ASSIGNMENTS)

    • IF YOU ARE REQUESTED TO SUBMIT A HARDCOPY AT ANY TIME IN THIS COURSE, MAKE SURE THAT WHAT YOU SUBMIT IS CLEAN AND FULLY MACHINE-GENERATED. IF THERE IS A HANDWRITTEN ADDITION OR CORRECTION ON A PRINTOUT, YOU’LL DEFINITELY LOSE POINTS.

    • Late submissions will first have 2 points deducted categorically. Then they’ll have 2 points deducted for every late day. (A new day begins at 12:01 midnight.)