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.
Since solutions (when found) are fast, use the doReps predicate to perform 1000 repetitions of each search and report those timings.
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.
- Define a state space for this problem by specifying the representation of a state and listing all possible moves from one state to another.
- 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.
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.
| || || || |
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.