This assignment involves writing and analyzing search-oriented programs. The first three problems involve state space search using various uninformed control strategies. The fourth problem is constraint-based, requiring a Test&Generate approach.

1. Use the built-in time predicate to compare the performance of each of the uninformed controls strategies on the examples from the lecture. In particular, use dfs, dfs_no_cycles, dfs_no_cycles_deep, and bfs to perform state space searches for
   • travel.pro: loc(omaha) --> loc(los_angeles)
   • jugs.pro: jugs(0,0) --> jugs(2,0)
   • puzzle.pro: tiles([1,2,3],[8,6,space],[7,5,4]) --> tiles([1,2,3],[8,space,4],[7,6,5])

   Since solutions (when found) are fast, use the doReps predicate to perform 1000 repetitions of each search and report those timings.
   
   

2. Consider the following problem:

   Three missionaries and three cannibals seek to cross a river, say from the left bank to the right bank. A boat that may be navigated by any combination of one or two people is available on their side of the river. If the missionaries on either side of the river are outnumbered at any time by cannibals, the cannibals will indulge in their anthropophagic tendencies and do away with the missionaries. Find a sequence of boat trips that will permit all the missionaries and cannibals to cross the river safely.

   1. Define a state space for this problem by specifying the representation of a state and listing all possible moves from one state to another.
      
      
   2. Attempt to solve this problem using the various uninformed search control strategies provided, i.e. dfs, dfs_no_cycles, dfs_no_cycles_deep, and bfs. Discuss the behaviors of each of these approaches. For example, if a strategy fails, explain why this would happen. Similarly, if one strategy outperforms another, explain why.

3. Consider a generalization of the previous problem where there are five missionaries and five cannibals that need to cross the river. The boat can handle up to three people, but the number of cannibals on the boat must never exceed the number of missionaries. As in the previous question, define a state space for this problem, attempt to solve the problem using each of the uninformed strategies, and explain your results.
   
   
4. We saw in class that Prolog's built-in search can be useful in solving constraint problems using the Test&Generate paradigm. Similar to the examples discussed, write a Prolog program that solves the following puzzle. In addition, note how many different combinations of possible solutions there are. Would Generate&Test be feasible?

   Consider the following people: Aaron, Beth, Chris, and Denita.
   Each person has a favorite color: red, blue, yellow, or green.
   Each person has a favorite food: chili, steak, pasta, or broccoli.
   Also, each person idolizes someone in the group (possibly himself/herself).
   

   Note: favorite colors, foods, and idols are unique, i.e. no color, food or idol is chosen by more than one person.

   Determine which color, food and idol goes with each person using the following information.

   • Aaron's favorite food is chili.
   • The person whose favorite color is red likes steak.
   • There is someone who idolizes himself/herself.
   • The person whose favorite color is yellow idolizes Denita.
   • The person whose favorite food is pasta is idolized by the person whose favorite color is blue.
   • The person who idolizes Chris likes chili.
   • The person who like blue idolizes the person who likes yellow.

ADDITIONAL QUESTION FOR GRADUATE STUDENTS:

5. Consider the following sliding-blocks puzle, consisting of some number of black tiles, the same number of white tiles, and an empty space. The initial configuration for the puzzle consists of all the black tiles to the left, all of the white tiles to the right, and the empty space in the middle. For example, the following shows the initial configuration when there are two tiles of each color:

   B

   B

   W

   W

   The goal is to reverse the locations of the tiles, i.e., have all white tiles to the left and all black tiles to the right, with the space in the middle. There are two types of moves allowed. A tile can move into an adjacent empty space, or it can jump over two adjacent tiles into the empty space.

   1. Define a state space for this problem by specifying the representation of a state and listing all possible moves from one state to another.
      
      
   2. Attempt to solve this problem where there are two white tiles and two black tiles, using the uninformed search control strategies provided: dfs, dfs_no_cycles, dfs_no_cycles_deep, and bfs. Discuss the behaviors of each of these approaches. For example, if a strategy fails, explain why this would happen. Similarly, if one strategy outperforms another, explain why.
      
      
   3. Now attempt to solve this problem when there are three tiles of each color. Use each of the uninformed control strategies and discuss the results as before.