Question $5$: Constraint satisfaction problems

$3]$

A local wildlife farm wants to donate animals to the local Zoo. These include lions, zebras, elephants and rhinos. The Zoo has enclosures where they can place these animals. They want to avoid placing the same species of animal in adjacent cages. The lions are a problem as well, because the zoo cannot place the lions adjacent to the zebras.

The map layout of the enclosures are as in the diagram below. For example, $E$ is adjacent to B$,$ C$,$ D$,$ F$,$ G and H$,$ but not adiacent to A and I.

$($a$)$ Consider the task of deciding which animals need to be placed into which enclosure as a constraint satisfaction problem $($CSP$).$ Define the variables, the domains of the variables, as well as the constraints of the problem, using the variables you have defined. Use the correct mathematical notation and operators.

$($b$)$ Draw the constraint graph for this CSP$.$

$($c$)$ Using any form of backtracking search, solve this CSP problem. Start with assigning Lion to a node $($think about which node is a good place to start the search$).$ Assign the rest of the animals in the sequence Elephant, Giraffe, Rhino $($this is alphabetical$).$

$($d$)$ BONUS MARKS $-$ What would happen to this CSP problem if you defined the alldiff$()$ constraint for the placement of the animals?

$(2($bonus$))$