Makerere University

College of Computing and Information Sciences

School of Computing and Informatics Technology
CS2114: Artificial Intelligence CSP questions

1. Consider the following CSP with 3 variables X, Y and Z with the following do-
mains X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Y = {5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15} and
Z = {5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}. The constraints on 3 the
variables are: X > Y , Y + Z = 12 and X + Z = 16.

(a) Draw the constraint graph

(b) Are the constraints arc consistent? If no, apply arc consistency method re-
peatedly so they become arc consistent. What is the updated domain of each
variable?

2. You are in charge of allocating rooms to tests scheduled for 9th October 2017. You
have just received the test schedule from the exam coordinator which provides infor-
mation about the papers,time and number of students expected to sit a particular
paper. This scheduled is listed in table 1 . A list of rooms available that day with
their corresponding capacity is also provided to you by the custodian as shown in ta-
ble 2. Your allocations must meet the following constraints for proper management
of tests.

• Students sitting the same paper must sit in a single room.

• Each paper must be allocated its own room.

Table 1: Test Schedule

Paper Time Number of
Students Table 2: Room Availability
CS2114 8:00-9:30 350 Room Time Sitting
Available Capacity
CS2100 10:00-11:00 300
R1 7:00-12:00 400
BS2102 10:00-11:00 100
R2 8:30:00-2:00 400
CS1101 8:30-9:30 120
R3 7:00-1:30 250
BIT1100 9:00-10:00 200
R4 7:00-11:30 200
BIS1101 11:30-12:30 300
R5 7:00-2:00 200
BIT1102 12:00-1:00 100
BSE1209 11:30-12:30 100

1
 (a) Using papers as variable and rooms as domains, list the valid domains for each
of the papers.
(b) By using the minimum remaining value (MRV) heuristics, which variable(s)
should be assigned first.
(c) List one solution to this CSP or state that none exist.

3. Consider 3 variables with corresponding domains A={1,2,3,4}, B={1,2,3,4} and C

={1,2,3,4}. If these variables are defined in a CSP with the following constraints
A < B and B < C.

(a) Apply the arc consistency algorithm to the problem and report the resulting
domains.
(b) Solve the problem with simplified domains using backtracking and forward
checking. Report the search tree, the domains after each application of forward
checking, and the solution found. Choose variables and values at random. Only
one solution is required.
(c) Explain why depth-first search strategy is preferred over breadth-first search
strategy in solving CSPs.

4. Jennifer is looking for a group of friends for her start-up, which develops and provides
mobile- based IT solutions to University students. Jennifer has determined that she
needs 2 Android Programmers, 2 Flash Designers, 1 Photoshop Guru, 1 Database
Admin, 1 Systems Engineer and 2 Java Programmers.
Assuming that if a person knows two languages/softwares, he or she can take on
two roles in the company. Jennifer narrowed down her selections to the following
people as shown in Table 3

Table 3: List of People

Name Abilities
Peter Android and Flash
John Java and Flash
Jim Flash and Systems
Jane Android and Database
Mary Photoshop and Flash
Bruce Systems and Android
Chuck Photoshop and Flash

(a) Suppose Jennifer knows Android and Java, and only has funds to hire four
more people. Model this scenario as a CSP using abilities as variables. Note
a person cannot take two roles which require same ability e.g Peter cannot fill
the two positions for Android programmer .

2 of 6
 (b) Suppose Jennifer decides to make Jane a co-founder. Jennifer and Jane discover
that all the developers absolutely refuse to abandon their favorite platforms as
shown in Table 4, and that they can only afford two single-booted workstations.

Table 4: Familiar Platform

Name Abilities OS
Jennifer Android and Java Windows
Peter Android and Flash Windows
John Java and Flash Windows
Jim Flash and Systems FreeBSD
Jane Android and Database FreeBSD
Mary Photoshop and Flash Linux
Bruce Systems and Android Linux
Chuck Photoshop and Flash Windows

