CS 4804 Homework #2
Date Assigned: September 12, 2003
Date Due: September 22, 2003, in class, before class starts
- (10 points) Give an example of a 4-node constraint graph with width=1. Use
a map coloring example.
- (10 points) Give an example of a 4-node constraint graph with width=2. Use
a map coloring example.
- (10 points) Give an example of a 4-node constraint graph with width=3. Use a
map coloring example.
- (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.
- (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.
- (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.