The tracks in the following figure show the routes of $5$ trains, each starting from a starting station $S_i$ to a terminating station $T_i.$ The orange circles indicate the stations the trains must pass through and the arrows indicate the track followed by each train. You may assume that the trains take exactly one hour to move from one station to the next.

Given that the trains must begin their journeys in the morning, at either $8\mathrm{.}00,9\mathrm{.}00$ or $10\mathrm{.}00,$ we would like to come up with a safe schedule $($assigning a valid starting time$)$ for all trains such that the following constraints are satisfied:

No two trains arrive at any intersecting station at the same time. For example, Train $2$ and Train $3$ cannot depart at the same time because they would collide at the next station

All trains must arrive at their final destination on or before $14$:$00.$

When a train starts its journey, it can only terminate at the final destination.

Use this information to answer each of the following questions:

Question $1$: $[$Warm up$]$

a$)$ Given that all trains must depart at either $8$:$00,9$:$00,$ or $10$:$00$ and looking at the track travelled by Train $1,$ what can you say about its departure time?

b$)$ If Train $1$ starts its journey at $8$:$00,$ list all the times that Train $2$ can safely depart?

c$)$ If Train $1$ starts at $8$:$00$ and Train $2$ starts at $9$:$00,$ list all the times that Train $3$ can safely depart?

Question $2$: $[$CSP Formulation$]$

Formulate the train scheduling problem as a constraint satisfaction problem $($CSP$)$ by providing each of the following:

a$)$ What are the variables for this problem? Denote those variables by $x_1,x_2$dots

b$)$ What is the domain of each variable? Use the original definition without eliminating any values.

c$)$ Provide a complete list of constraints using precise mathematical notation. For example, you may say that $x_1+2x_2,$ where $x_1$ and $x_2$ are CSP variables. $($Hint: You should express all your constraints using $(=,,,).$

Question $3$: $[$Backtracking Search$]$

Based on your formulation in Question $2$ above, answer each of the following:

a$)$ Selecting variables in the order: Train $1,$ Train $2,$ Train $3,$ Train $4,$ Train $5$ and selecting values to assign in the order: $8$:$00,9$:$00,10$:$00,$ draw the entire search tree that is generated by the Backtracking Search algorithm until a successful complete assignment is found. How many nodes are generated? $($Hint: many nodes are generated$)$

b$)$ Suppose variables are selected in different order as in: Train $4,$ Train $1,$ Train $2,$ Train $3,$ Train $5,$ but with the same order of values, $8$:$00,9$:$00,10$:$00.$ Draw the entire search tree that is generated by the Backtracking Search algorithm until a successful complete assignment is found. Now, how many nodes are generated? $($Hint: a few nodes are generated$)$

c$)$ Compare your answers to $3($a$)$ with $3($b$).$ What do you observe? Does the order of selecting variables and values matter in the Backtracking Search algorithm?

Question $4$: $[$Consistency Checks$]$

As described in the lecture, there are many consistency checks that can be implement before we start the Backtracking Search algorithm. The objective of these consistency checks is to reduce the search space. Explore some of these:

a$)$ In your CSP formulation in $(2),$ you should have some unary constraints. Use these to prune the domains of the concerned variables and list the updated domains.

b$)$ Draw the Constraints Graph based on your results in $($a$)$ above and apply Arc Consistency on the graph to further prune the domains of the variables. List the updated domains.