CSP Problem Set

6.1 How many solutions are there for the map-coloring problem in Figure 6.1? How many solutions if four colors are allowed? Two colors?

Answer:

we are looking at a map of Australia showing each of its states and territories, as in Figure 6.1, and that we are given the task of coloring each region either red, green, or blue in such a way that no neighboring regions have the same color.

To formulate this as a CSP, we define the variables to be the regions: WA, NT, Q, NSW, V , SA, and T.

The domain of each variable is the set {red; green; blue}.

The constraints require neighboring regions to have distinct colors; for example, the allowable combinations for WA and NT are the pairs {(red; green); (red; blue); (green; red); (green; blue); (blue; red); (blue; green)} . The constraint can also be represented more succinctly as the inequality WA NOT EQUAL TO NT, provided the constraint satisfaction algorithm has some way to evaluate such expressions. There are many possible solutions, such as {WA=red; NT =green; Q=red; NSW =green; V =red; SA=blue; T =red }.

6.2 Consider the problem of placing k knights on an n x n chessboard such that no two knights are attacking each other, where k is given and k≤n^2
a. Choose a CSP formulation. In your formulation, what are the variables?
b. What are the possible values of each variable?
c. What sets of variables are constrained, and how?
d. Now consider the problem of putting as many knights as possible on the board with-out any attacks.
e. Explain how to solve this with local search by defining appropriate ACTIONS and RESULT functions and a sensible objective function.
Answer:

(a) Solution A: There is a variable corresponding to each of the n2 positions on the board.
Solution B: There is a variable corresponding to each knight.

(b) Solution A: Each variable can take one of two values, {occupied, vacant}
Solution B: Each variable’s domain is the set of squares.

(c) Solution A: every pair of squares separated by a knight’s move is constrained, such that both cannot be occupied. Furthermore, the entire set of squares is constrained, such that the total number of occupied squares should be k.

Solution B: every pair of knights is constrained, such that no two knights can be on the same square or on squares separated by a knight’s move. Solution B may be preferable because there is no global constraint, although Solution A has the smaller state space when k is large.

(d) We will solve this using local search. Briefly describe in English a sensible successor function. Any solution must describe a complete-state formulation because we are using a local search algorithm. For simulated annealing, the successor function must completely connect the space; for random-restart, the goal state must be reachable by hill climbing from some initial state. Two basic classes of solutions are:
Solution A: ensure no attacks at any time. Actions are to remove any knight, add a knight in any un attacked square, or move a knight to any un attacked square.
Solution B: allow attacks but try to get rid of them. Actions are to remove any knight, add a knight in any square, or move a knight to any square.

(e) An objective function returns a number describing the desirability of the state. The key requirement is that the objective function must have its global optimum at the optimal solution (here, we are maximizing):
Solution A: the number of knights placed on the board. Since all states have no attacks, the global optimum of this function is in fact the optimal solution.
Solution B: Here we need to penalize for attacks. One might suggest maximizing #knights - #attacks, but one must be careful to avoid the possibility that the score can be improved by adding lots more knights at the cost of a few extra attacks. One can show that #knights - 2#attacks works

6.3 Consider the problem of construction (not solving) crossword puzzles: fitting words into a rectangular grid. The grid, which is given as part of the problem, specifies which squares are black and which are shaded. Assume that a list of words (i.e., a dictionary) is provided and that the task is to fill in the blank squares by using any subset of the list. Formulate this problem precisely in two ways:
a. As a general search problem. Choose an appropriate search algorithm and specify a heuristic function. Is it better to fill in the blanks one letter at a time or one word at a time?
b. As a constraint satisfaction problem. Should the variables be words or letters? Which formulation do you think will be better? Why?

Answer (a)
Problem formulation: Initial State: A grid of all empty squares, and a dictionary with all the words.

Goal: Every square (except the black ones) contains a letter, and every word slot (string of consecutive horizontal or vertical squares) contains a word from the dictionary. We might also want the constraint that no word is used more than once.

Successor function: There are many choices here. They break down roughly into word-at-a-time and letter at-a-time. We will go with word at a time: you can choose any word from the dictionary and place it in any word slot of the same length, as long as there are no contradictory letters already in place there. The resulting state has one more word slot lied in and (if we have the word-used-only-once constraint) one less word in the dictionary.
Path cost: No preference here, so each operator costs 1.

Search strategy: A constraint satisfaction algorithm is quite natural. The variables are the word slots, the domain of each variable is the list of words of appropriate length in the dictionary, and the constraints are that no word may be used twice, and that if two word slots intersect, they must have the same letter in the intersecting square. A* is also a reasonable approach for adding words to the puzzle.
Answer (b)
Heuristic: There are many choices here; the most-constrained-variable heuristic is an important one, but it is expensive to calculate exactly when the dictionary is large. That is, we don’t want to spend a lot of time going through 50,000 words to determine exactly how many t into each slot. We can get an estimate by choosing k words at random and seeing how many of them t into a slot. We can do the same with the

least-constraining-value heuristic: of the first k candidate words to all a slot, choose the one that imposes the least constraints on the intersecting slots. A* search requires a die rent sort of heuristic. If we know in advance where the black squares will be, then we can assign an estimated cost of 1 to every unlade word slot. This is admissible because a finished puzzle has no unlade word slots, and a puzzle with k unlade word slots requires at least k operations before achieving the goal state

6.4Give precise formulations for each of the following as constraint satisfaction problems:
a. Rectilinear floor-planning: find non-overlapping places in a large rectangle for a number of smaller rectangles.
b. Class scheduling: There is a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots for classes. Each professor has a set of classes that he or she can teach.
c. Hamiltonian tour: given a network of cities connected by roads, choose an order to visit all cities in a country without repeating any.

Answer (a)

To make this into a traditional constraint satisfaction problem, we will have to discretize the possible locations for the tiles. It’s clear that as we discretize more finely, we enable more possible solutions, but increase complexity. The most sensible solution is probably to have a variable for each small rectangle, which can take on, as values, possible locations of, say, its lower left corner within the big rectangle. It makes it relatively easy to check constraints, to see if any rectangles are overlapping. An alternative formulation is to have a variable for each location in the big rectangle, containing the value None or a value indicating one of the small rectangles overlaps that location. In this case, we automatically satisfy the non-overlapping constraint, but we’d have to work hard to be sure we had a coherent assignment (that is, the right number of contiguous locations were all assigned to the same small rectangle). One way to do it would be to assign a whole batch of them at once.

Answer (b) There are many choices here. Let’s say we have K classes, L profs, M possible times and N possible rooms.

Formulation 1: Have three different variables for each class: which professor, which time, and which room. So, we’d have K variables with domain size L, K with domain size M, and K with domain size N. Constraints would have to be that profs can’t be in two classes at the same time; that you can use the same room for two classes at the same time; that only appropriate professors are assigned to classes.

Formulation 2: Have two sets of variables, each of which have as their domain the K possible classes: L ×M variables representing professor time-slots and M× N variables representing room time slots. Constraints would have to be every class has to be assigned to exactly one room; that every class has to be assigned to exactly one prof; that only appropriate professors are assigned to classes. One rule of thumb is that it’s better to pick formulations in which variables have smaller domains, because the constraints can do more work for you in ruling out choices. Another rule of thumb is that its better to pick formulations that already have some of your constraints built in.