07/03/2019 Gradescope | Submit HW 2 (Electronic Component)
HW 2 (Electronic Component)
Q1 Campus Layout
44 Points
You are asked to determine the layout of a new, small college. The
campus will have four structures: an administration structure (A), a
bus stop (B), a classroom (C), and a dormitory (D). Each structure
(including the bus stop) must be placed somewhere on the grid
shown below.
The layout must satisfy the following constraints:
i. The bus stop (B) must be adjacent to the road.
ii. The administration structure (A) and the classroom (C) must both be
adjacent to the bus stop (B).
iii. The classroom (C) must be adjacent to the dormitory (D).
iv. The administration structure (A) must not be adjacent to the dormitory
(D).
v. The administration structure (A) must not be on a hill.
vi. The dormitory (D) must be on a hill or adjacent to the road.
vii. All structures must be in different grid squares.
Here, adjacent means that the structures must share a grid edge,
not just a corner.
We recommend you work out the solutions to the following
questions on a sheet of scratch paper, and then enter your results
below.
Q1.1
4 Points
Which of the constraints above are unary constraints?
https://www.gradescope.com/courses/37468/assignments/146349/submissions/new 1/32
,07/03/2019 Gradescope | Submit HW 2 (Electronic Component)
i
ii
iii
iv
v
vi
vii
None of the above
EXPLANATION
Unary constraints are constraints that involve a single variable. i
only constrains (B), v only constrains (A), and vi only constrains
(D). All the other constraints involve more than one variable.
This question will be graded by your instructor.
Submit Last submitted on Mar 07 at 2:37 PM
Q1.2
4 Points
Select the domains of all variables after unary constraints have
been applied.
A
https://www.gradescope.com/courses/37468/assignments/146349/submissions/new 2/32
,07/03/2019 Gradescope | Submit HW 2 (Electronic Component)
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(2,3)
B
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(2,3)
C
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(2,3)
D
https://www.gradescope.com/courses/37468/assignments/146349/submissions/new 3/32
, 07/03/2019 Gradescope | Submit HW 2 (Electronic Component)
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(2,3)
EXPLANATION
i limits (B) to (1,3) or (2,3), because those are the only positions
adjacent to the road.
v removes (1,2) and (2,1) from the domain of (A) because those
two positions have hills
vi removes (1,1) and (2,2) from the domain of (D) because those
two positions are neither on a hill, nor adjacent to the road.
(C) has no unary constraints, and thus can still be any value
after unary constraints are applied.
This question will be graded by your instructor.
Submit Last submitted on Mar 07 at 2:42 PM
Q1.3
4 Points
Let's start from the table above (the answer to Part 2) and enforce
arc consistency. Initally, the queue contains all arcs (in alphabetical
order).
Let's examine what happens when enforcing A → B. After
enforcing unary constraints, the domains of A and B are:
https://www.gradescope.com/courses/37468/assignments/146349/submissions/new 4/32
HW 2 (Electronic Component)
Q1 Campus Layout
44 Points
You are asked to determine the layout of a new, small college. The
campus will have four structures: an administration structure (A), a
bus stop (B), a classroom (C), and a dormitory (D). Each structure
(including the bus stop) must be placed somewhere on the grid
shown below.
The layout must satisfy the following constraints:
i. The bus stop (B) must be adjacent to the road.
ii. The administration structure (A) and the classroom (C) must both be
adjacent to the bus stop (B).
iii. The classroom (C) must be adjacent to the dormitory (D).
iv. The administration structure (A) must not be adjacent to the dormitory
(D).
v. The administration structure (A) must not be on a hill.
vi. The dormitory (D) must be on a hill or adjacent to the road.
vii. All structures must be in different grid squares.
Here, adjacent means that the structures must share a grid edge,
not just a corner.
We recommend you work out the solutions to the following
questions on a sheet of scratch paper, and then enter your results
below.
Q1.1
4 Points
Which of the constraints above are unary constraints?
https://www.gradescope.com/courses/37468/assignments/146349/submissions/new 1/32
,07/03/2019 Gradescope | Submit HW 2 (Electronic Component)
i
ii
iii
iv
v
vi
vii
None of the above
EXPLANATION
Unary constraints are constraints that involve a single variable. i
only constrains (B), v only constrains (A), and vi only constrains
(D). All the other constraints involve more than one variable.
This question will be graded by your instructor.
Submit Last submitted on Mar 07 at 2:37 PM
Q1.2
4 Points
Select the domains of all variables after unary constraints have
been applied.
A
https://www.gradescope.com/courses/37468/assignments/146349/submissions/new 2/32
,07/03/2019 Gradescope | Submit HW 2 (Electronic Component)
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(2,3)
B
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(2,3)
C
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(2,3)
D
https://www.gradescope.com/courses/37468/assignments/146349/submissions/new 3/32
, 07/03/2019 Gradescope | Submit HW 2 (Electronic Component)
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(2,3)
EXPLANATION
i limits (B) to (1,3) or (2,3), because those are the only positions
adjacent to the road.
v removes (1,2) and (2,1) from the domain of (A) because those
two positions have hills
vi removes (1,1) and (2,2) from the domain of (D) because those
two positions are neither on a hill, nor adjacent to the road.
(C) has no unary constraints, and thus can still be any value
after unary constraints are applied.
This question will be graded by your instructor.
Submit Last submitted on Mar 07 at 2:42 PM
Q1.3
4 Points
Let's start from the table above (the answer to Part 2) and enforce
arc consistency. Initally, the queue contains all arcs (in alphabetical
order).
Let's examine what happens when enforcing A → B. After
enforcing unary constraints, the domains of A and B are:
https://www.gradescope.com/courses/37468/assignments/146349/submissions/new 4/32
