Write a program that employs backtracking

A farmer with a wolf, a goat, and a container of cabbage are on the west bank of the river. On the river is a boat in which the farmer and one of the other three (wolf, goat, or cabbage) can fit. If the wolf is left alone with the goat, the wolf will eat the goat. If the goat is left alone with the container of cabbage, the goat will eat the cabbage. Your goal is to transfer everyone to the other side of the river safely. Solve this problem using:

a. Depth first search

b. Breadth first search

Write a program that employs backtracking to solve the 8–Queens problem and then answer the following questions:

a. How many solutions are there?

b. How many of these solutions are distinct?

c. Which generator did your program employ?

We discussed The Missionaries and Cannibals Problem. Develop a solution to this problem given that the “moves” or “transitions” are forced. Identify “subgoal states” to the problem solution state which must be achieved in order to solve the problem.

Explain the role of computer chess with regard to AI.

 

Solution: