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 A on wicked problems). If necessary, you may work individually, but your requirements will be essentially the same as those for partnerships.

Your team will formulate a problem and demonstrate problem solving with that formulation. You may choose problems from any of the three categories: wicked problems, uncommon puzzles, or common puzzles. The requirements vary from one category to another, due to the relative simplicity of formulating the common puzzles and difficulty of formulating a wicked problem. Thus if you select common puzzles, you will need to create three formulations and come up with more heuristics and/or a deeper analysis of them than if you select an uncommon puzzle. If you formulate a wicked problem, however, you don't have to actually solve your problem, but simply demonstrate that the formulation works and captures some essential features of the (wicked) problem. Note also that extra credit is available in options A and B, but not C; this is explained later.

The formulation must be in the same format as in Assignment 3, and must be compatible with the A3 starter code. Further details are given further down in this page.

Every student (i.e., both members of each partnership) should fill out the online questionnaire about your team and chosen option and problem(s) by Friday night at 11:45 PM. The 5 points of credit allocated to this questionnaire will only be awarded for on-time submissions.

(We expect most students to choose this option.) Identify some wicked problem that your team will "tame" by creating a formulation of it. Your formulation should involve each of the steps shown on Slide 25 (and Slides 26, 27, and 28) of the April 14 lecture slides.

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 21).

Before formulating your problem, explain why it fits the criteria of Rittel and Webber for being a wicked problem (at least criteria 1 and 6).

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. Solving the nuclear standoff with North Korea
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 h(s) that maps each state of your state space to a non-negative real number that represents the inverse of how good that state is in relation to the goal criteria. It can be thought of as a heuristic; however, it does not have to be admissible, and you might not even have a goal test in your formulation, if the problem does not have any clearly defined goal state. Explain what h(s) measures or computes and give some examples of states and their h values. In your formulation file, there should be a section in the following format:

  #
  def h1(state):
    pass # The code to computer your evaluation function goes here.
  
  HEURISTICS = [h1]
  #
  

• 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.
• In a file named Our-Wicked-Problem.pdf, write a summary that explains what you attempted to capture in your problem formulation, and the extent to which you believe you were successful.

In this option, your team will implement two problem formulations of the "uncommon puzzles" variety. Choose two types of puzzle from the collection at ... http://www2.stetson.edu/~efriedma/rubik/index.html. You may also consider puzzles from the websites linked from that page (under "Other Puzzle Collections").
Do NOT use any of the common puzzles or puzzles that you have already studied in this course. (And no 15 Puzzles -- they are almost the same as the 8 puzzle.) If in doubt, get an OK from the instructor.

Do either suboption C.3 (implement formulations of three of the following puzzles), or suboption C.2+ (implement formulations of two of the following puzzles plus do an in-depth analysis of heuristics for both of them).

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.)
6. Instant Insanity. (Given 4 unit cubes, whose faces are pre-colored using colors from the set { red, white, green, blue }, arrange them in a tower, such that each of the four sides of the tower has all 4 of the different colors showing. This is a standard puzzle and you can see lots of illustrations of it online by doing a Google image search for "instant insanity". In some instances of the puzzle, the color white is not used, and yellow is used instead.

For each puzzle that you implement, create a formulation file, using the same format as used for Assignment 3. It should include the following (except that in Option A you don't need a goal test):

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 C 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 for each problem formulation. Except for in Option A, it should be an admissible heuristic that is not zero. If you are doing Option C.2+, then you should have at least two heuristics per problem formulation. In your problem formulation file, put your heuristic(s) for that problem in a list like this (and here we see three heuristics listed for this problem formulation):

   HEURISTICS = [h1, h2, h3]
   

5. Make each 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." The function should be a method in the State class, and it should be named __str__ and have the signature __str__(self) Here's an example for the Eight puzzle:

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

No matter whether you are doing Option A, B, or C, your main file should not immediately crash when imported by the Assignment 3 starter code program ItrDFS.py. However, you do not need to turn in anything to demonstrate that compatibility.

For Option B or C, provide a transcript of a test run that shows a solution found by either BreadthFS.py or AStar.py using your formulation. Make this an appendix of your pdf report. This will be especially helpful to the human graders if something goes wrong between your code and the autograder.

If you are doing Option C.2+, develop tests that show the relative performance of Breadth-First Search, A* with heuristic 1, and A* with heuristic 2. Your two 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 or Option C.3, then you only need to compare Breadth-First Search with A* using one heuristic function (for each of your problem formulations).

Depending on which option you are doing, you may be eligible for extra credit:

• Option A: 10 points of extra credit for a clean and thoughtful working formulation of one of the wicked problems. Awarding of this extra credit will be at the discretion of the instructional team. Clear and thoughtful explanations within the document "Our-Wicked-Problem.pdf" are likely to be helpful if you are hoping for extra credit.
• Option B: 5 points of extra credit for a clean and thorough job done on at least one of your two uncommon puzzles or problems; Clear and thoughtful explanations within the document "Our-Uncommon-Puzzle.pdf" are likely to be helpful if you are hoping for extra credit.
• Option C: no extra credit.

A Python File called who_and_what.py:

A skeleton version of this file called who_and_what.py is given here. Fill in the missing portions of the file as indicated in the comments within the file. Run the program before and after you edit it, so you can see what it is supposed to do and contain, and whether your own information has been correctly entered.

Portions of this assignment will be evaluated by an autograder. The autograder will first look for this file and then take additional actions based on the information you put in this file. Once you have filled in the missing information, you can run the file as a program, and its output will help you make sure all the data about you and your partner is correct. Be sure to complete the file and turn it in.

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, in pdf format with a name that depends on your option as follows. Option A: Our-Wicked-Problem.pdf; Option B: Our-Uncommon-Puzzles.pdf; Option C: Our-Common-Puzzles.pdf. This file will give 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.

This assignment is worth 100 points per student. In a partnership, the instructional staff will assume that both partners contributed equally to the assignment results, unless we have some important reason to believe differently. We hope that each student will work to the benefit of the partnership and to providing complementary knowledge, skills, and efforts. Ideally, both parters will learn new things and improve their skills during the assignment.

The planning questionnaire responses are due Friday, April 21. Each student should respond separately, even though you are in partnerships. Each student who responds by the deadline will earn 5 points towards the 100 points available in the assignment.

If your file who_and_what.py provides all correct information, and it works successfully, allowing the autograder to automatically import and test your problem formulations, you'll get an additional 5 points, even if your formulations don't work.

Your report is worth 25 points. It includes basic documentation that includes the facts you put in who_and_what.py but elaborates on your problem formulation, describing how you designed your state representations, set of operators, and heuristic functions. Describe the intuition behind each heuristic function for A*, and finally, if doing Option C.2+, explain, as best you can, why one of the heuristics is performing better than the other (if that is true).

If you are doing Option B or Option C, then you should have a section on TESTING OF HEURISTICS that gives the statistics you were asked for in the option's description. Finally, you should have your Retrospective section as described earlier.

The remaining 65 points are for your problem formulations, heuristics, and code for testing.

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