What are the domains for the remaining positions after constraint propagation?
(c) Assuming Jennifer and Jane hired Jim,Chuck and John and they have awarded
a contract for their first project, a rush job due Friday at 5 PM. It’s Monday
at 9 AM and they have to put in 50 total hours of work on it by the due date.
There are a number of constraints associated with their work schedules:
• They only have access to two machines of the requisite platform, and only
have access to those two machines between 9 AM and 5 PM every day.
• Each person can work a maximum of 20 hours over the course of the week.
• Work session by a single person on a particular machine can last no fewer
than two hours.
• Jennifer cannot work from 12-4 PM Tuesday and Thursday.
• Jane cannot work Monday, Wednesday and Friday 9-12.
• Jim can only work between noon and 2 PM every day.
• John can only work Thursday and Friday
• Chuck can only work on Monday and Tuesdays.
Model this scheduling problem as a CSP. Indicate how the indicated constraints
impact the domains for all variables.

5. Soroti University’s new circular campus is nearing completion. Unfortunately,the

chief architect on the project was using Google Maps to store the location of each
individual department, and after upgrading to android 6, all the plans for the new
campus were lost. Figure 1 shows an approximate map of the campus The campus
has six offices, labeled 1 through 6, and six departments:

• Legal

3 of 6
 Figure 1: The circular campus structure

• Maps Team
• Prototyping
• Engineering
• Human Resource
• Examination Storage

Offices can be next to one another, if they share a wall (for an instance, Offices 1
ad 6). office can also be across from one another (specifically, Offices 1-4, 2-5, 3-6).
The Electrical Grid is connected to Offices 1 and 6. The Lake is visible from Offices
3 and 4. There are two "halves" of the campus thats South (Offices 1-3) and North
(Offices 4-6). The constraints are as follows

(i) Legal wants a view of the lake to look for prior art examples.
(ii) Human Resource Office must not be across from Maps.
(iii) Prototyping must have an electrical connection.
(iv) Examination Storage must be next to Engineering.
(v) Engineering must be across from Human Resource office.
(vi) Prototyping and Legal cannot be next to one another.
(vii) Prototyping and Engineering must be on opposite sides of the campus (if one
is on the North side, the other must be on the South side).
(viii) No two departments may occupy the same office.

(a) Formulate the SOroti University’s new circular campus as a CSP

i What are the urinary constraints?

4 of 6
 ii What are the binary constraints?
iii In the constraint graph for this CSP, how many edges are there?
(b) If we assign office 1 to Prototyping. What is domain(s) of the remaining
variables when Forward Checking is performed on the remaining variables.
(c) If we assign office 1 to Prototyping and office 3 to Human Resource. What
is the updated domain(s) for the remaining variables when arc consistency is
enforced after these assignments.

6. You are asked to determine the layout of a new, small recreation center. The
recreation center will have the following structures: administration block (A), a bus
stop (B), playground (P), a refreshment block (R) and a hotel (H). Each structure
must be placed somewhere on the grid shown in Figure 2. The following constraints
must be satisfied:

(i) The bus stop (B) must be adjacent to the road.

(ii) The administration block (A) and refreshment block (R)must both be adjacent
to the bus stop (B).
(iii) The hotel(H) must be on the hill or adjacent to the road.
(iv) The refreshment block (R) must be adjacent to the hotel (H).
(v) The playground (P) must be adjacent to the hotel (H).
(vi) The administration block (A) must not be adjacent to the playground (P).
(vii) The administration block (A) must not be on a hill.
(viii) The play ground (P) must not be on a hill or adjacent to the road.
(ix) All structures must be in different grid squares.

Here, “adjacent” means that the structures must share a grid edge, not just a corner.

Figure 2: Grid

5 of 6
(a) Let the variables A, B, H,P and R each range over the set of locations on the
grid. Express the description above as unary and binary constraints over these
variables.
(b) Cross out eliminated values to show the domains of all variables after unary
constraints and arc consistency have been applied but no variables have been
assigned.
(c) Cross out eliminated values to show the domains of the variables after B = (1,
3) has been assigned and arc consistency has been rerun.
(d) List one solution to this CSP or state that none exist.

End

6 of 6