HW2: Constraint Satisfaction Problems Solution

    • Crossword Puzzles Part I

(This is a variant of exercise 6.3 from the book.) Consider the problem of constructing (not solv-ing) crossword puzzles: tting words into a rectangular grid. The grid, which is given as part of the problem, speci es which squares are blank (i.e., can contain letters) and which squares are shaded (i.e., cannot contain letters). Assume also that a list of words (i.e., a dictionary) is pro-vided. The task is to ll in the blank squares using any subset of the list.

    1. Formulate this problem as a CSP where the variables are words. List all the variables and constraints.

    2. Formulate this problem as a CSP where the variables are letters. List all the variables and constraints.

    3. Suppose we wish to make sure the the crossword puzzle we generate doesn’t contain mul-tiple words that are \too similar." We’ll say that words w1 and w2 are too similar if either one can be obtained from the other by changing exactly one character or one is a substring of the other. For instance \dog" and \dogs" are too similar (by the second constraint) as are \dog" and \dog" (again, by the second constraint). Similarly, \cats" and \cots" are too similar (by the rst constraint). How would you specify these additional constraints in both the by-word and by-letter formulations?


    • Arc Consistency

While skiing at Alta last week, Alice (our venarable computer science student) decides that she wants to get a minor in math. She has already taken many of the requirements as part of her CS degree; all that remains are the following courses:

She must take both Analysis (A) and Analysis II (B). She then has three electives of which she must take two; these are: Linear Algebra (C), Number Theory (D) and Modern Algebra (E)1. Alice has three more semesters of study to go. Fortunately, every course is o ered every semester, but she can take at most two math courses during any given semester.

Of course, there are constraints on how she must take the courses. Obviously she must take Anal-ysis (A) before Analysis II (B). She must also take Linear Algebra (C) before Number Theory (D). She can only take Number Theory (D) once she’s taken Modern Algebra (E). Sadly, Analysis

    (A) and Linear Algebra (C) are always o ered at exactly the same time, so she cannot take both in the same semester.


    • This is not exactly the requirements for the math minor at the U, but is close.


1
We will now formulate Alice’s scheduling problem as a CSP in which each variable corresponds to a class Alice must take and the values correspond to the numbering of the remaining semesters: 1 for junior Spring, 2 for senior Fall and 3 for senior Spring; 1 for \does not take this course."

    1. Find an assignment of the variables to values (just by trial and error) that satis es the con-straints.

    2. State the domain of the variables and the constraints in mathematical notation using the following symbols: =; 6=; <; >; ; .
    3. We now solve this CSP using backtracking search with arc consistency. Namely, we wull run the AC-3 algorithm as a preprocessor and after each variable assignment. When there is ambiguity as to which variable to assign next, assign a value to the variable corresponding with the course letter that comes rst alphabetically. Furthermore, when the next value to assign to a variable is ambiguous, break ties by assigning the earliest value rst.

        (a) What are the remaining domains after enforcing arc consistency on the initial CSP with no assignments?

        (b) What are the remaining domains after assigning A = 1 and re-enforcing arc consis-tency?

    4. Suppose we’re running AC-3 but trying to get Alice to nish in only one semester instead of three. Sketch a complete run of AC-3 under these new constraints followed by applying all unary constraints and say precisely when it will fail and how many states are expanded before failing.






























2