$1.(2\mathrm{.}5\%)$ Consider the problem of placing k knights on an n$$n chess board such that no two knights are attacking each other, where k is given and k $$ n$2.$

$$ Choose a CSP formulation. What are the variables in your formulation?

$$ What are the possible values of each variable in your formulation?

$$ What sets of variables are constrained, and how?

$$

$2.(2\mathrm{.}5\%)$ At CSUSB, we have $5$ vehicles to take transfer students to a trip to the campus: A$,$ B$,$ C$,$ D$,$ and E and two stops: CGI building and JB Hall. Our job would be to schedule a time slot and a stop for each vehicle to either arrive at or leave the stop. The department gave us four possible time slots: $\{1,2,3,4\}$ for each stop, during which we can schedule a vehicle to arrive or leave.

Constraints:

$$ Vehicle B has lost its battery and must arrive in time slot $1.$

$$ Vehicle D can only arrive or leave during or after time slot $3.$

$$ Vehicle A is running low on fuel but can last until at most time slot $2.$

$$ Vehicle D must arrive before Vehicle C leaves, because some students must transfer from D to C$.$

$$ Vehicles A$,$ B$,$ and C cater to students from CGI and can only use the CGI stop.

$$ Vehicles D and E cater to students from JB Hall and can only use the JB Hall stop.

$$ No two vehicles can reserve the same time slot for the same stop.

$$

$1.$ Formulate this problem as a CSP where there is one variable per vehicle, reporting the domains and constraints $($e$.$g$.,$ the time slots are $\{1,2,3,4\}$ and stop are $\{$CGI$,$ JB Hall$\}.$ Also, list binary constraints on the classes. Your constraints should be specified formally, which should be implicit rather than explicit with words.

$2.$ Draw the constraint graph for your problem in item $1.$