Constraints
Many challenging reasoning tasks have the following form:
• some choices to be made • constraints to be satisfied
We will examine a collection of such reasoning tasks
Copyright By PowCoder代写加微信 assignmentchef
• map colouring • cryptarithmetic • scheduling
• 8 queens
• visual interpretation • logic puzzles
all of which can be solved in Prolog in a similar way
cps721 Artificial Intelligence © Constraint Satisfaction 1
Map colouring
A simple map:
Five countries: A,B,C,D,E
Three colours: red, white, blue
Neighbouring countries must have different colours on the map
solve([A,B,C,D,E]) :-
colour(A), colour(B), colour(C),
colour(D), colour(E),
not A=B, not A=C, not A=D, not A=E,
not B=C, not C=D, not D=E.
colour(red).
colour(white).
colour(blue).
L = [red,white,blue,white,blue]
+ 5 others
cps721 Artificial Intelligence ©
Constraint Satisfaction 2
Constraint Satisfaction
General form:
• some number of variables
– e.g. colours on the map
• values to be chosen from finite domains
– e.g. each colour must be red, white, or blue • constraints among subsets of variables
– e.g. adjacent countries have different colours The simplest program is “generate and test”
solve(ListOfVariables) :- domain1(Variable1),
domainn(Variablen), constraint1(Variable, …, Variable),
constraintm(Variable, …, Variable). and optionally
generate values for the variables
test the values with constraints
print_solution :- solve(ListOfVariables),
write(‘The answer is ‘), …, nl.
cps721 Artificial Intelligence © Constraint Satisfaction 3
Output in Prolog
It is often useful to get Prolog to print a message in addition to the values for variables.
Two special goals:
This goal always succeeds and has the effect of generating a new line of output
• write(term or string)
This goal always succeeds and has the effect of printing the term or the string (enclosed in single quotes) on the current line
For example, for the query
X=blue, write(‘The value of X is ‘),
write(X), nl, write(‘
write(‘ is it!’).
we get the output
The value of X is blue
and that is it!
X = blue ; no
and that’),
This comes in especially handy to annotate the answers to a constraint satisfaction problem.
cps721 Artificial Intelligence © Constraint Satisfaction 4
Cryptarithmetic
Puzzles of the form
SEND Each letter stands for a
MONEY not be zeroes
distinct digit. Leading digits must
Variables: S,E,N, etc. and “carry digits”
Domains: 0,1,2,3,4,5,6,7,8,9 for digits and 0,1 for carry digits
Constraints: as above and
(D + E) mod 10 = Y (D + E) / 10 = C1
(N + R + C1) mod 10 = E (N + R + C1) / 10 = C10
(E + O + C10) mod 10 = N (E + O + C10) / 10 = C100
(S + M + C100) mod 10 = O (S + M + C100) / 10 = M
Artificial Intelligence ©
Constraint Satisfaction 5
Arithmetic in provides facilities for evaluating and comparing arithmetic expressions, made up of variables, integers, parentheses, and the arithmetic operators +, -, //, *, ^, and mod. For example
12*(X^2-3) + (-3*Y//5) mod 4
Note that any variables appearing in such expressions must already have values that are integers
Using expressions like these, Prolog has the following arithmetic goals
expr1 > expr2, expr1 < expr2, expr1 >= expr2, expr1=
Y is (D+E) mod 10, C1 is (D+E) // 10,
E is (N+R+C1) mod 10, C10 is (N+R+C1) // 10,
N is (E+O+C10) mod 10, C100 is (E+O+C10) // 10, test O is (S+M+C100) mod 10, M is (S+M+C100) // 10,
all_diff([S,E,N,D,M,O,R,Y]).
dig(0).dig(1). dig(2). dig(3).dig(4).
dig(5).dig(6). dig(7). dig(8).dig(9).
all_diff([]).
all_diff([N|L]) :- not member(N,L), all_diff(L).
member(N,[N|L]).
member(N,[M|L]) :- member(N,L).
The result:
L = [9,5,6,7,1,0,8,2].
after 167 minutes of computer time!
cps721 Artificial Intelligence © Constraint Satisfaction 7
Finding a better search order
Avoid guessing a value that is fully determined by other values, and later testing if the value is correct
for example, instead of
digit(A), digit(B),
C is (A+B) mod 10,
we should use
digit(A), digit(B),
C is (A+B) mod 10,
guess at C value repeatedly
calculate once
Avoid placing independent guesses between the generation and the testing of a value
for example, instead of
digit(A), digit(B),
digit(C), digit(D),
we should use
digit(A), digit(B),
digit(C), digit(D),
all values for C and D will be attempted each time test fails
no values for C and D will be considered until test succeeds
Artificial Intelligence ©
Constraint Satisfaction 8
A second program
solve([S,E,N,D,M,O,R,Y]) :-
dig(D), dig(E),
Y is (D+E) mod 10, C1 is (D+E) // 10,
dig(N), dig(R),
E is (N+R+C1) mod 10, C10 is (N+R+C1) // 10,
dig(E), dig(O),
N is (E+O+C10) mod 10, C100 is (E+O+C10) // 10,
dig(S), S > 0, dig(M),
O is (S+M+C100) mod 10, M is (S+M+C100) // 10,
all_diff([S,E,N,D,M,O,R,Y]).
dig(0).dig(1). dig(2). dig(3).dig(4).
dig(5).dig(6). dig(7). dig(8).dig(9).
all_diff([]).
all_diff([N|L]) :- not member(N,L), all_diff(L).
member(N,[N|L]).
member(N,[M|L]) :- member(N,L).
• Uses exactly the same constraints
• Gives exactly the same answer
• But this time: completes in 9 seconds!
Can we do even better?
cps721 Artificial Intelligence © Constraint Satisfaction 9
Dependency graph
Note: both var is expr and not goal in Prolog require values for the variables in expr or goal
Draw a graph whose nodes are the variables, with an edge from var1 to var2 if the value of var1 will be calculated from that of var2
SEND D R + MORE Y
ignoring carries
Previous method guessed at D and E first, then calculated Y, guessed at N and R, then verified E, guessed at O, verified N, etc.
Can use the dependency graph to reduce guessing: • guess at M and S, calculate O
• guess at E, calculate N
• guess at R, verify choice for E
• guess at D, calculate Y
With this order, we will also need to guess carry digits
cps721 Artificial Intelligence © Constraint Satisfaction 10
A better program
print_solution :-
solve([S,E,N,D,M,O,R,Y]),
write(‘‘),write(S),write(E),write(N),write(D),nl,
write(‘+ ‘),write(M),write(O),write(R),write(E),nl,
write(‘ ‘),write(‘_____’),nl,
write(‘ ‘),write(M),write(O),write(N),write(E),
write(Y),nl.
solve([S,E,N,D,M,O,R,Y]) :-
car(M), M > 0, car(C100),
dig(S), S > 0,
M is (S+M+C100) // 10, O is (S+M+C100) mod 10,
dig(E), car(C10),
N is (E+O+C10) mod 10, C100 is (E+O+C10) // 10,
dig(R), car(C1),
E is (N+R+C1) mod 10, C10 is (N+R+C1) // 10,
Y is (D+E) mod 10, C1 is (D+E) // 10,
all_diff([S,E,N,D,M,O,R,Y]).
car(0). car(1).
dig(0).dig(1). dig(2). dig(3).dig(4).
dig(5).dig(6). dig(7). dig(8).dig(9).
all_diff([]).
all_diff([N|L]) :- not member(N,L), all_diff(L).
member(N,[N|L]).
member(N,[M|L]) :- member(N,L).
print_solution.
+ 1085 _____
This time the program completes in .1 seconds!
cps721 Artificial Intelligence © Constraint Satisfaction 11
Scheduling
In general: finding times and/or places for events
We want to schedule a new class to meet 5 hours a week. Meetings times are on the hour from 9am to 4pm, on weekdays. Some of the times will be taken by already-scheduled courses. Classes must not meet on successive hours on the same day, and for more than 2 hours total on any one day.
Variables: T1, T2, T3, T4, T5, where each Ti is one of the 5 meeting times for the course
Domain: pair [Day, Hour] where
Day is one of mon, tues, wed, thurs, fri Hour is one of 9, 10,11, 12, 1, 2, 3, 4
Constraints: the five chosen times must be • not already taken
• non-consecutive
• no more than 2 per day
• all different
not explicitly mentioned! cps721 Artificial Intelligence © Constraint Satisfaction 12
solve(Time_list) :-
Time_list = [T1,T2,T3,T4,T5],
class_time(T1), class_time(T2), class_time(T3),
class_time(T4), class_time(T5),
not taken(T1), not taken(T2), not taken(T3),
not taken(T4), not taken(T5),
not two_consecutive_hours(Time_list),
not three_classes_same_day(Time_list),
all_diff(Time_list).
/* A class time is a pair [Day,Hour]. */
class_time([Day,Hour]) :-
member(Day,[mon,tues,wed,thurs,fri]),
member(Hour,[9,10,11,12,1,2,3,4]).
two_consecutive_hours(TL) :-
member([Day,Hour1],TL),
member([Day,Hour2],TL),
append(_,[Hour1,Hour2|_],[9,10,11,12,1,2,3,4]).
three_classes_same_day(TL) :-
member([Day,Hour1],TL),
member([Day,Hour2],TL),
member([Day,Hour3],TL),
not Hour1=Hour2, not Hour1=Hour3, not Hour2=Hour3.
all_diff([]).
all_diff([N|L]) :- not member(N,L), all_diff(L).
append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
member(X,L) :- append(_,[X|_],L).
/* And optionally… */
taken([thurs,3]).…
cps721 Artificial Intelligence © Constraint Satisfaction 13
Running the scheduler
Suppose the following times are taken
9 10 11 12 1 2 3 4
mon tues wed
taken([mon,9]). taken([tues,9]). taken([thurs,10]). taken([mon,10]). taken([tues,10]). taken([thurs,2]).
taken([mon,2]).
taken([mon,3]).
taken([mon,4]).
taken([_,12]).
taken([wed,_]).
taken([fri,_]).
taken([tues,11]).
taken([tues,3]).
taken([tues,4]).
solve(TL).
TL = [[mon,11],[mon,1],[tues,1],
[thurs,9],[thurs,11]]
But: without ordering, it takes a long time to get an answer … cps721 Artificial Intelligence © Constraint Satisfaction 14
The 8 Queens problem
The problem:
Place 8 queens on an 8×8 chess board such that no queen can capture any other
Can reasonably assume that each row will have exactly one queen
So the job is to choose a column for each queen Variables: C1, C2, C3, C4, C5, C6, C7, C8
where Ci is the column for queen in row i Domains: the columns 1,2,3,4,5,6,7,8 Constraints: no queen can capture any other
each queen must be on its own
left diagonal right diagonal
Artificial Intelligence
Constraint Satisfaction 15
Capturing queens
• along a left diagonal, (row – column) stays constant
• along a right diagonal, (row + column) stays constant
row – column = 2
row + column = 12
each left diagonal and each right diagonal will have a different constant
So a queen on [row1, col1] can capture another queen on [row2, col2] if any of the following hold:
• row1 = row2
• col1 = col2
• row1 – col1 = row2 – col2 • row1 + col1 = row2 + col2
same left diagonal same right diagonal
cps721 Artificial Intelligence ©
Constraint Satisfaction 16
Queens in Prolog
solve([C1,C2,C3,C4,C5,C6,C7,C8]) :-
safe([2,C2], [[1,C1]]),
safe([3,C3], [[1,C1],[2,C2]]),
Note the interleaving of generation and testing
safe([4,C4], [[1,C1],[2,C2],[3,C3]]),
safe([5,C5], [[1,C1],[2,C2],[3,C3],[4,C4]]),
safe([6,C6], [[1,C1],[2,C2],[3,C3],[4,C4],[5,C5]]),
safe([7,C7], [[1,C1],[2,C2],[3,C3],[4,C4],[5,C5],
safe([8,C8], [[1,C1],[2,C2],[3,C3],[4,C4],[5,C5],
col(1).col(2).col(3).col(4).
col(5).col(6).col(7).col(8).
safe(_, []).
safe(Queen1, [Queen2|Rest]) :-
not capture(Queen1,Queen2),
safe(Queen1,Rest).
capture([Row1,Col], [Row2,Col]).
capture([Row1,Col1], [Row2,Col2]) :-
(Row1-Col1) =:= (Row2-Col2).
capture([Row1,Col1], [Row2,Col2]) :-
(Row1+Col1) =:= (Row2+Col2).
[1,5,8,6,3,7,2,4]
A queen is safe from a list of other queens
The 3 ways a queen on one row can capture a queen on another row
[6,C6],[7,C7]]).
cps721 Artificial Intelligence © Constraint Satisfaction 17
Aerial photo interpretation
Would like to label the regions in the picture as either
grass, water, pavement, house, vehicle
subject to constraints such as
• a region cannot border or be inside another region with the same label
• houses cannot be next to or surrounded by water
• vehicles must be next to or surrounded by pavement
• pavement cannot be inside any other region
• houses, vehicles and pavement are regular (straight- edged) regions; grass and water are irregular
• vehicles are small; the other regions are large
cps721 Artificial Intelligence © Constraint Satisfaction 18
Visual constraints
The task here is to determine how properties of the picture can be translated into suitable constraints
the more we extract from the photo, the more we are able to rule out incorrect interpretations
In our example picture:
1. region R5 is small; the others are large
2. regions R3 and R5 are regular; R2 and R1 are irregular; region R4 could go either way
3. region R1 borders on R2; R2 borders on R4
4. region R3 is inside R2; R5 is inside R4
It is clear how to represent (1) and (2) as constraints on possible labellings.
To handle (3), we simply ensure that the two regions do not violate any of the given rules about borders.
• the two regions must be different
• they must be not be house and water
• if one is vehicle, the other must be pavement
Constraint (4) is handled analogously.
cps721 Artificial Intelligence © Constraint Satisfaction 19
solve([R1,R2,R3,R4,R5]) :-
label(R1), label(R2), label(R3), label(R4), label(R5),
large(R1), large(R2), large(R3), large(R4), small(R5),
regular(R3), regular(R5), irregular(R2), irregular(R1),
borders(R1,R2), borders(R2,R4),
inside(R3,R2), inside(R5,R4).
label(grass). label(water). label(vehicle).
label(pavement).label(house).
large(grass). large(water). small(vehicle).
large(pavement).large(house).
irregular(grass). irregular(water).
regular(pavement).regular(house).
regular(vehicle).
borders(X,Y) :- not illegal_border(X,Y).
illegal_border(X,X).
illegal_border(house,water).
illegal_border(water,house).
illegal_border(vehicle,X) :- not X=pavement.
illegal_border(X,vehicle) :- not X=pavement.
inside(X,Y) :- not illegal_inside(X,Y).
illegal_inside(X,X).
illegal_inside(house,water).
illegal_inside(vehicle,X) :- not X=pavement.
illegal_inside(pavement,X).
solve([R1,R2,R3,R4,R5]).
R1 = water R2 = grass R3 = house R4 = pavement R5 = vehicle ;
interpretation is unique even without info on R4 regularity
Artificial Intelligence ©
Constraint Satisfaction 20
Blocks world vision
Other visual interpretation tasks also end up needing to solve constraints.
Imagine looking at a blocks world scene and trying to figure out what the objects are, assuming you have already found the edges and the vertices
Part of understanding this type of scene is labelling the vertices: deciding how to interpret each vertex.
For instance, for a Y vertex
– which of the 3 quadrants are occupied by some object and which are background?
– which occupied quadrants are closest to the viewer?
The label that is selected for one vertex imposes constraints on the labels of adjacent vertices
cps721 Artificial Intelligence © Constraint Satisfaction 21
Logic puzzles
In conversation, Chris, Sandy and Pat discovered that they had distinct occupations and played distinct musical instruments. Also,
1. Chris is married to the doctor.
2. The lawyer plays the piano.
3. Chris is not the engineer.
4. Sandy is a patient of the violinist.
Who plays the flute?
To solve puzzles like these, we again need to determine how the given information leads to constraints on possible solutions.
Here, all we need to know is that
• if X is married to Y, then X ! Y.
• if X is a patient of Y, then X ! Y and Y is the doctor
cps721 Artificial Intelligence © Constraint Satisfaction 22
solve(Flute) :-
distinct_people(Doctor,Lawyer,Engineer),
distinct_people(Piano,Violin,Flute),
/* Chris is married to the doctor */
not chris = Doctor,
/* The lawyer plays the piano */
Lawyer = Piano,
/* The engineer is not Chris */
not Engineer = chris,
/* Sandy is a patient of the violinist */
Violin = Doctor,
not sandy = Violin.
/* Generating the people + testing for all_diff */
distinct_people(X,Y,Z) :-
person(X), person(Y), person(Z),
not X=Y, not X=Z, not Y=Z.
person(chris).
person(sandy).
person(pat).
solve(Flute).
Flute = sandy
cps721 Artificial Intelligence © Constraint Satisfaction 23
Hidden variables
Sometimes, the only way to express the contraints is to imagine that there are variables other than the ones mentioned in the puzzle
cf. the carry digits in cryptarithmetic
Example: as before, with one difference
1. Chris is married to the doctor.
2. The lawyer plays the piano.
3. Pat is not married to the engineer. 4. Sandy is a patient of the violinist.
So, for instance, it follows that if Pat is the doctor, then Chris is not the engineer (from (1) and (3)).
Useful to think in terms of new variables for Chris’ spouse, Sandy’s spouse and Pat’s spouse
• Domain: Chris, Sandy, Pat, and “none” • Constraints: only 4 legal arrangements
– nobody is married
– Chris and Pat
– Chris and Sandy – Sandy and Pat
cps721 Artificial Intelligence ©
Constraint Satisfaction 24
solve([Doctor,Lawyer,Engineer,Piano,Violin,Flute]) :-
distinct_people(Doctor,Lawyer,Engineer),
distinct_people(Piano,Violin,Flute),
spouses(Chris_spouse,Sandy_spouse,Pat_spouse),
Chris_spouse = Doctor,
Lawyer = Piano,
not Pat_spouse = Engineer,
Violin = Doctor,
not sandy = Violin.
distinct_people(X,Y,Z) :-
person(X), person(Y), person(Z),
not X=Y, not X=Z, not Y=Z.
spouses(none,none,none).
spouses(sandy,chris,none).
spouses(pat,none,chris).
spouses(none,pat,sandy).
person(chris).
person(sandy).
person(pat).
The 4 clues
print_solution :-
solve([Doctor,Lawyer,Engineer,Piano,Violin,Flute]),
write(‘The doctor is ‘), write(Doctor), nl,
write(‘The lawyer is ‘), write(Lawyer), nl,
write(‘The engineer is ‘), write(Engineer), nl,
write(‘==================================’), nl,
write(‘The piano is played by ‘), write(Piano), nl,
write(‘The violin is played by ‘), write(Violin), nl,
write(‘The flute is played by ‘), write(Flute), nl.
nobody married Chris and and and Pat
cps721 Artificial Intelligence © Constraint Satisfaction 25
Sometimes, it takes some work to discover what the values of the variables should be
An old classic:
On a street, there are 5 houses of different colours occupied by 5 individuals of different nationalities, who own 5 different pets,
drink 5 different beverages, and smoke 5 different brands of (American) cigarettes. Also,
1. The occupant of the red house is English. 2. The Spaniard owns a dog.
3. The coffee drinker lives in a green house. 4. The Ukranian drinks tea.
5. The ivory house is to the left of the green one. 6. The snail owner smokes Winstons.
7. The person in the yellow house smokes Kools. 8. The occupant in the middle house drinks mil
程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.