Consider a scheduling problem, where there are five activities to be scheduled in four time slots. Suppose we represent the activities by the variables

$$

$,$

$$

$,$

$$

$,$

$$

$,$ and

$$

$,$ where the domain of each variable is

$\{$

$1$

$,$

$2$

$,$

$3$

$,$

$4$

$\}$

and the constraints are

$$

$>$

$$

$,$

$$

$>$

$$

$,$

$$

$!=$

$$

$,$

$$

$>$

$$

$,$

$$

$!=$

$$

$,$

$$

$>=$

$$

$,$

$$

$!=$

$$

$,$ and

$$

$!=$

$$

$+$

$1$

$.[$Before you start this, try to find the legal schedule$($s$)$ using your own intuitions.$]$

$($a$)$ Show how backtracking solves this problem. To do this, you should draw the search tree generated to find all answers. Indicate clearly the valid schedule$($s$).$ Make sure you choose a reasonable variable ordering.

To indicate the search tree, write it in text form with each branch on one line. For example, suppose we had variables

$$

$,$

$$

$,$ and

$$

with domains

$$

$,$

$$

and constraints

$$

$!=$

$$

and

$$

$!=$

$$

$.$ The corresponding search tree is written as

X$=$t Y$=$t failure

Y$=$f Z$=$t solution

Z$=$f failure

X$=$f Y$=$t Z$=$t failure

Z$=$f solution

Y$=$f failure

$[$Hint: It may be easier to write a program to generate such a tree for a particular problem than to do it by hand.$]$