This assignment should be done in partnerships. Most partnerships will be teams of two students. In a few cases, teams of three will be permitted (and only in Option C on wicked problems). If necessary, you may work individually, but your requirements will be essentially the same as those for partnerships.

Fill out the online questionnaire about your team and chosen option and problem by Friday night at 11:45 PM.

1. Peg solitare. (See http://http://en.wikipedia.org/wiki/Peg_solitaire). Select either the English version or the European version.
2. Sudoku. (Develop a general solver, but provide some specific example puzzles yourselves.)
3. Rubik's Cube
4. Pentominos. (goal is to fill a 6 by 10 board.)
5. Mazes. (If you choose this option, your team should write, in addition to the formulation for solving and the heuristics, an instance generator that, given the dimensions N and M and a random seed R, comes up with a new, solvable maze; your maze generator should use the algorithm presented in CSE 373 that uses the Disjoint Sets (UNION/FIND) abstract data type to keep track of the sets of connected cells of the maze.)

1. One or more alternative initial states. Provide a function CREATE_INITIAL_STATE or alternative versions of such a function. For example, if you are doing Option A and mazes, you might define one version of your function this way:

   def CREATE_INITIAL_STATE():
     return Maze(8, 15, 0) # Assumes your maze generator is defined as a class within COMMON_CODE.
   

2. GOAL_TEST(s).
3. OPERATORS: A list of operators sufficient to solve any solvable instance of the problem.
4. Include at least one heuristic evaluation function. It should be an admissible heuristic that is not zero. If you are doing Option A, then include at least two different heuristic evaluation functions and a means to specify one or the other in each run.
5. Make this formulation work with: ItrDFS, BreadthFS, and AStar.
6. Create a function that can display a state of the puzzle in some easy-to-read way, possibly using "ASCII art." Here's an example for the Eight puzzle:

   <STATE_VIS>
   def render_state(s):
     txt = "\n"
     for i in range(3):
         for j in range(3):
           txt += str(TILE_NAMES[s[i*3 + j]])+' '
         txt += "\n"
     return txt
   </STATE_VIS>
   

Provide a test run that shows a solution found by either BreadthFS.py or AStar.py using your formulation.

If you are doing Option A, develop tests that show the relative performance of Breadth-First Search, A* with heuristic 1, and A* with heuristic 2. If you wish, you can use two separate graphs, one comparing Breadth-First Search and A* with one heuristic, and another comparing just the two versions of A*. Each graph should be created with examples that help the reader understand the differences in performance from the heuristics. Your heuristics themselves should use different insights about the problem, and they should not be closely related, such as one being some constant multiple of the other.

If you are doing Option B, then you only need to compare Breadth-First Search with A* using one heuristic function.

In your report file, describe your approach to formulating the problem. Describe the intuition behind each heuristic function for A*, and finally explain, as best you can, why one of the heuristics is performing better than the other (if that is true).

You may select some problem you feel is a wicked problem and use that, but if in any doubt, get clearance from the instructor, either via email or through the web questionnaire on Friday (April 24).

Before formulating your problem, explain why it fits the criteria of Rittel and Webber for being a wicked problem.

Here are a few sample wicked problems to help you come up with your own.

1. Designing a plan to deal with the Zika virus (A possible resource is here)
2. Fixing world poverty
3. Design of buildings for environmental sustainability
4. Finding a cure for cancer
5. Avoiding another world war
6. Cleaning the detritus in space in near-earth orbit
7. Fixing California's water problem
8. Designing a website for the United Nations
9. Saving fish stocks from overfishing or even extinction
10. Creating a secure and safe Internet

• Create an evaluation function Q(s) that maps each state of your state space to a non-negative real number that represents how good that state is in relation to the goal criteria. Explain what Q(s) measures or computes and give some examples of states and their Q values.
• Demonstrate that your problem formulation works by showing some alternative candidate solutions and the derivations (operators and state sequences) that produce them. At the very least, each operator should be demonstrated by giving "before-and-after" state pairs with an explanation of what has changed.
• Write a summary that explains what you attempted to capture in your problem formulation, and the extent to which you believe you were successful.

Python Files: Your Python files should begin with a multiline string that gives, on the first line, your names, and on the next lines: the problem being formulated, and the status of the program represented by the file.
Textual Report File: Also turn in a text file, report.txt or report.pdf, that gives the answers and explanations required by your problem option. The text file should also begin with your names and give the same information as to what problem is being formulated. Then it should identify by name the main Python file. Other Python files might then contain examples, or modules to be imported by your main Python file.

Include in your report a section called "Retrospective" that explains (a) what each team member contributed to the partnership's work, and (b) in each team member's own words, what he or she learned by doing this assignment.

If necessary, updates and corrections will be posted here and/or mentioned in class or on GoPost.

After submitting your solution, please answer this survey