Course scheduling is a practical problem in that multiple courses are scheduled to be offered at different time slots in classrooms. Course scheduling problem could be generally modeled as a Constraint Satisfaction Problem.

As we discussed in the class, for each course there are two attributes: classroom and time which have the impact to the scheduling. Here is a toy example of the course scheduling problem: there are five courses {A, B, C, D, E}, four time slots {1, 2, 3, 4} and there are two classrooms {I, J} (I stands for Integrated lab classroom, while J stands for Joyful classroom). For each classroom, we could only schedule one course at a time.

Here are some other constraints:

 

Course B must be offered at time slot 1

Course D must be offered at time slot 3 or after

Course A is to be offered at time slot 1 or 2

Course D must be offered before C

Courses A, B, C need to use computer lab, so they would rather be scheduled to classroom I, Course D and E would use classroom J.

 

In this assignment, you are asked to implement solving the course scheduling problem based on the modified arc consistency algorithm.

 

You need to implement the following steps:

1. based on all the constraints, build the constraint graph (with programming, but not manually build the graph)

2. Implement the minimum remaining values (MRV) heuristic, it will be used to order the variables when there is a need to select among many variables for consideration. e.g., you could use it to determine how to choose a variable to assign value in the backtracking-search algorithm, or you may try to manage the arcs in the queue in ARC algorithm, etc.

3. enforce unary constraints, if there are existing unary constraints, we could easily reduce the domain(s) on those related variables.

4. Implement forward-checking on top of the backtracking search, again, you could utilize the sample code provided, but please make sure you have a new function named "forward-checking" to differentiate it from the original backtracking search.

5. arc consistency algorithm, I would suggest you to integrate above features if possible to improve the standard ARC.