CS 4804 Homework #2

Date Assigned: September 12, 2003
Date Due: September 22, 2003, in class, before class starts
  1. (10 points) Give an example of a 4-node constraint graph with width=1. Use a map coloring example.

  2. (10 points) Give an example of a 4-node constraint graph with width=2. Use a map coloring example.

  3. (10 points) Give an example of a 4-node constraint graph with width=3. Use a map coloring example.

  4. (20 points; from the Spring 2003 midterm) The magic square puzzle is the problem of placing the numbers from 1 to 9 on a 3-by-3 grid such that each position is occupied by a unique number and the sum of the numbers along a row, column, or diagonal equals 15. One solution to this puzzle is given below:
    
    8 1 6
    3 5 7
    4 9 2
    
    Pose the magic square puzzle as a boolean satisfiability (SAT) problem in CNF form, i.e., the boolean expression must be a conjunction of disjunctions of propositional variables. For full credit, state what the variables are, how many there are, and identify the clauses they participate in. Give enough examples of the clauses to convince us that you understand what is going on.

    You do not have to solve the puzzle. You do not have to code anything up; Just state the problem as a SAT problem.

  5. (20 points) Take a look at the description of the 3x3 Rubik's tangle puzzle at http://members.lycos.nl/rubik/tangle3.html. Pose this puzzle as a boolean satisfiability (SAT) problem in CNF form, i.e., the boolean expression must be a conjunction of disjunctions of propositional variables. For full credit, state what the variables are, how many there are, and identify the clauses they participate in. Give enough examples of the clauses to convince us that you understand what is going on.

    You do not have to solve the puzzle (at least not in this question). You do not have to code anything up (at least not in this question); Just state the problem as a SAT problem.

  6. (30 points) In this exercise, you are going to actually (!) solve the 3x3 Rubik's tangle puzzle using traditional constraint solving techniques. You are not going to solve it as a SAT problem (although that is how you posed it in the previous question); instead, you are going to think of it as a traditional CSP (domains, variables, constraints, representable as a constraint graph) and use traditional CSP techniques (e.g., backtracking, maintaining arc-consistency etc.).

    Use the following problem formulation. Each level of the search tree corresponds to one of the tile positions to be placed; thefore the solution lies at depth 9. At each level, you choose a tile to be placed for that position (from among the remaining tiles) and continue.

    The first program you will implement is a mere backtracking search (i.e., depth-first search). The second program conducts what is called forward propagation (read the book to see what this is about). Here, after a tile is placed in a given position, it "flushes" out to find all positions where a new tile should not be placed, and reduces the domains of the future position variables). It backtracks when a domain gets empty. Forward propagation is thus performed only with respect to the currently placed tile. The third program maintains arc-consistency, meaning it performs a full lookahead. It extends constraint propagation to even the tiles that have not been placed. For instance, assume that we have placed tiles in positions P1, P2, P3, and P4. Maintaining arc consistency might simplify the domain of position P7 because for some tile setting(s) of this position, there is no possible value for position P8. 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.

    Which of your three programs runs fastest? Time each carefully, taking care to distinguish the time spent in constraint propagation from that spent in search - i.e., "thinking" versus "doing". 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 represented the states, operators, the specific manner in which you did your experiments, and graphs/tables depicting the numbers you measured. Give English statements summarizing the conclusions and lessons learned.

    Extra Credit: Extend your code to work for the Rubik's 5x5 tangle.

Return Home