CS 4804 Homework #2

1. (10 points) We claimed in class that all n-ary constraints can be reformulated as binary constraints (i.e., so that the constraint graph need only have edges between two nodes, not between three or four nodes). Take the constraint satisfaction problem (CSP) shown in Fig. 5.2 (a) of your textbook and reformulate it as a CSP involving only binary constraints. For full credit, describe the variables, their domains, and the constraints.
   
   Hint: To use only binary constraints, you will have to artificially increase the number of variables (and constraints) beyond those given in the problem statement.
   
   
2. (10 points) We showed in class how the 8-queens problem and the graph coloring problem can be posed as a satisfiability (SAT) problem. Describe how to model the pigeonhole problem as a SAT problem. Here, the goal is to place (n+1) pigeons into n holes, so that no two pigeons occupy the same hole.
   
   Obviously the problem has no solution, but that is not our concern. We only have to model it as a SAT, turn it to a SAT solver, which will supposedly come back and tell us that there is no solution!
   
   For full credit, describe what the variables are (and how many there are), the clauses (and how many there are), and what these clauses will look like.
   
   
3. (20 points) Describe how you would model problem 5.13 of your textbook as a SAT problem. This is akin to a question from the analytical section of the GRE. For full credit, give the boolean variables, what they stand for, and identify all clauses they participate in.
   
   
4. (60 points) In this exercise, you are going to code up three different CSP programs for solving the n-queens puzzle. You will use a problem encoding so that each queen is already assigned to one row, so the only thing remaining to do is figure out which column each queen goes into.
   
   The first program is a mere backtracking search (i.e., depth-first search). The second program conducts forward propagation (i.e., after a queen is placed, it "flushes" out to find all positions where a new queen should not be placed, and reduces the domains of the future queen variables). It backtracks when a domain gets empty. Forward propagation is thus performed only with respect to the currently placed queen. The third program maintains arc-consistency, meaning it performs a full lookahead. It extends constraint propagation to even the queens that have not been placed. For instance, assume that we have placed queens Q1, Q2, Q3, and Q4. Maintaining arc consistency might simplify the domain of queen Q7 because for some setting(s) of this queen, there is no possible value of queen Q8. Use the algorithm given in Fig. 5.7 for implementing this approach. Once again, you backtrack when a domain becomes empty. The algorithm in 5.7 has to be implemented carefully, in order to ensure that the effect of removing values from a domain is properly "propagated" to neighboring values.
   
   Conduct a series of experiments for increasing "n" and record the number of states generated for each strategy, before finding a solution. Keep increasing "n" to see the range of problems you can tackle with each approach. Also time each program carefully (if possible, try to distinguish the time spent in constraint propagation from that spent in search). Make interesting observations about the search times, the effectiveness of the different strategies, and the range of problems that each strategy can solve.
   
   For full credit, give us an URL where your code can be checked (and downloaded, if necessary), write up a summary of how you did your experiments, and graphs/tables depicting the numbers you measured. Give English statements summarizing the conclusions and lessons learned.