Constraint satisfaction

Your task in this assignment is to write a general-purpose constraint solving algorithm, and apply it to solve several CSPs.

It’s useful to be able to build code from scratch. This time, I have not provided you any code. Make sure you read the detailed design notes below, however – they are based on my own solution. Here are the things you will need to do:

1. Write a simple backtracking solver.

2. (In parallel, probably.) Develop a framework that poses the map-coloring problem as a CSP that your solver can solve.

3. Test your solver on the map-coloring problem.

4. Write code that describes and solves the circuit-board layout problem. Solve it for at least the example case I have suggested. You should not have to write any more backtracking code; you should be able to use the same implementation you used for map-coloring.

5. Add an inference technique (MAC-3). Make it easy to enable or disable inference, since you will need to test effectiveness.

6. Add heuristics (MRV, LCV, etc). Make it easy to enable or disable each, since you will want to compare the effectiveness of your results, and since that will aid debugging.

7. In your write-up, describe your methodology, how you laid out problems, what you implemented for the backtracking search, and compare running time results using different heuristics and inference.

8. (Optional) Also implement min-conflicts and apply it to the three problems. There are further extra credit ideas described at the end of the assignment.

Design notes

Just like graph search, constraint satisfaction problems can be phrased in a very general way so that a single solver can be applied to different problems. Notice that (CSP) variable names don’t really matter in any fundamental way, for example. You could call Western Australia “WA”, or you could call it “0”; the CSP solver doesn’t care.

So I would recommend that you write some generic ConstraintSatisfactionProblem class, that solves CSPs with variables that are just numbers. Similarly, values might as well be integers; 0, 1, and 2 are equivalent to “r”, “g”, and “b”. Then an assignment would just be an array of ints. The index into the array would indicate which variable we are talking about, and the value at that location in the array would indicate the value.

Here’s an example. For the map-coloring problem, consider the variables WA, NT, and V. Give them indexes 0, 1, and 2, in that order. Consider the values “r”, “g”, and “b”. Let them correspond to integer values 1, 2, and 3. So an assignment (WA = g, NT = r, V = b). This might be written as

assignment[0] = 2;     //   WA = g  (WA has index 0, g has value 2)
assignment[1] = 1;     //   NT = r
assignment[2] = 3;     //   V = b

So your generic CSP solver just works with integers.

A constraint involves some variables, and, given assignments to each of those variables, is either satisfied, or is not.

You might have a constraint dictionary that maps from pairs of integers (corresponding to the indices of CSP variables involved in the constraint) to lists of pairs of integers (the list of allowable combinations of values for that pair of variables).

Now your MapColoringCSP would extend your basic CSP class. It would have a constructor that maps from some human-readable description of the particular CSP (maybe just a list of territory names and color domains) into an integer CSP. And then you’d have some output method that takes solutions to the integer CSP, and print them out nicely using territory names and colors. (The constructor might build a hashtable that maps from the integers back to strings for printing.)

Similarly, your circuit-board layout CSP class might do some initial processing to convert variable into integer indices, and values in the domains into integers too.

Map-coloring problem

Write a CSP that can solve the map-coloring problem for Australia as described in the book.

Constraints

The map-coloring problem involves several binary constraints. For each pair of adjacent countries, there is a binary constraint that prohibits those countries from having the same color.

The circuit-board layout problem

You are given a rectangular circuit board of size n x m, and k rectangular components of arbitrary sizes. Your job is to lay the components out in such a way that they do not overlap. For example, maybe you are given these components:

      bbbbb   cc
aaa   bbbbb   cc  eeeeeee
aaa           cc

and are asked to lay them out on a 10x3 grid

..........
..........
..........

A solution might be

eeeeeee.cc
aaabbbbbcc
aaabbbbbcc

Notice that in this case the solution is not unique!

The variables for this CSP will be the locations of the lower left corner of each component. Assume that the lower left corner of the board has coordinates (0, 0).

• In your write-up, describe the domain of a variable corresponding to a component of width w and height h, on a circuit board of width n and height m. Make sure the component fits completely on the board.

• Consider components a and b above, on a 10x3 board. In your write-up, write the constraint that enforces the fact that the two components may not overlap. Write out legal pairs of locations explicitly.

• Describe how your code converts constraints, etc, to integer values for use by the generic CSP solver.

