[bp-users]Puzzle to solve in prolog
Neng-Fa Zhou
zhou@sci.brooklyn.cuny.edu
Mon, 18 Nov 2002 14:21:59 -0800
This is a multi-part message in MIME format.
------=_NextPart_000_0093_01C28F0D.DB701DE0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Ken wrote:
>Hey guys,
>Can anyone help me in solving this puzzle in prolog code? I'm having =
problems.
>...
Here is a CLP(FD) program I wrote, which runs on B-Prolog and should run =
on other CLP(FD) systems that support non-integer finite domains. You =
can change it into a generate-and-test style Prolog program, but the =
program may be extremely slow.
Neng-Fa Zhou
% Problem posted by Ken
% Logic Problems Issue 16 page 46
% Program written by Neng-Fa Zhou, 2002
% Run on B-Prolog 6.x (www.probp.com)
%
%On one page of the visitor's book at Sandholme Castle, seat of the Duke =
of
%Wallingfen, were the names of ten couples from various locations in the
%English-speaking world who had paid to look round the ancestral pile.
%From the clues given below, can you fill in the blank page of the book =
with
%the surnames and home-towns of each couple?
%
%Clues:
%1. The Drummonds are from Edinburgh; their name appears on the line =
above the
% Jones family, who were not the last couple to sign the page.=20
%2. Mr and Mrs Ince's signatures are immediately followed by those of =
the London couple.
%3. The couple on line 3 gave a North American address; their surname =
contains
% two more letters than that of the Portsmouth pair and three more =
than that
% of the couple on line 9.
%4. Only one couple's surname initial immediately preceeds that of the =
next
% family to sign; they are not the Childers family, whose name appears =
on line 5
% and who do not live in Melbourne.
%5. Bristol is the address on the line above Durban; one of these cities =
is the
% home of the Adams family.
%6. The Los Angeles couple signed on line 8; their surname contains an =
even
% number of letters.
%7. Mr and Mrs Fellowes, who are not transatlantic visitors, wrote their =
name on
% an odd-numbered line, unlike the couple from Wellington.
%8. The Toronto family's name immediately follows that of the =
Harringtons, who
% are not from Washington.
%9. Mr and Mrs Bourne signed on the lower half of the page, whilst the =
Giles
% family, who did not sign on line 6, are not resident in the U.K.
%
%London, Edinburgh, Bristol and Portsmouth are all in the U.K. Durban is =
in
%South Africa. Los Angeles and Washington (D.C.) are in the U.S.A. =
Toronto is in
%Canada. Wellington is in NewZealand. And of course, Melbourne is in =
Australia.
/*=20
This is the solution to check your answer with.
L =3D [[1, drummond, edinburgh], [2, jones, portsmouth], [3, edwards, =
washington], [4, giles, wellington], [5, childers, bristol], [6, adams, =
durban], [7, fellowes, melbourne], [8, harrington, los_angeles], [9, =
ince, toronto], [10, bourne, london]]
*/
=20
go:-
Persons=3D[person("adams",Cadams,Ladams),
person("ince",Cince,Lince),
person("childers",Cchilders,Lchilders),
person("bourne",Cbourne,Lbourne),
person("drummond",Cdrummond,Ldrummond),
person("edwards",Cedwards,Ledwards), =20
person("fellowes",Cfellowes,Lfellowes),
person("giles",Cgiles,Lgiles),
person("harrington",Charrington,Lharrington),
person("jones",Cjones,Ljones)],
=
Lines=3D[Ladams,Lince,Lchilders,Lbourne,Ldrummond,Ledwards,Lfellowes,Lgil=
es,Lharrington,Ljones],
Lines :: 1..10,
alldifferent(Lines),
=
Cities=3D[Cadams,Cince,Cchilders,Cbourne,Cdrummond,Cedwards,Cfellowes,Cgi=
les,Charrington,Cjones],
Cities :: =
[london,edinburgh,bristol,portsmouth,durban,la,washington,toronto,welling=
ton,melbourne],
alldifferent(Cities),
=20
%clue 1
Cdrummond=3Dedinburgh,
Ldrummond #< Ljones,
Ljones #\=3D 10,
%clue 2
Llondon #=3D Lince+1,
%clue 3
C3 :: [la,washington,toronto],
N3Len #=3D NportsmouthLen+2,
N3Len #=3D N9Len+3,
%clue 4
Lchilders =3D 5,
Cchilders #\=3D melbourne,
%clue 5
Lbristol #=3D Ldurban-1,
Cadams :: [durban,bristol],
%clue 6
Lla =3D 8,
NlaLen #=3D 2*_,
%clue 7
Lfellowes #=3D 2*_+1,
Cfellowes notin =
[la,washington,toronto,edinburgh,bristol,portsmouth],
Lwellington #=3D 2*_,
%clue 8
Ltoronto #=3D Lharrington+1,
Charrington #\=3D washington,
%clue 9
Lbourne #> 5,
Lgiles #\=3D 6,
Cgiles notin [edinburgh,bristol,portsmouth],
labeling(Lines), % find a permutation
%check other clues
member(person(_,london,Llondon),Persons),
member(person(N3,C3,3),Persons),
length(N3,N3Len), =20
member(person(Nportsmouth,portsmouth,Lportsmouth),Persons),
length(Nportsmouth,NportsmouthLen),
member(person(N9,_,9),Persons),
length(N9,N9Len),
% clue 4
findall(preceed(P1,P2),preceed(P1,P2,Persons),Preceeds),
length(Preceeds,NumPreceeds),NumPreceeds =3D:=3D1,
%
member(person(Ndurban,durban,Ldurban),Persons),
member(person(Nbristol,bristol,Lbristol),Persons),
member(person(Nla,la,Lla),Persons),
length(Nla,NlaLen),
member(person(Nwellington,wellington,Lwellington),Persons),
member(person(Ntoronto,toronto,Ltoronto),Persons),
write_persons(Persons,1),nl.
write_persons(Persons,N):-
member(person(Name,City,N),Persons),!,
write(N),write(':'),write_string(Name),write(':'),write(City),nl,
N1 is N+1,
write_persons(Persons,N1).
write_persons(Persons,N).
preceed(P1,P2,Persons):-
member(person(P1,_,L1),Persons),
P1 \=3D "childers",
L2 is L1+1,
member(person(P2,_,L2),Persons),
P2 \=3D "childers",
P1=3D[C1|_],
P2=3D[C2|_],
C1 =3D:=3D C2-1.
=20
------=_NextPart_000_0093_01C28F0D.DB701DE0
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Diso-8859-1">
<META content=3D"MSHTML 6.00.2600.0" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial size=3D2>
<DIV>Ken wrote:</DIV>
<DIV>>Hey guys,</DIV>
<DIV>>Can anyone help me in solving this puzzle in prolog code? I'm =
having=20
problems.</DIV>
<DIV>>...</DIV>
<DIV> </DIV>
<DIV>Here is a CLP(FD) program I wrote, which runs on =
B-Prolog=20
and should run on other CLP(FD) systems that support =
non-integer=20
finite domains. You can change it into a generate-and-test style Prolog =
program,=20
but the program may be extremely slow.</DIV>
<DIV> </DIV>
<DIV>Neng-Fa Zhou</DIV>
<DIV> </DIV>
<DIV>% Problem posted by Ken<BR>% Logic Problems Issue 16 page 46<BR>% =
Program=20
written by Neng-Fa Zhou, 2002<BR>% Run on B-Prolog 6.x (<A=20
href=3D"http://www.probp.com">www.probp.com</A>)<BR>%<BR>%On one page of =
the=20
visitor's book at Sandholme Castle, seat of the Duke of<BR>%Wallingfen, =
were the=20
names of ten couples from various locations in the<BR>%English-speaking =
world=20
who had paid to look round the ancestral pile.<BR>%From the clues given =
below,=20
can you fill in the blank page of the book with<BR>%the surnames and =
home-towns=20
of each couple?<BR>%<BR>%Clues:<BR>%1. The Drummonds are from Edinburgh; =
their=20
name appears on the line above the<BR>% Jones family, who =
were not=20
the last couple to sign the page. <BR>%2. Mr and Mrs Ince's signatures =
are=20
immediately followed by those of the London couple.<BR>%3. The couple on =
line 3=20
gave a North American address; their surname contains<BR>% =
two more=20
letters than that of the Portsmouth pair and three more than=20
that<BR>% of the couple on line 9.<BR>%4. Only one couple's =
surname=20
initial immediately preceeds that of the next<BR>% family to sign; =
they=20
are not the Childers family, whose name appears on line =
5<BR>% and=20
who do not live in Melbourne.<BR>%5. Bristol is the address on the line =
above=20
Durban; one of these cities is the<BR>% home of the Adams=20
family.<BR>%6. The Los Angeles couple signed on line 8; their surname =
contains=20
an even<BR>% number of letters.<BR>%7. Mr and Mrs Fellowes, =
who are=20
not transatlantic visitors, wrote their name on<BR>% an =
odd-numbered=20
line, unlike the couple from Wellington.<BR>%8. The Toronto family's =
name=20
immediately follows that of the Harringtons, who<BR>% are =
not from=20
Washington.<BR>%9. Mr and Mrs Bourne signed on the lower half of the =
page,=20
whilst the Giles<BR>% family, who did not sign on line 6, =
are not=20
resident in the U.K.<BR>%<BR>%London, Edinburgh, Bristol and Portsmouth =
are all=20
in the U.K. Durban is in<BR>%South Africa. Los Angeles and Washington =
(D.C.) are=20
in the U.S.A. Toronto is in<BR>%Canada. Wellington is in NewZealand. And =
of=20
course, Melbourne is in Australia.<BR>/* <BR>This is the solution to =
check your=20
answer with.<BR>L =3D [[1, drummond, edinburgh], [2, jones, portsmouth], =
[3,=20
edwards, washington], [4, giles, wellington], [5, childers, bristol], =
[6, adams,=20
durban], [7, fellowes, melbourne], [8, harrington, los_angeles], [9, =
ince,=20
toronto], [10, bourne, =
london]]<BR>*/<BR> <BR>go:-<BR> =20
Persons=3D[person("adams",Cadams,Ladams),<BR> &nbs=
p;=20
person("ince",Cince,Lince),<BR> =20
person("childers",Cchilders,Lchilders),<BR> =
=20
person("bourne",Cbourne,Lbourne),<BR> =20
person("drummond",Cdrummond,Ldrummond),<BR> =
=20
person("edwards",Cedwards,Ledwards), =20
<BR> =20
person("fellowes",Cfellowes,Lfellowes),<BR> =
=20
person("giles",Cgiles,Lgiles),<BR> =20
person("harrington",Charrington,Lharrington),<BR> =
=20
person("jones",Cjones,Ljones)],<BR> =20
Lines=3D[Ladams,Lince,Lchilders,Lbourne,Ldrummond,Ledwards,Lfellowes,Lgil=
es,Lharrington,Ljones],<BR> =20
Lines :: 1..10,<BR> =
alldifferent(Lines),<BR> =20
Cities=3D[Cadams,Cince,Cchilders,Cbourne,Cdrummond,Cedwards,Cfellowes,Cgi=
les,Charrington,Cjones],<BR> =20
Cities ::=20
[london,edinburgh,bristol,portsmouth,durban,la,washington,toronto,welling=
ton,melbourne],<BR> =20
alldifferent(Cities),<BR> <BR> %clue =
1<BR> Cdrummond=3Dedinburgh,<BR> =
Ldrummond=20
#< Ljones,<BR> Ljones #\=3D 10,</DIV>
<DIV> </DIV>
<DIV> %clue 2<BR> Llondon #=3D =
Lince+1,</DIV>
<DIV> </DIV>
<DIV> %clue 3<BR> C3 ::=20
[la,washington,toronto],<BR> N3Len #=3D=20
NportsmouthLen+2,<BR> N3Len #=3D N9Len+3,</DIV>
<DIV> </DIV>
<DIV> %clue 4<BR> Lchilders =3D=20
5,<BR> Cchilders #\=3D melbourne,</DIV>
<DIV> </DIV>
<DIV> %clue 5<BR> Lbristol #=3D=20
Ldurban-1,<BR> Cadams :: [durban,bristol],</DIV>
<DIV> </DIV>
<DIV> %clue 6<BR> Lla =3D=20
8,<BR> NlaLen #=3D 2*_,</DIV>
<DIV> </DIV>
<DIV> %clue 7<BR> Lfellowes =
#=3D=20
2*_+1,<BR> Cfellowes notin=20
[la,washington,toronto,edinburgh,bristol,portsmouth],<BR> &nbs=
p;=20
Lwellington #=3D 2*_,</DIV>
<DIV> </DIV>
<DIV> %clue 8<BR> Ltoronto #=3D=20
Lharrington+1,<BR> Charrington #\=3D washington,</DIV>
<DIV> </DIV>
<DIV> %clue 9<BR> Lbourne #>=20
5,<BR> Lgiles #\=3D 6,<BR> Cgiles =
notin=20
[edinburgh,bristol,portsmouth],</DIV>
<DIV> </DIV>
<DIV> labeling(Lines), % find a=20
permutation<BR> %check other =
clues<BR> =20
member(person(_,london,Llondon),Persons),<BR> =20
member(person(N3,C3,3),Persons),<BR> =20
length(N3,N3Len), <BR> =20
member(person(Nportsmouth,portsmouth,Lportsmouth),Persons),<BR> &nbs=
p; =20
length(Nportsmouth,NportsmouthLen),<BR> =20
member(person(N9,_,9),Persons),<BR> =20
length(N9,N9Len),<BR> % clue 4<BR> =20
findall(preceed(P1,P2),preceed(P1,P2,Persons),Preceeds),<BR> &=
nbsp;=20
length(Preceeds,NumPreceeds),NumPreceeds =3D:=3D1,<BR> =
%<BR> =20
member(person(Ndurban,durban,Ldurban),Persons),<BR> =20
member(person(Nbristol,bristol,Lbristol),Persons),<BR> =
member(person(Nla,la,Lla),Persons),<BR> =20
length(Nla,NlaLen),<BR> =20
member(person(Nwellington,wellington,Lwellington),Persons),<BR> &nbs=
p; =20
member(person(Ntoronto,toronto,Ltoronto),Persons),<BR> =
write_persons(Persons,1),nl.</DIV>
<DIV> </DIV>
<DIV>write_persons(Persons,N):-<BR> =20
member(person(Name,City,N),Persons),!,<BR> =20
write(N),write(':'),write_string(Name),write(':'),write(City),nl,<BR>&nbs=
p; =20
N1 is N+1,<BR> =20
write_persons(Persons,N1).<BR>write_persons(Persons,N).</DIV>
<DIV> </DIV>
<DIV>preceed(P1,P2,Persons):-<BR> =20
member(person(P1,_,L1),Persons),<BR> P1 \=3D=20
"childers",<BR> L2 is L1+1,<BR> =20
member(person(P2,_,L2),Persons),<BR> P2 \=3D=20
"childers",<BR> P1=3D[C1|_],<BR> =20
P2=3D[C2|_],<BR> C1 =3D:=3D =
C2-1.<BR> =20
<BR></DIV></FONT></DIV></BODY></HTML>
------=_NextPart_000_0093_01C28F0D.DB701DE0--