1/9414/9814 18s1
other symbols.
Constraint Satisfaction Problems 7
COMP3411 Tutorial- Week 4
Constraint Satisfaction
Question 1 – Cryptarithmetric
Cryptarithmetric is a type of mathematical puzzle where the numbers have been replaced with letters, or
Solve the famous Cryptarithmetric problem and Provide not just the final answer, but also explain your reasoning along the way.
mple: Cryptarithmetic
ables:
M N O R S Y
SEND +MORE MONEY
Constraints:
M ̸= 0, S ̸= 0 (unary constraints)
Y =D+E orY =D+E−10,etc.
ains:
,2,3,4,5,6,a7),8,C9a}n you idenDtif̸=y Ean,yDb̸=acMktr,aDck̸=ingNh,eutcri.stics or enhancements that you may have (unknowingly) used
when you solved the problem?
b) Are there any backtracking heuristics or enhancements that you would now use to solve the problem more efficiently?
⃝c Alan Blair, 2013-8 What heuristics and strategies did you use along the way?
The sum of two 4-digit numbers cannot exceed 1998, so M=1.
10+O = S+1 or S+1+1, i.e. S = O+9 or O+8, but 1 has already been used, so O=0.
Therefore S=9, because there is no possibility of a carry from E+O.
We then have E+1 = N and 10+E = N+R or N+R+1, so R = 8 or 9, but 9 has already been assigned, so R=8. (Note how Minimum Remaining Values has been used at each step.)
The puzzle now looks like this:
9END + 108E
10NEY
This gives us the two constraints: E+1 = N D+E = 10+Y
The remaining values are 2,3,4,5,6,7.
We have D+E <= 6+7 = 13, so Y = 2 or 3. (Note: MRV again).
But if Y=3 (Most Constraining Value) then all three variables D,E,N would need to take values 6 or 7, which is impossible (Constraint Propagation).
Therefore Y=2, E=5, N=6 and D=7.
a
m 1
UNUSWNSW
⃝c ⃝AclaAnlBanlaBir,la2i0r,1230-183-8
Use Forward Checking to show that the Australia map-colouring problem has no solution when we assign
WA=green, V=Red, NT=Red. If we apply Arc Consistency as well, can the inevitable failure be detected further up the tree?
Present your answer to this question and discuss with others in the tutorial group. Solution:
Question 2 - Map Colouring
COMP3411/9414/9814 18s1 Constraint Satisfaction Problems 3 COMP3411/9414/9814 18s1 Constraint Satisfaction Problems 3
EExxaammpplele: :MMaapp-C-Coololorirningg
WeWstesrtnern AuAstursatlrialia
NoNrtohretrhnern TerTreitrorirtyory
SoSuothuth AuAstursatlrialia
QuQeueneesnlasnladnd
NeNweSwoSuothutWhaWleasles VicVtiocrtioaria
VaVraiaribalbelseWs WAA, N, NT,TQ, Q, N, NSWSW, V, ,VS, ASA, T, T
DDomomaianisnDs Di =i ={r{erde,dg,rgereene,nb,lbuleu}e} CoCnosntrsatrianitns:tsa:dajdajcaecnetnrtergeigoinosnms musutshtahvaevedidffieffrernetnctoclolrosrs e.ge.gW. WAA̸≠=NNT,Te,tect.c.
(Refer to lectures for week 3)
TaTsmasamnaiania
WA
NT
Q
NSW
V
SA
T
initial domains
RG B
RG B
RG B
RG B
RG B
RG B
RG B
WA=Green
G
RB
RG B
RG B
RG B
RB
RG B
V = Red
G
RB
RG B
GB
R
B
RG B
NT = Red
G
R
GB
GB
R
B
RG B
SA = Blue
G
R
G
G
R
B
RG B
Q = Green
G
R
G
R
B
RG B
No options remain for NSW, so there is no solution.
If we also apply Arc Consistency, the question can be resolved further up the tree (but with extra computation at each node) as follows:
WA
NT
Q
NSW
V
SA
T
initial domains
RG B
RG B
RG B
RG B
RG B
RG B
RG B
WA=Green
G
RB
RG B
RG B
RG B
RB
RG B
V = Red
G
RB
RG B
GB
R
B
RG B
NT→SA, Q→SA, NSW→SA
G
R
RG
G
R
B
RG B
Q → NT
G
R
G
G
R
B
RG B
Q → NSW
G
R
G
R
B
RG B
Question 3 - 8-queens problem
Consider the following state for the 8-queens problem:
a) Is this a solution?
NO
b) What is the value of h?
There is only one violation, so h=1.
c) Explain why Hill-climbing with Min Conflicts would get stuck in this state, but simulated annealing may be able to "escape" and eventually find a solution.
For each column, moving the queen on that column (while keeping the other queens in place) would result in an increase to h. Therefore, any such move will be rejected by Hill-climbing. Simulated Annealing, however, can accept such a move with probability e−(h1−h0)/T, thus bumping the
system out of this local optimum and allowing it to continue the search for a global optimum. (Note: when started from a random initial state, Hill-climbing will get stuck 86% of the time on this problem, and will need to be continually re-started from a new random state each time, until it succeeds.)
Question 4 - Logic Puzzle
(Exercise 6.6 from Russell & Norvig.)
Consider the following logic puzzle: In five houses, each with a different colour, live five persons of different nationalities, each of whom prefers a different brand of candy, a different drink, and a different pet. Given the following facts, the questions to answer are "Where does the zebra live, and in which house do they drink water?".
1. The Englishman lives in the red house.
2. The Spaniard owns a dog.
3. The Norwegian lives in the first house on the left.
4. The Green house is immediately to the right of the ivory house.
5. The man who eats Hershey bars lives in the house next to the man with the fox.
6. Kit Kats are eaten in the yellow house.
7. The Norwegian lives next to the blue house.
8. The Smarties eater owns snails.
9. The Snickers eater drinks orange juice.
10. The Ukrainian drinks tea.
11. The Japanese eats Milky Ways.
12. Kit Kats are eaten in a house next to the house where the horse is kept. 13. Coffee is drunk in the green house.
14. Milk is drunk in the middle house.
Discuss different representations of this problem as a CSP. Why might we prefer one representation over another?
There is a straightforward Prolog solution to this:
houses(Houses) :-
length(Houses, 5),
member(house(red, english, _, _, _), Houses),
member(house(_, spanish, dog, _, _), Houses),
Houses = [house(_, norwegian, _, _, _), _, _, _,_],
right_of(house(green,_,_,_,_), house(ivory,_,_,_,_), Houses),
next_to(house(_,_,_,_,hershey), house(_,_,fox,_,_), Houses),
member(house(yellow, _, _, _, kit_kats), Houses),
next_to(house(_, norwegian, _, _, _), house(blue,_,_,_,_), Houses),
member(house(_, _, snails, _, smarties), Houses),
member(house(_, _, _, orange_juice, snickers), Houses),
member(house(_, ukranian, _, tea, _), Houses),
member(house(_, japanese, _, _, milky_ways), Houses),
next_to(house(_,_,_,_,kit_kats), house(_,_,horse,_,_), Houses),
member(house(green, _, _, coffee, _), Houses),
member(house(_, _, zebra, _, _), Houses),
Houses = [_, _, house(_, _, _, milk, _), _, _],
member(house(_, _, _, water, _), Houses),
print_houses(Houses).
next_to(A, B, Ls) :- append(_, [A,B|_], Ls).
next_to(A, B, Ls) :- append(_, [B,A|_], Ls).
right_of(A, B, Ls) :- append(_, [B,A|_], Ls).