Give a precise formulation of the following constraint satis

Give a precise formulation of the following constraint satisfaction problem (i.e. define variables, domains of variables, constraints):
(a) Class scheduling: There is a xed 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.

Solution

a) four variables which are represented in this problem are: : Teachers, Subjects, Classrooms and Time slots. We

can use two constraint matrices, Tij and Sij . Tij represents a teacher in classroom i at time j. Sij represents a

subject being taught in classroom i at time j. The domain of each Tij variable is the set of teachers. The domain

of each Sij variable is the set of subjects. Let’s denote by D(t) the set of subjects that teacher named can teach.

The constraints are: Tij 6= Tkj k 6= I which enforces that no teacher is assigned to two classes which take place at

the same time. There is a constraint between every Sij and Tij , denoted Cij (t, s) that ensured that if teacher t is

assigned to Tij , then Sij is assigned a value from D(t). An example for the constraint C is

C(Tij , Sij ) = {(Dechter, 6a),(Dechter, 171),(Dechter, 175a),(Smyth, 171),(Smyth, 278),(Irani, 6a), . . .}

In general C(Tij , Sij ) = {(t, s)| teacher t can teach subject s}