goran@erix.UUCP (04/15/87)
Here is a solution to the Xmas shoppers problem posted a year or more
back. The problem text is also included.
Some comments about the solution:
The execution time needed to solve the problem is very dependent
on the order in which the clues are given. The clues have been
separated into three classes:
- Simple clues giving information that can be entered straight into
the choosen representation.
- Important clues, involving many couples. Using these clues early
will hopefully reduce the search space significally.
- Other clues.
Inside these classes the clues are stated in the order they were
given in the text. By rearranging the clues and some goals in clues
the execution time can be drastically reduced. The program below
used 82 cpusec on a VAX750, which was reduced to 1.5 cpusec
by some rearranging (almost no backtracking over clues).
An interesting observation is that the text of the solution is
less than twice that of the problem text, 5260 vs 2980 characters
for resonably filtered versions of the solution and problem text.
The generate and test method used in the solution below is very
much adapded to Prolog. Another method that seemed natural to me
when I solved it by hand (took an hour or two) was to repeatedly
scan the clues extracting information that could be safely entered
into the solution, and always apply the constraints on purchases and
items. If I remember correctly almost no backtracking was needed.
I guess a similar method could be used in a program to solve the
problem more efficiently.
The solution below is rather straightforward, the only part that is
somewhat complicated is constraints checking. That part can be
slightly simplified by using a global variable (using something like
assert or record) instead of an extra parameter (F in check_ and fill_
predicates below), but this is costly in execution time. Using assert/
retract increased execution time for the naive version from 82 to 106
cpusec and the clue-optimised version from 1.5 to 3.4 cpusec.
The transpose predicate, used to simplify constraints checking, uses
difference lists to transpose in O(N**2) time. That is off course not
important here, a naive O(N**3) time algorithm would do, as the matrix
is transposed once.
--
Goran Boge
goran@erix.UUCP
Phone: +46 8 719 9993
Mail: TN/T/SU
Ericsson Telecom
S-126 25 STOCKHOLM
Sweden
-----------------------------------------------------------------------
Text of Puzzle:
Christmas was one short month away, and Filene's was crowded with
holiday shoppers. The throngs moved quickly, however, and the vivid
decorations and festivities added a cheerful air. Among the shoppers
on one snowy Saturday morning were members of December 25, a Christmas
shoppers' club of 12 married couples. A Sales Associate waited on all
12 couples consecutively, as they bought a total of 8 each of the
following items:
1. Aris Gloves
2. Airplane Book
3. COCO Perfume
4. Pearl Strands
5. A Football Sweater
6. A Handbag
Each husband and wife were waited on together. Each couple bought
4 items. No two couples bought the same combination of items, and
none of the couples bought two or more of the same item. Using the
following clues, can you determine:
1. The full name of each husband and wife.
2. What order they were waited on.
3. What items each couple bought.
CLUES:
Hint: One husband is Bob, one wife is Elizabeth, and one surname
is Stanton.
1. The Craigs, who bought a handbag, were waited on before the
Murphys, who were not waited on last.
2. The Collins bought Aris gloves, a sweater, and handbag, and
COCO.
3. The couples waited on 8th and 10th bought the Airplane Book.
4. These five couples were waited on consecutively: the Smiths;
Gary and his wife; a couple who bought the Airplane Book and a
handbag; the Swains; and Bill and his wife.
5. Geraldine and her husband did not buy either a handbag or a
sweater.
6. The couple who were waited on last did not buy pearls.
7. One of the items Tom and his wife bought was the Airplane Book.
8. The Marshalls did not buy COCO or pearls.
9. Evelyn and her husband bought Aris gloves but not COCO.
10. These five couples were waited on consecutively: Martha and
her husband; Jack and his wife; the couple who bought Aris gloves,
COCO, the Airplane Book, and a handbag; the couple who did not buy
either pearls or the Airplane Book; and Margaret and her husband.
11. The first five couples waited on all bought COCO.
12. Chuck and his wife did not buy Aris gloves.
13. The couples waited on first, second, and fourth did not buy
a sweater.
14. Eleanor and her husband did not buy COCO.
15. Neither Allen and his wife, who did not buy a handbag, nor
the Anthonys bought Aris gloves.
16. Cheryl and her husband, who were not waited on 10th or 12th,
and John and his wife are two couples who bought both a sweater
and a handbag.
17. The Douglases, who did not buy Aris gloves or a sweater, were
waited on 9th.
18. Adam and his wife, who did not buy a handbag, were waited on
immediately before the Days.
19. Steve and his wife bought pearls, the Airplane Book, a sweater,
and one other item.
20. The last three couples waited on did not buy Aris gloves.
21. The Joneses did not buy a sweater.
22. Susan and her husband bought pearls.
23. George and his wife bought a sweater.
24. The four couples who did not buy Aris gloves are (in no particular
order): Dorothy and her husband; the Craigs; Joe and his wife; and
Rosalyn and her husband (who did not buy a sweater).
25. The O'Connors bought both COCO and a sweater.
26. Sandra and her husband, who did not buy a sweater, were waited on
immediately before Cathleen and her husband.
Logic Problem courtesy of your friends at Dell ... the Puzzle People!
------------------------------------------------------------------------
And here is the solution in Quintus Prolog:
solve:-
init(1,CL),
time(0,T0),
gen(CL),
test(CL),
time(T0,_),
write(' SOLUTION:'),nl,
pr(CL).
% The main datastructure is a list of 12 couples. Each couple
entry contains arrival order (1-12), his name, her name,
family name and a list of 6 items. The list of items indicates
which items the couple did (y) or didn't (n) buy. Considering
the items only, the datastructure may be regarded as a 12 couples
by 6 items matrix.
init(N,[couple(N,_,_,_,[_,_,_,_,_,_])|T]):-
N<12 -> N1 is N+1, init(N1,T) |
true.
gen(CL):-
transpose(CL,CLT), % CLT is used to constraint check columns -
% this makes constraints checking easier.
simple_clues(CL),
constraints(CL,CLT),
important_clues(CL,CLT),
other_clues(CL,CLT).
test(CL):-
check_names_and_purchases(CL,[],[],[],[]).
check_names_and_purchases([],_,_,_,_).
check_names_and_purchases([couple(_,MX,FX,NX,PX)|T],ML,FL,NL,PL):-
\+ member(MX,ML), % MX not in ML
\+ member(FX,FL),
\+ member(NX,NL),
\+ member(PX,PL),
check_names_and_purchases(T,[MX|ML],[FX|FL],[NX|NL],[PX|PL]).
% Naive ordering of clues.
simple_clues(CL):-
% The following simple clues contains information that can be entered
% into CL straight away.
clue3(CL),
clue6(CL),
clue11(CL),
clue13(CL),
clue17(CL),
clue20(CL).
important_clues(CL,CLT):-
% These clues contains information about many couples and will reduce
% the search space substantially.
% Check constraints after each clue.
clue4(CL),
constraints(CL,CLT),
clue10(CL),
constraints(CL,CLT),
clue24(CL),
constraints(CL,CLT).
other_clues(CL,CLT):-
% The rest of the clues. Check constraints now and then.
clue1(CL),
clue2(CL),
clue5(CL),
clue7(CL),
clue8(CL),
clue9(CL),
constraints(CL,CLT),
clue12(CL),
clue14(CL),
clue15(CL),
clue16(CL),
clue18(CL),
clue19(CL),
constraints(CL,CLT),
clue21(CL),
clue22(CL),
clue23(CL),
clue25(CL),
clue26(CL),
name_clue(CL),
constraints(CL,CLT).
% And here are the clues in Prolog
name_clue(CL):-
member(couple(_,bob,_,_,_),CL),
member(couple(_,_,elizabeth,_,_),CL),
member(couple(_,_,_,stanton,_),CL).
clue1(CL):-
before(couple(_,_,_,craig,[_,_,_,_,_,y]),
couple(N1,_,_,murphy,_),CL),
N1=\=12.
clue2(CL):-
member(couple(_,_,_,collin,[y,n,y,n,y,y]),CL).
clue3(CL):-
member(couple( 8,_,_,_,[_,y,_,_,_,_]),CL),
member(couple(10,_,_,_,[_,y,_,_,_,_]),CL).
clue4(CL):-
consec([couple(_,_,_,smith,_),
couple(_,gary,_,_,_),
couple(_,_,_,_,[_,y,_,_,_,y]),
couple(_,_,_,swain,_),
couple(_,bill,_,_,_)],CL).
clue5(CL):-
member(couple(_,_,geraldine,_,[_,_,_,_,n,n]),CL).
clue6(CL):-
member(couple(12,_,_,_,[_,_,_,n,_,_]),CL).
clue7(CL):-
member(couple(_,tom,_,_,[_,y,_,_,_,_]),CL).
clue8(CL):-
member(couple(_,_,_,marshall,[_,_,n,n,_,_]),CL).
clue9(CL):-
member(couple(_,_,evelyn,_,[y,_,n,_,_,_]),CL).
clue10(CL):-
consec([couple(_,_,martha,_,_),
couple(_,jack,_,_,_),
couple(_,_,_,_,[y,y,y,n,n,y]),
couple(_,_,_,_,[_,n,_,n,_,_]),
couple(_,_,margaret,_,_)], CL).
clue11(CL):-
member(couple(1,_,_,_,[_,_,y,_,_,_]),CL),
member(couple(2,_,_,_,[_,_,y,_,_,_]),CL),
member(couple(3,_,_,_,[_,_,y,_,_,_]),CL),
member(couple(4,_,_,_,[_,_,y,_,_,_]),CL),
member(couple(5,_,_,_,[_,_,y,_,_,_]),CL).
clue12(CL):-
member(couple(_,chuck,_,_,[n,_,_,_,_,_]),CL).
clue13(CL):-
member(couple(1,_,_,_,[_,_,_,_,n,_]),CL),
member(couple(2,_,_,_,[_,_,_,_,n,_]),CL),
member(couple(4,_,_,_,[_,_,_,_,n,_]),CL).
clue14(CL):-
member(couple(_,_,eleanor,_,[_,_,n,_,_,_]),CL).
clue15(CL):-
member(couple(N1,allen,_,_,[n,_,_,_,_,n]),CL),
member(couple(N2,_,_,anthony,[n,_,_,_,_,_]),CL),
N1=\=N2.
clue16(CL):-
member(couple(N1,john,_,_,[_,_,_,_,y,y]),CL),
member(couple(N2,_,cheryl,_,[_,_,_,_,y,y]),CL),
N2=\=10,
N2=\=12,
N2=\=N1.
clue17(CL):-
member(couple(9,_,_,douglas,[n,_,_,_,n,_]),CL).
clue18(CL):-
consec([couple(_,adam,_,_,[_,_,_,_,_,n]),
couple(_,_,_,day,_)],CL).
clue19(CL):-
member(couple(_,steve,_,_,[_,y,_,y,y,_]),CL).
clue20(CL):-
member(couple(10,_,_,_,[n,_,_,_,_,_]),CL),
member(couple(11,_,_,_,[n,_,_,_,_,_]),CL),
member(couple(12,_,_,_,[n,_,_,_,_,_]),CL).
clue21(CL):-
member(couple(_,_,_,jones,[_,_,_,_,n,_]),CL).
clue22(CL):-
member(couple(_,_,susan,_,[_,_,_,y,_,_]),CL).
clue23(CL):-
member(couple(_,george,_,_,[_,_,_,_,y,_]),CL).
clue24(CL):-
member(couple(N1,_,dorothy,_,[n,_,_,_,_,_]),CL),
member(couple(N2,_,_,craig,[n,_,_,_,_,_]),CL),
N1=\=N2,
member(couple(N3,joe,_,_,[n,_,_,_,_,_]),CL),
N3=\=N1, N3=\=N2,
member(couple(N4,_,rosalyn,_,[n,_,_,_,n,_]),CL),
N4=\=N1, N4=\=N2, N4=\=N3.
clue25(CL):-
member(couple(_,_,_,oconnor,[_,_,y,_,y,_]),CL).
clue26(CL):-
consec([couple(_,_,sandra,_,[_,_,_,_,n,_]),
couple(_,_,cathleen,_,_)],CL).
% Constraints on the number of items
% - Every couple bought 4 different items out of 6 (row)
% - There are 8 copies of each item (column)
% These constraints are checked and used to fill in purchases
% until nothing more can be filled in.
constraints(CL,CLT):-
% always check purchases (row) and items (columns)
check_purchases(CL,_),
item_constraints(CL,CLT).
purch_constraints(CL,CLT):-
% check purchases and if anything was filled in check items
check_purchases(CL,F),
( F=fill -> item_constraints(CL,CLT) | true ).
item_constraints(CL,CLT):-
% check items and if anything was filled in check purchases
check_items(CLT,F),
( F=fill -> purch_constraints(CL,CLT) | true ).
% check_purchases(X,F) and check_items(X,F) check and fill in
% purchases (rows) and items (columns) using constraints on the
% number of items purchased and the number of items available.
% F indicates if some element was filled (fill) or not (nofill).
% Both predicates fail if some constraint cannot be met.
check_purchases(CL,F):-
fill_purchases(CL,F).
fill_purchases([],nofill):- !.
fill_purchases([],fill).
fill_purchases([couple(_,_,_,_,P)|T],F):-
fill(P,4,2,_,F1) ->
F1=fill, % fail if F1=error
F=fill,
fill_purchases(T,fill) |
fill_purchases(T,F).
check_items(CLT,F):-
fill_items(CLT,F).
fill_items([],nofill):- !.
fill_items([],fill).
fill_items([P|T],F):-
fill(P,8,4,_,F1) ->
F1=fill, % fail if F1=error
F=fill,
fill_items(T,fill) |
fill_items(T,F).
% fill(L,Ny,Nn,V,F) fills unbound variables of L (row or column)
% if possible.
% L is the (tail of) a row (purchase) or column (items) and V its
% unified unbound variables.
% Ny (Nn) is the maximum number of y's (n's) remaining.
% fill succeeds with F=fill if some element is bound.
% If no element is bound, fill fails in order to de-unify unbound elements.
% If some constraint is not met (too many y's or n's) fill succeeds
% with F=error.
% end of L:
fill([],0,Nn,n,fill):- !, Nn=\=0. % Ny=0 => bind remaining variables to n
% fail if Ny=Nn=0 - no element bound
fill([],_,0,y,fill). % Nn=0 => bind remaining variables to y
% fail if Ny and Nn > 0 - no filling
% next element is unbound:
fill([V|T],Ny,Nn,V,F):-
var(V),!,
fill(T,Ny,Nn,V,F).
% next element is y:
fill([y|T],Ny,Nn,V,F):-
Ny=0 -> F=error | % too many y's
Ny1 is Ny-1, fill(T,Ny1,Nn,V,F).
% next element is n:
fill([n|T],Ny,Nn,V,F):-
Nn=0 -> F=error | % too many n's
Nn1 is Nn-1, fill(T,Ny,Nn1,V,F).
% Support predicates
% transpose the couple matrix (O(n**2))
% transpose(M,Tr) Tr == transpose_purchases_part_of(M)
transpose([],[]).
transpose([],[[]|T]):-
transpose([],T).
transpose([couple(_,_,_,_,P)|T],Tr):-
tr_row(P,diff(Tr,TrT)),
transpose(T,TrT).
% transpose a row
% tr_row(Row,TrR) TrR == transpose(Row)
tr_row([],diff([],[])).
tr_row([X|T],diff([[X|XT]|T1],[XT|T2])):-
tr_row(T,diff(T1,T2)).
member(X,[X|_]).
member(X,[_|T]):-
member(X,T).
before(C1,C2,[C1|T]):-
member(C2,T).
before(C1,C2,[_|T]):-
before(C1,C2,T).
consec([X|T1],[X|T2]):-
head_sublist(T1,T2).
consec(S,[_|T]):-
consec(S,T).
head_sublist([],_).
head_sublist([X|T1],[X|T2]):-
head_sublist(T1,T2).
pr([]).
pr([H|T]):-
write(H), nl,
pr(T).
time(TIN,TOUT):-
TIN=0 -> statistics(runtime,[TOUT,_]) |
statistics(runtime,[TOUT,_]),
T is TOUT-TIN,
write(' Extime = '), write(T), write(' ms'), nl.