Complete the breadth-first search version of the farmer, fox, chicken, corn puzzle. It should find the cheapest (fewest river crossings) solution always. Keep the coding as general as possible, so that the details of the puzzle (which animals are involved, who eats whom) are not part of the code at all, but are given as very simple data structures so the same program can solve any puzzle of a similar nature. There will always be a farmer, but everything else is variable. The rules will be in the form of a dictionary. The keys are the names of the characters and the values are sets of the names of the characters that the key would eat if the opportunity arose. e.g. The standard form of the puzzle is { "fox": {"chicken"}, "chicken": {"corn"}, "corn": {} } My incorrect version is { "fox": {"chicken"}, "goat", {"cabbage"}, "chicken": {"corn"}, "cabbage": {} } With a dinosaur { "fox": {"chicken"}, "chicken": {"corn"}, "corn": {}, "tyrannosaurus": {"fox", "chicken", "farmer"} } Do not be concerned with the last example, you do not need to take the possibility of one of the other characters eating the farmer take into account. Make the output neat, tidy, and comprehensible. Read the important rules on the class web page to be sure you are submitting correctly. Be sure that your program will properly detect that a given problem is insoluble. DIY: code the queue yourself, and make sure it doesn't involve any particularly inefficient operations Extra Credit (a bit) Convert it to use iterative deepening instead of a queue. This should be a separate program. I need to see both versions intact.