15-381/681 Homework 2

Part I: Experimenting with Constraint Satisfaction Solvers [23 points]

Download the file csp-files.zip and extract its contents. It contains copies of utils.py and search.py that you will be familiar with from Homework 1, plus a new file csp2.py that contains two constraint satisfaction solvers. One uses backtracking search; the other uses local search with the min-conflicts heuristic.

Also included in the file are several sample map coloring problems: the states of Australia (used in the textbook), the provinces of France, and the states of the US. In the case of France there are two coloring problems: one using four colors and one using three; the latter is unsolvable.

The constraint solvers will tell you how many variable assignments they made before finding a solution or giving up. You can run a search problem by typing an expression such as the following: 

            backtracking_search(australia)

            min_conflicts(australia)

Read through the code in csp2.py before proceeding further.

Q1: (2 pts) How many assignments does backtracking search use on the 'france' problem?

Q2: (2 pts) Run min_conflicts search on the 'france' problem 10 times. What is the minimum number of assignments used? What is the maximum? What is the mean?

Q3: (2 pts) Local search algorithms that make random changes don't know when to quit. What happens when you run min_conflicts on the 'france3' problem?

Q4: (2 pts) What happens when you run backtracking_search on the 'france3' problem?

Q5: (2 pts) The default backtracking_search algorithm uses no heuristics. It can work acceptably for small problems, but is overwhelmed by larger ones. What happens when you run the backtracking_search algorithm on the 'usa' problem? Specify an assignment_limit parameter of 500,000.

Q6: (2 pts) How does min_conflicts do on the 'usa' problem? Run it 10 times and give the min, max, and mean values.

Q7: (2 pts) Constraint propagation is a powerful technique for reducing the size of the search space. The mac (Maintain Arc Consistency) heuristic included in the file csp2.py uses the AC3 algorithm discussed in the book and in class. How does backtracking search perform on the 'usa' problem if you use the mac heuristic?

Q8: (2 pts) MRV (minimum remaining values) is another heuristic we discussed. How does backtracking search perform on the 'usa' problem if you use both the mac and mrv heuristics?

Q9: (5 pts) Create a new constraint satisfaction problem called 'southam' that colors a map of South America with the colors RGBY. Including the Falklands but excluding Panama, there should be 14 states or territories. How many assignments does ordinary backtracking_search require?

Q10: (2 pts) Create an RGB version of the South America problem called southam3. How many assignments does ordinary backtracking_search require in order to fail? What about if you add the MAC heuristic?

Part II: Programming Constraint Satisfaction [64 points]

In this section you are going to create a new type of constraint satisfaction problem called CryptCSP for cryptarithmeic problems, similar to how the MapColoringCSP function in csp2.py describes map coloring problems. Add your code to the end of the csp2.py file. The function CryptCSP should take three string arguments X, Y, and Z, and construct a CSP object describing the cryptarithmetic problem X+Y=Z. We can then solve that problem by calling one of our two solvers. For example:

          crypt1 = CryptCSP('TWO', 'TWO', 'FOUR')

          backtracking_search(crypt1)
As discussed in the textbook, cryptarithmetic problems require additional variables Ci to denote the carry from one column to the next.

Cryptarithmetic problems use n-ary constraints to express the relationships among variables. But the AC3 constraint propagation algorithm only works for binary constraints. Therefore you will need to generate binary constraints from your n-ary constraints. See this page for an explanation of how to do that.

Q11. (60 pts) Write the CryptCSP() function and any auxiliary functions you need to implement cryptarithmetic. We are going to provide an autograder, so make sure that you name your basic variables as single letters like 'F' or 'R'; you can use whatever names you like for the remaining variables.

Q12. (2 pts) For each of the following problems, report how many assignments backtracking_search takes when no heuristics are used, and how many it takes when constraint propagation (MAC) is used:

  1. TWO + TWO = FOUR
  2. SEND + MORE = MONEY
  3. BASE + BALL = GAMES
  4. HAVE + LOVE = PEACE
  5. TURKEY + DINNER = UNITES

Q13. (2 pts) How well does the min_conflicts solver do on TWO + TWO = FOUR? Be sure to run it at least 10 times.

Part III: Propositional Logic [13 points]

Q14. (4 pts) The relationship in the wumpus world between pits and breezes can be expressed as a biconditional. Write down the biconditional for B2,2 in a 4x4 wumpus world.

Q15. (4 pts) Convert the biconditional to conjunctive normal form, i.e., to a set of clauses (the conjunction is implicit).

Q16. (5 pts) Can Wumpus world inference be expressed entirely as Horn clauses? Give an argument to support your answer.

Hand-in Instructions

Create a zip archive containing exactly these files: (1) your modified csp2.py file, (2) an answers.pdf file containing your answers to the written questions in Parts I-III, and (3) a README.txt file with your name and Andrew id. Note: do not use other archive formats such as tar, rar, or bz2; you must submit a zip file.

Submit your zip file via Autolab.

Back to class home page.