artificial intelligence- Constraint Satisfaction
Part (c) and (d) in this question
cs 540-1 Spring 2017
Problem 3: Constraint Satisfaction [17]
Imagine that you manage a puppy kindergarten, which allows puppies of all
breeds to attend. However, small dogs are not allowed to sit next to large dogs,
for fear that Big Buddy will crush Snowball. However, medium dogs are allowed
to sit next to large and small dogs.
Variables:
Formally, there are 7 dogs enrolled: (Akita – large, Basset Hound – medium,
Chihuahua – small , Dachshund – small, Elkhound – medium, French Bulldog
small , Golden Retriever – large).
Domain:
Each of these 7 dogs can take one of 7 available places represented as i, j
coordinates. Two places in the grid aren‘t available for the dogs because of
other objects in the room. The seats are arranged as follows:
Water L
Bowls
1,0 Chew
Toys
Hence, d = {(0,0), (1,0), (1,1), (2,1), (2,2), (1,2), (0,2)
Constraints:
No two dogs can sit in the same place. No small dogs can sit next to large dogs.
a) [3] Draw a constraint graph with the variables [A,B,C,D,E,F,G] as nodes
and canSitNextTo relationships as edges. That is, represent the dogs who
can sit next to each other as connected in the graph. If two dogs cannot
sit next to each other, do not connect them with an edge.
b) [4] Formalize the dogs that cannot sit next to each as binary numeric
constraints relative to the each dog’s current coordinate position. (See
the n-queens example in the lecture slides.)
c) [8] Assume that an owner has requested that G sit at (1,1) and another
c) [8] Assume that an owner has requested that G sit at (1 ,l) and another
cs 540-1 Spring 2017
has requested B sit at (2, 1). No other dogs have been assigned places.
Perform a (pseudo) iteration of DFS search with forward checking from
the current state.
Draw array that shows the remaining legal values (possible coordinates)
for each variable (dog) with this configuration. (Check the lecture slides on
forward checking)
Identify the most-constrained variable(s), the most-constraining variable,
and the least-constraining value for the most constraining variable, and
whether the algorithm would backtrack from this state.
d) [2] Can an optimal solution be reached from this state? Why or why not?
If yes, give an optimal solution, if not, propose an alternative assignment
of dogs to places.
