Examples of puzzles with constraints
Acknowledgement:
based on the book by
October 20, 2020
(CS/RU) Examples of puzzles with constraints October 20, 2020 1 / 11
Wedding puzzle
There are 5 women: Anne, Cathy, Eve, Fran, Ida. Also there are 5 men: Paul, Rob, Stan, Vern, Wally. Five couples were married last week, each on a different weekday. From the information provided, determine the woman and man who make up each couple, as well as the day on wich each couple was married.
1 Anne was married on Monday, but not with Wally.
2 Stan’s wedding was on Wednesday.
3 Rob was married on Friday, but not to Ida.
4 Vern (who married Fran) was married the day after Eve.
Write a Prolog program using smart interleaving of generate and test to solve this CSP problem. It you use any helping predciates, you must implement them.
What are the unknown variables ? What are the domains for the variables ? We have to make sure the constraints are easy to represent.
Since each married couple is uniquely associated with a weekday, it is natural to encode the underlying domain with the atomic statements
day(1). day(2). day(3). day(4). day(5).
The variables are the first letters of the names of the women A,C,E,F,I and the men P, R, S, V , W . Each couple is mapped to same day. How to write a program to solve this puzzle ?
(CS/RU) Examples of puzzles with constraints October 20, 2020 2 / 11
Wedding puzzle: solution
1 Anne was married on Monday, but not with Wally.
2 Stan’s wedding was on Wednesday.
3 Rob was married on Friday, but not to Ida.
4 Vern (who married Fran) was married the day after Eve.
day(1). day(2). day(3). day(4). day(5).
solve([A,C,E,F,I,P,R,S,V,W]) :-
day(A), A=1, day(W), not A=W, /*(1) We still call day(A) */ day(S), S=3, /*(2) Call day(S) since we have to follow the technique*/ day(R), R=5, day(I), not R=I, /* 3 */ day(V), day(F), V=F, day(E), V is E+1, /* (4) implicit constraints? */
day(C),
day(P),
all_diff([A,C,E,F,I]),
all_diff([P,R,S,V,W]).
/* implicit: Cathy got married */ /* implicit: Paul got married */ /* women got married on different days */ /* men got married on different days */
all_diff([ ]).
all_diff([X | List]) :- not member(X,List), all_diff(List).
Questions – ?
(CS/RU) Examples of puzzles with constraints October 20, 2020 3 / 11
Wages puzzle
Ann, Bob, Cindy, Daniel, Eve are working part-time at a company that has several positions with different pay levels. There are the following wages per week that the employees can earn depending on their position within the company: $100, $200, $300, $400, $500. Find wages of all people based on the following constraints.
1 Bob’s wage is different both from Cindy’s wage and from Eve’s wage.
2 Cindy earns less than Daniel, and less than Eve.
3 Ann’s wage is lower than Eve’s wage and it is lower than Bob’s wage.
4 Ann’s wage is different both from Daniel’s wage and from Cindy’s wage.
5 Daniel earns more than Eve and more than Bob.
Write an efficient Prolog program that computes all 5 possible wages subject to all of the given constraints. The program has to follow the interleaving of generate and test technique.
What will be the variables ? What are the domains for variables ? Make sure we can easily formulate the constraints.
Since the puzzle is formulated in terms of wages, it is natural to choose the wages 100, 200, 300, 400, 500 as the domain.
wage(100). wage(200). wage(300). wage(400). wage(500).
How to start writing a program that solves this problem?
(CS/RU) Examples of puzzles with constraints October 20, 2020 4 / 11
Wages puzzle: solution
1 Bob’s wage is different both from Cindy’s wage and from Eve’s wage.
2 Cindy earns less than Daniel, and less than Eve.
3 Ann’s wage is lower than Eve’s wage and it is lower than Bob’s wage.
4 Ann’s wage is different both from Daniel’s wage and from Cindy’s wage.
5 Daniel earns more than Eve and more than Bob.
wage(100). wage(200). wage(300). wage(400). wage(500).
solve([A,B,C,D,E]) :-
wage(B), wage(C), not B=C, wage(E), not B=E,
C < E,
wage(D), C < D,
wage(A), A < E, A < B,
not A=D, not A=C,
D > E, D > B.
/*1*/
/*2*/ /*2*/
/*3*/ /*4*/ /*5*/
October 20, 2020 5 / 11
Questions?
(CS/RU)
Examples of puzzles with constraints
Puzzle about a quiz: cont.
(1) (0.5 point) Using the single predicate answer(X) characterize the finite domain of 2 possible answers to each question: t and f.
(2) (1.5 point) Implement a helping predicate grade(Q1,Q2,Q3,Q4,Q5,A1,A2,A3,A4,A5,N) that holds when N is the grade (the number of correct answers) when a student submits the Qi while the correct answers are the Ai . In other words, the predicate grade takes as inputs Qi , Ai ,
i ∈ {1, 2, 3, 4, 5}, counts the number N of matches between the corresponding elements Qi and Ai , and returns N as an output. Hint: it is easy to implement this predicate using another auxiliary predicate sameAs(L1,L2,N) that counts the number of total matches between the corresponding elements of lists L1 and L2, where L1 and L2 have equal length. For example, sameAs([t,f,f,f,t],[t,t,t,t,t],N) returns N=2, but sameAs([t,f,t,f,t],[f,t,f,t,f],N) returns N=0.
(3) (3 points) Write a Prolog program that solves this instance of CSP. You can use any of the techniques that we studied in class: generate-and-test or interleaving of generate and test. Provide in-line comments indicating which constraints you implement where. Use the predicates answer and grade in your program. You do not need any other helping predicates in your program, but you decide to use them, then implement them as well.
(CS/RU) Examples of puzzles with constraints October 20, 2020 7 / 11
Puzzle about a quiz
The following puzzle can be formulated as a constraint satisfaction problem (CSP). A group of 5 students wrote a quiz that included 5 questions with true/false answers. The answers submitted by these students are as follows
Ann : Bob : Cindy : David : Edward :
true, true, false, true, false false, true, true, true, false true, false, true, true, false false, true, true, false, true true, false, true, false, true
Once students have received their grades
(calculated as the number of correct answers), they found that
1 Cindy got more answers right than Ann.
2 David got more right than Bob.
3 Edward did not get all the answers right, nor did he get them all wrong.
It turns out that these constraints are sufficient to determine the correct answers to all questions from the quiz! Write a Prolog program that can find the correct answers to all the questions. (Do not waste your time on solving this puzzle yourself: your Prolog program should solve it!)
(CS/RU) Examples of puzzles with constraints October 20, 2020 6 / 11
Helping predicates
Hint: implement predicate sameAs(L1,L2,N) that counts the number of total matches between the corresponding elements of lists L1 and L2, where L1 and L2 have equal length.
As usual, do case analysis: what is the base case(s), then recursive rule(s).
same([A],[A],1). /* Base cases */ same([S],[A],0) :- not A=S.
Case 1: if the heads of L1 and L2 match, then add 1 to the counter. Case 2: they do not match, do not change the counter.
sameAs([H | List1], [H | List2], N) :-
sameAs(List1, List2, S), N is S+1.
sameAs([H1 | Tail1], [H2 | Tail2], N) :- not H1=H2,
sameAs(Tail1, Tail2, N).
/* Case 1 */
/*Case 2*/
How to implement grade(Q1,Q2,Q3,Q4,Q5,A1,A2,A3,A4,A5,N) ? grade(Q1,Q2,Q3,Q4,Q5, A1,A2,A3,A4,A5, N) :
sameAs([Q1,Q2,Q3,Q4,Q5], [A1,A2,A3,A4,A5], N). Use the predicates answer and grade in your program.
(CS/RU) Examples of puzzles with constraints October 20, 2020 8 / 11
Prolog program that solves CSP
Ann : Bob : Cindy : David : Edward :
true, true, false, false, true, true, true, false, true, false, true, true, true, false, true,
true, false true, false true, false false, true false, true
Once students have received their grades (calculated as the number of correct answers), they found that
1 Cindy got more answers right than Ann.
2 David got more right than Bob.
3 Edward did not get all the answers right, nor did he get them all wrong.
answer(t). answer(f).
solve([A1,A2,A3,A4,A5]) :- /*find correct quiz answers only */
answer(A1), answer(A2), /* generate values for variables */ answer(A3), answer(A4), answer(A5),
grade(t,t,f,t,f,A1,A2,A3,A4,A5,NA),
grade(f,t,t,t,f,A1,A2,A3,A4,A5,NB),
grade(t,f,t,t,f,A1,A2,A3,A4,A5,NC),
grade(f,t,t,f,t,A1,A2,A3,A4,A5,ND),
grade(t,f,t,f,t,A1,A2,A3,A4,A5,NE),
/* NA is the grade for Ann */
/* NB is the grade for Bob */ /*NC is the grade for Cindy */ /*grade for David */ /*grade for Edward */
NC > NA,
ND > NB,
NE > 0, NE < 5.
(CS/RU)
/* the 1st constraint */ /* the 2nd constraint */ /*howtoimprovethisprogram? */
Examples of puzzles with constraints October 20, 2020 9 / 11
(CS/RU) Examples of puzzles with constraints October 20, 2020 11 / 11
?- reachable(boston).
init(toronto).
road(toronto,edmonton). road(ottawa,montreal). road(montreal,boston).
reachable(X) :- init(X).
reachable(Z) :- road(Y,Z), reachable(Y).
(CS/RU) Examples of puzzles with constraints October 20, 2020 10 / 11