Exercise 7.6.One of the oldest known mathematical puzzles is the wolf-goat-cabbage problem. At the break of dawn, a farmer sets out for the market in a nearby village. She is accompanied by a small goat and a domesticated wolf, and she is carrying a large cabbage she hopes to sell at the market. To reach the village, the unconventional party
has to cross a river using a small boat that is just large enough to carry the farmer and either the wolf, the goat, or the cabbage. For obvious reasons, the farmer cannot leave the goat alone with the cabbage or the wolf alone with the goat.
a) Is there still a way for the whole party to cross the river unharmed?
Although it’s fairly easy to solve the wolf-goat-cabbage problem by hand, it’s even easier when modeling it using graphs. The idea, again, is to enumerate the possible states of the problem and study how they are connected by valid moves.
b) How many different states are there? Propose a way to label them.
c) Construct the graph that underlies the wolf-goat-cabbage problem and explain why it is symmetric. How many different solutions are there?
d) Implement the resulting graph using the Graph interface.
Exercise 7.7.Here is another river-crossing puzzle that is similar to the wolf-goat-cabbage problem but uses different constraints on who may use the
boat at a given time. It is called the jealous couples problem.
Two married couples need to cross a river. There is a small rowing boat that holds a maximum of two people. To group agrees on the following rule so that no one is getting jealous: No wife should ever be left in the presence of another man unless her husband is present as well.
a) Is it possible for both couples to get across the river without anyone getting jealous? How many trips are necessary?
The puzzle can be extended to an arbitrary number of couples. With three jealous couples, it is still possible to cross the river, but when there are four or more couples, the problem has no solution. A popular variation of the puzzle is therefore to add an island in the middle of the stream that can be used
to drop off passengers, should the need arise.
b)Write a program that solves the jealous couples problem with an island. Your program should be able to handle at least ten couples.
c) Use your program to study the \(n\)-couple problem with an island for \(2\le n\le 10\). For which values of \(n\) is there a solution, and how many trips are required in each case?
Measuring with Three Jugs
Exercise 7.8.Consider the following variation of the die-hard problem. There are now three jugs: two empty jugs that can hold
three and five gallons, respectively, and an additional jug that is filled with eight gallons of water. (This third jug replaces the fountain in the original description of the problem.) The goal is to evenly divide the contents of the eight-gallon jug.
a) What’s the relationship between this problem and the original die-hard problem?
b) Assume you start with only six gallons of water in the additional jug. Sketch the graph that corresponds to this problem. How does it differ from the die-hard graph in Fig. 7.2? Is it still possible to measure four gallons in this case? Is it possible to divide the six gallons evenly? If yes, what is the most efficient way of doing so?
c) Write a program that computes the graphs that model the three-jug problem. The structure of each graph is determined by four numbers: the capacities of the three jugs and the total amount of water distributed among the jugs. Explain how to
compute the set of all nodes and the neighbors of each node.
d) Consider the three-jug problem with 6 units of water discussed in part (b). What is the diameter of the corresponding graph? What are
the most difficult water-measuring problems of this puzzle?
Hanoi Graphs
Exercise 7.9.In Exercise 3.8 we discussed the Towers of Hanoi and how to solve this puzzle using recursion. In this exercise, we translate the puzzle into a graph problem and study the resulting Hanoi graph.
The Hanoi graph \(\text {Hanoi}(n)\) is defined as the graph that corresponds to the Towers of Hanoi puzzle with \(n\) disks. There is one node for each valid configuration of the \(n\) disks, and two nodes are connected by an edge if there is a legal move of a single disk that connects the
corresponding disk configurations. The edges are undirected because all moves are reversible.
As we discussed in Exercise 3.8, every configuration of \(n\) disks (and therefore every node) can be described by a sequence of \(n\) letters that specifies the order in which disks are placed on the pegs A, B, and C. The node
ABB corresponds to the configuration in which the largest disk is placed on peg A and the next two disks on peg B; peg C remains empty.
The first two Hanoi graphs are shown in Fig. 7.4. For \(n=1\) the graph consists of three nodes A, B, and C, and since the disk can be moved freely, there is an edge between each pair of nodes. For \(n=2\) there are nine nodes AA, AB, AC,
BA, BB, BC, CA, CB, CC and a total of 12 edges between them. Nine of these 12 edges, including BA — BB, BB — BC, BC — BA, correspond to moving the small disk; the nodes that are connected by these edges differ in their last letter only.
The remaining three edges AC — BC, AB — CB, and BA — CA correspond to moving the large disk, which is only possible if the small disk is out of the way.
Figure 7.4 The first two Hanoi graphs. There is one node for every configuration of disks, and an edge for every pair of configurations that are related by moving a single disk.
In general, every Hanoi graph \(\text {Hanoi}(n)\) consists of three smaller Hanoi graphs \(\text {Hanoi}(n-1)\) in which the largest disk remains fixed and the remaining \(n-1\) disks can move around freely. These three subgraphs are then joined by three edges that corresponds to moving the
largest disk to a different peg. It’s easy to see that moving from one corner of the Hanoi graph to another corresponds to transferring every disk from one peg to another.
a) Sketch \(\text {Hanoi}(3)\). How many nodes and edges does the graph \(\text {Hanoi}(n)\) have?
b) Write a program that computes the Hanoi graph of order \(n\).
Using Hanoi graphs, we can solve the Towers of Hanoi by using breadth-first search to find a path from a starting node such as AAA to a target node such as CCC.
c) How efficient is breadth-first search compared to a tailor-made algorithm for solving the Towers of Hanoi such as the one we discussed in Exercise 3.8? Hint: Consider the
number of nodes that are visited by both algorithms.
A path visits every node of a graph is called a Hamiltonian path, and a path that visits every node and returns to the start is a Hamiltonian cycle. It’s obvious that \(\text {A}\to {}\text {B}\to {}\text {C}\to {}\text {A}\) is a Hamiltonian cycle of \(\text {Hanoi}(1)\): the path is cyclic and contains all three nodes.
d) Find Hamiltonian cycles in \(\text {Hanoi}(2)\) and \(\text {Hanoi}(3)\).
e) Use induction to show that for every Hanoi graph it is possible to construct a Hamiltonian path between any two of its corners. Does every Hanoi graph also contain a Hamiltonian cycle?
Flood Fill
Exercise 7.10.Most paint programs come with a tool for filling regions of an image: The user clicks on a pixel inside the image, and the entire region
connected to that pixel is filled with a new color. This operation is usually referred to as flood fill because its effect is reminiscent of color streaming out of the selected pixel and into neighboring pixels in all four directions until it is stopped by a different color. The two images in Fig. 7.5 illustrate how flood fill works. When the user clicks on one of the white pixels in the center of the maze, all white pixels that are directly or indirectly connected to it are set to a new color. Two pixels are only considered connected if they are
horizontally or vertically adjacent, but not if they are diagonally adjacent.
Figure 7.5 Flood fill finds and colors a contiguous region of pixels in a raster image. One such region is shown in gray.
The simplest algorithm for flood fill uses an approach similar to breadth-first search. The main data structure is a queue of pixels in the image that is initialized to the pixel clicked by the user. Each step of the algorithm removes one pixel from this queue and inspect its four direct neighbors: Every
neighbor that has the same color as the current pixel (or, by extension, the starting pixel), it added to the back of the queue. We then set the current pixel to its new color and repeat the process until the queue is empty. The pixels in the queue are always on the boundary of the flooded area, which expands
outwards from the initial pixel.
a) Implement the flood fill algorithm. What happens in your implementation if the starting pixel already matches the new color?
This simple flood fill algorithm is fairly slow and consumes a lot of memory when working with large images because it has to process every pixel individually. More efficient algorithms can be obtained by processing multiple pixels at once. One such approach is based on the idea of a span, a
contiguous row of pixels with the same color. Two spans are considered adjacent if any of their pixels are adjacent and have the same color.
b) Consider the three rows of pixels shown in the following image:
How many spans are there and which spans are adjacent to each other?
c) Modify your implementation of flood fill to work with spans instead of individual pixels. Each entry in the queue represents a single span, and each step of the algorithm fills an entire span and adds neighboring spans to the back of the queue.
