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
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
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
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
crypt1 = CryptCSP('TWO', 'TWO', 'FOUR')
Q13. (2 pts) How well does the min_conflicts solver do on TWO +
TWO = FOUR? Be sure to run it at least 10 times.
- TWO + TWO = FOUR
- SEND + MORE = MONEY
- BASE + BALL = GAMES
- HAVE + LOVE = PEACE
- TURKEY + DINNER = UNITES
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.
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.