1) Problem 8.30
2) The following specifies the Wolf-Sheep-Cabbage game.
A farmer has a wolf, a sheep, and a cabbage. He also has a rowboat that can carry himself and one other item. The farmer is on the right bank of a river together with the boat, the wolf, the sheep, and the cabbage. He wants to move all the items to the other bank. But if the sheep is left alone with the cabbage, it will eat the cabbage. If the wolf is left alone with the sheep, it will eat the sheep. How can the farmer move everything to the left bank without anything being eaten?
Draw a graph that shows all the possible states and moves of this game. Each node is a state, and for each node, specify on which side of the river the boat, the wolf, the sheep, and the cabbage are. Each edge is a move. In each move, the farmer rows to the other bank, either with an empty boat or with a load. Mark all the nodes without outgoing edges as either winning states or losing states.
Assume you want to write a computer program to solve this puzzle. List all the nodes in the graph in depth-first order (with preorder) until you find a winning node. Then do a breadth-first search and list all the nodes in the order you access them until you find a winning node. Which was faster? Was there a reason why one was faster in this particular problem?
3) Write a backtracking algorithm that determines whether k (1<=k<=8) queens can threaten all squares of an 8-by-8 chess board. I.e., whether it is possible to arrange k queens in such a way that every square on the board is threatened.