1. Represent the following class scheduling problem as a discrete CSP: 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 class that he or she can teach.
2. Consider the rectangle packing problem: find nonoverlapping places in a large rectangle for a number of smaller rectangles.
(a) Suppose the height and width of every rectangle is a integer value in the range 1 to N. Represent this problem as a discrete-valued CSP.
(b) Suppose instead the heights and widths are real values in the range (0,N]. Represent this problem as a CSP where the values of the variables are tuples of real numbers.
(c) How can you efficiently solve a rectangle packing CSP? Read the paper
Optimal Rectangle Packing: A Meta-CSP Approach, by Michael D. Moffitt & Martha E. Pollack. Proceedings of the 16th International Conference on Automated Planning & Scheduling (ICAPS-2006)
http://www.eecs.umich.edu/~mmoffitt/papers/moffitt_icaps2006.pdf
and write a short summary of their approach.
3. Sudoku is easy to solve by constraint satisfaction. Write a CSP solver for Sudoku that implements forward checking. Does it ever need to backtrack when given a good (published) Sudoku? Try taking a Sudoku and erasing some of the clues before giving it to your solver. Now might it need to backtrack? What does this suggest about the relationship between the number of clues and the difficulty of solving Sudoku type problems?