Python language

Thank you!

Prelude A person, travelling with a wolf, a goat and a cabbage arrives at a river. There is a single small boat to afford passage across the river. The boat can hold the person and only one of the wolf, goat or cabbage. The person must ferry his animals and vegetable across the river making as many trips as necessary to do so. However, if the goat is left unattended with the cabbage, the goat will eat the cabbage. Similarly if the wolf is left unattended with the goat, the wolf will eat the goat. How can the person ferry all items across the river without anything being eaten? Overture For this assignment, you will be implementing a general-purpose graph search algorithm and three problem specific instance classes to which the program can be applied. You will be using your software to conduct a number of experiments. You will produce a beautiful and informative report detailing the results of your experiments. Background Download the file "Search Problem.py" from CourseLink. Extend the Search Problem class to implement classes for the following problems. First Task Use the Search Problem depth first search (DFS) algorithm to find a solution to the Cabbage, Goat, Wolf Problem. Determine the number of states that were visited by the search. Determine the depths (number of steps) to the solution state. Determine the number of non-looping paths to the solution state. (A looping path is any path that visits any state more than once.) This task will be partially developed in the lecture. Second Task The eight-puzzle consists of 8 sliding tiles, numbered 1 to 8, and one blank space placed in a 3x3 grid. The object of the puzzle is to move the number tiles into their respective positions (1 top left, 2 top middle, 3-top right, 4-middle left, 5=middle middle, 6middle right, 7=bottom left, 8 bottom middle, blankbottom right). In the code, make "continue search return false. Use the Search Problem depth first search algorithm to find solutions to the 8 puzzle for 50 randomly generated boards (create the boards by randomly placing the digits 1-8 in the 9 positions of the board; not by shuffling a board). For each of the 50 examples: Determine the number of states that were visited by the search. Determine the depths (number of steps) to the solution state. Determine the number of non-looping paths to the solution state. (A looping path is any path that visits any state more than once.) Third and Fourth Task Write a new search algorithm that can be used instead of "dfs" that takes one whole number argument. This search algorithm should do a breadth first search of the nodes at the depth given by the whole number argument. Wrap this algorithm in a loop that increases the whole number argument from 0 to 25. Repeat the first and second tasks with the new algorithm. Compare the number of states visited and depths of solutions found for the two approaches. When counting states visited make sure to add up the values for all the whole number arguments used