Java Reference
In-Depth Information
Programming Projects
1.
Write a recursive program to solve the “Missionaries and Cannibals” problem. Three missionaries and three canni-
bals come to a river and find a boat that holds two. If the cannibals ever outnumber the missionaries on either bank,
the missionaries will be eaten. How might they cross safely?
Your output should include the initial problem, the moves you make, and a “picture” of the current state of the puzzle after
each move. Your final output should produce only the moves and the picture for the states that are on the solution path.
2.
Write a recursive program to solve the Towers of Hanoi puzzle. The puzzle involves manipulating disks that you can
move between three different towers. You are given a certain number of disks (four in this example) stacked on one
of the three towers. The disks have decreasing diameters, with the smallest disk on the top (see Figure 12.9).
A
B
C
Figure 12.9
Towers of Hanoi
The object of the puzzle is to move all of the disks from one tower to another (say, from A to B). The third tower is
provided as a temporary storage space as you move disks around. You are allowed to move only one disk at a time,
and you are not allowed to place a disk on top of a smaller one (i.e., one with a smaller diameter).
Examine the rather simple solutions for one, two, and three disks, and see if you can discern a pattern. Then write a
program that will solve the Towers of Hanoi puzzle for any number of disks. (
Hint:
Moving four disks is a lot like
moving three disks, except that one additional disk is on the bottom.)
3.
Write a recursive program to solve the Eight Queens puzzle. The puzzle involves placing eight queens on a standard
chessboard in such a way that no two threaten each other. Figure 12.10 shows one example solution to this problem.
a
b
c
d
e
f
g
h
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
a
b
c
d
e
f
g
h
Figure 12.10
A solution to the Eight Queens puzzle
Search WWH ::
Custom Search