Read the given description of a CSP and write solution as per the given questions: [20]
YCPS@GIFT is going to arrange a gaming competition at campus. They are considering using seven games
for this competition:
1) Supreme Commander (SC)
2) Grand Theft Auto (GTA)
3) Call of Duty: Modern Warfare (CoD)
4) Mortal Kombat (MK)
5) Tactical Ops (TO)
6) Rocket League (RL)
7) Dark Souls (DS)
YCPS President has assigned seven YCPS members to supervise the competition. They are:
a) Baber
b) Daud
c) Faisal
d) Jameela
e) Kiran
f) Marium
g) Naila
These members can also work together, but it turns out there are various constraints as given below that they
must follow:
1) Daud will not supervise the game in which Jameela is already assigned
2) Kiran must supervise either SC, GTA, or CoD
3) Marium can only supervise any one of games DS, CoD, or TO
4) Naila can supervise a game that comes before Marium’s game in the list
5) Kiran can supervise a game that comes before Daud’s game in the list
6) Baber can only supervise the game RL
7) Jameela can supervise a game that comes after Naila’s game in the list
8) Baber cannot supervise a game with Naila
9) Naila cannot supervise the game RL
10) Faisal cannot supervise any of the games MK, TO, or RL
11) Daud cannot supervise the game TO
12) Daud must supervise a game that comes before Faisal’s game in the list
This problem can be modeled as a CSP, with the name of each YCPS member as a variable, and the
domains are the game names.

a) [3]: What would be left in each variable’s domain if we apply the unary constraints on each varia-
ble?

You should write your answer as: variable name: domain value(s)
b) [3]: If the MRV (Minimum Remaining Values) heuristic is applied, what variable would be assigned
first?

c) [5]: Now we will use the LCV (Least Constraining Value) heuristic to assign values. We will select
Marium as the first variable to be assigned. We begin by using the Forward Checking with the LCV

heuristic to find the remaining values in each variable’s domain. What would be the order of as-
signed variables using the LCV heuristic? You will need to completely show your work in which

you clearly show the result of Forward Checking with LCV on each variable’s domain.
Suppose you are now given the following tree structured graph of this CSP as below:

KIRAN     DAUD     FAISAL     JAMEELA     NAILA     BABER      MARIUM

d) [5]: Now perform a Right-to-Left pass to prune the values from each variable’s domain. Write the
remaining values in each variable’s domain after this pass.
e) [4]: Now perform a Left-to-Right pass and assign values to each variable as a possible solution.
Write the complete solution as: variable: value, and so on.

c) [5]: Now we will use the LCV (Least Constraining Value) heuristic to assign values. We will select Marium as the first variable to be assigned. We begin by using the Forward Checking with the LCV heuristic to find the remaining values in each variable's domain. What would be the order of as- signed variables using the LCV heuristic? You will need to completely show your work in which you clearly show the result of Forward Checking with LCV on each variable's domain. Suppose you are now given the following tree structured graph of this CSP as below: KIRAN DAUD FAISAL JAMEELA NAILA BABER MARIUM d) [5]: Now perform a Right-to-Left pass to prune the values from each variable's domain. Write the remaining values in each variable's domain after this pass. e) [4]: Now perform a Left-to-Right pass and assign values to each variable as a possible solution. Write the complete solution as: variable: value, and so on.