Write a brief essay in answer to each of the following questions.
1. (~1.5 pages) Consider the following water transfer puzzle. You have three jars--one whose capacity is 8 quarts, one of 5 quarts, and one of 3 quarts. At the start of the puzzle, the 8 quart jar is filled, and the other two jars are empty. Your job is to transfer water (without measuring) between jars so that eventually there are 4 quarts in the large jar, and 4 quarts in the 5-quart jar. Each transfer must either fill the target jar or empty the source jar (or both).
1a. List all the possible achievable states of this puzzle, using a format like the following:
A. 8 0 0
B. 5 0 3
C. 3 5 0
and so forth. In other words, use three numbers to designate a state in which the first number is the amount in the 8-quart jar, the second number is the amount in the 5-quart jar, and the third number is the amount in the 3-quart jar. (Hint: if you label each state with a letter, as Ive done for the three states listed above, you won't need the entire alphabet to list them all!)
1b. Show the solution to the problem by listing a sequence of states from part 1a. For instance, if your first move is to transfer the 8-quart jar to the 5-quart jar, then your solution will begin A --> C --> and so forth, if you use the labeling scheme above.
1c. Show a possible order of states that would be encountered in breadth-first search for this puzzle. For instance, if the start state is A, then the next two states encountered would be one move away--namely, states B and C. Show all the new states (i.e., the ones we have not yet encountered) that are two moves away; three moves away; and so forth.
2. (~1.5 pages) Choose a puzzle problem (it could be one of the puzzles handed around in class, or some other sort of mental puzzle of the kind, say, found in "Games" magazine), and analyze it in terms of the language of problem spaces discussed in lecture. You should (for instance) describe the state space, making an estimate of its size; describe the nature of moves available; and mention what sorts of strategies one might use to solve the puzzle. Does this analysis seem at all informative about why the puzzle is (or maybe isn't) interesting or fun?