Make sure your code displays the output in some nice (enough) way. Ascii art would be fine.

A particularly strong solution might consider several boards, of different sizes and with different numbers, sizes, and shapes of parts.

The CS 1 section assignment problem (optional extension)

At the beginning of every term in which CS 1 is offered, we need to assign students in the class into different sections. There are section leaders, and there are students. Each student and section leader fills out an availability form. We’ll simplify things for now and assume people are “available” or “not available” for a given time, and not worry about “prefer to avoid” times.

Then you get pair of long lists of comma-separated values: one for section leaders, and one for students:

Boba Fett, Monday 4:00, Monday 5:00, Monday 6:00, Tuesday 7:00, Wednesday 12:30
Chewbacca, Tuesday 6, Wednesday 4
...

Student names (and section leader names) are the variables; you might prepend an asterisk to section leader names to make it clear which is which in debugging. Values are section times. Domains for each variables are specified by the lists.

For test purposes, you will probably want to write a program that generates a few lists like this randomly, and saves them each in a text file. Student names like “student1” would be fine. Then your CSP can load that text file.

The goal is to find an assignment of students to sections that satisfies several constraints:

1. There is exactly one section leader in each section. (An alldiff constraint.)
2. There is no student in a section that does not also contain a section leader. (Notice that there are more available section times on the form than there will be sections.) This is also a global constraint, and will need to be specially implemented.
3. If there are n students, and k section leaders, than no section has fewer than n/k − 1 students, and no section has more than n/k + 1 students.

You do not need an explicit constraint to specify that a student can only meet at specified times – that’s part of the domain already. (You can think of the domain as a unary constraint.)

There are probably more- and less- efficient ways of implementing these global constraints. The easiest way is probably to use a partial assignment to build a set for each section, and test those sets for particular properties. You can test for the properties as the sets are constructed, for early termination.

Further extension ideas: Complete CS 1 section assignment package

The CS 1 section assignment is a real-world problem – for years, TAs have been assigning students to sections by printing out piles of surveys and shuffling them into different piles. It takes about 4 hours and the results are not always satisfactory.

For extra credit, improve your solution for this problem to the point where it could be practically applied. Do some or all of the following:

• Build a web page that allows students and section leaders to enter their names and select times, saving the results to a list. (This is just eye-candy, but if you really want this used…)

• Allow additional binary constraints. For example, section leader Sally and student Sam can’t be in the same section because they dated two years ago.

• Allow a gender-balancing constraint. Some students are uncomfortable being the only male in a section, or the only female. Require that there are either at least n/2k - 1 students of one gender in a section (including the section leader), or the section is uniform in gender (including the section leader). Obviously, this constraint will need more information to be entered in the list. Perhaps name, gender, time1, time2, ... would be the list format.

• Allow “might be available” times. One way to do this would be to score completed assignments, and keep searching until several assignments have been found; pick the best-scoring assignment.

• Min-conflicts. As soon as the sections are assigned, some clown invariably sends an e-mail saying their availability has changed. Maybe this doesn’t cause a constraint to be violated, but if it does, we don’t want to generate a completely new assignment. One possibly fix would be to use the min-conflicts algorithm to find a good assignment using a random walk, starting from the non-satisfying assignment generated after moving the single student.

Even more extension ideas

• There are some symmetries in solutions to the circuit-board layout problem. Any solution may be reflected either horizontally or vertically, giving the same answer. Describe how you would take advantage of this fact to increase the speed of your algorithm. Implement it. Measure the speed improvements on a few sample cases and discuss.

• Modify your circuit-board model to allow non-rectangular components.

• Apply your CSP solver to solve an interesting problem of your choosing. For example, Sudoku.

Rubric

Your code should be efficient and well-designed, with excellent style, formatting, comments. It should be brief if possible.

• Backtracking solver: 3
• Map-coloring framework and tests: 3
• Heuristics (MRV, LCV): 3
• Inference (MAC-3): 3
• Circuit-board: 3
• Discussion questions and discussion of implementation (report): 5
• Extensions beyond the basic requirements (CS 1, etc): up to 5 points

The assignment is out of 25 points, but 20 points is a pretty good score, corresponding to about an A-. (To get an A, you’ll need at least 22 points.) It is better to select a few extensions and do them well then to try to do everything imaginable.