我正在阅读"7天内7种语言"一书，并且已经到达了Prolog章节。作为学习练习，我正在尝试解决一些文本逻辑难题。谜题如下：
五个姐妹的生日都在不同的月份，每个星期的不同日期。使用下面的线索，确定每个姐妹的生日是一周中的月份和日期。
- 宝拉出生于三月，但不是星期六。阿比盖尔的生日不是星期五或星期三。
- 生日是星期一的女孩比布伦达和玛丽早出生。
- 塔拉不是二月出生的，她的生日是在周末。
- 玛丽不是在十二月出生的，她的生日也不是在工作日出生的。生日在六月的女孩出生在星期天。
- 塔拉出生在布伦达之前，布伦达的生日不是星期五。玛丽不是在七月出生的。
对于经验丰富的Prolog程序员来说，我目前的实现可能看起来像一个笑话。代码粘贴在下面。
我希望就如何解决问题以及如何使代码既清晰又密集提供一些意见。
即：
- 我怎样才能避免输入限制说 Days 必须是唯一的。
- 我怎样才能避免输入月份必须是唯一的限制。
- 添加有关生日排序的限制。
is_day(Day) :-
member(Day, [sunday, monday, wednesday, friday, saturday]).
is_month(Month) :-
member(Month, [february, march, june, july, december]).
solve(S) :-
S = [[Name1, Month1, Day1],
[Name2, Month2, Day2],
[Name3, Month3, Day3],
[Name4, Month4, Day4],
[Name5, Month5, Day5]],
% Five girls; Abigail, Brenda, Mary, Paula, Tara
Name1 = abigail,
Name2 = brenda,
Name3 = mary,
Name4 = paula,
Name5 = tara,
is_day(Day1), is_day(Day2), is_day(Day3), is_day(Day4), is_day(Day5),
Day1 == Day2, Day1 == Day3, Day1 == Day4, Day1 == Day5,
Day2 == Day1, Day2 == Day3, Day2 == Day4, Day2 == Day5,
Day3 == Day1, Day3 == Day2, Day3 == Day4, Day3 == Day5,
Day4 == Day1, Day4 == Day2, Day4 == Day3, Day4 == Day5,
is_month(Month1), is_month(Month2), is_month(Month3), is_month(Month4), is_month(Month5),
Month1 == Month2, Month1 == Month3, Month1 == Month4, Month1 == Month5,
Month2 == Month1, Month2 == Month3, Month2 == Month4, Month2 == Month5,
Month3 == Month1, Month3 == Month2, Month3 == Month4, Month3 == Month5,
Month4 == Month1, Month4 == Month2, Month4 == Month3, Month4 == Month5,
% Paula was born in March but not on Saturday.
member([paula, march, _], S),
Day4 == sunday,
% Abigail's birthday was not on Friday or Wednesday.
Day1 == friday,
Day1 == wednesday,
% The girl whose birthday is on Monday was born
% earlier in the year than Brenda and Mary.
% Tara wasn't born in February, and
% her birthday was on the weekend.
Month5 == february,
Day5 == monday, Day5 == wednesday, Day5 == friday,
% Mary was not born in December nor was her
% birthday on a weekday.
Month3 == december,
Day3 == monday, Day3 == wednesday, Day3 == friday,
% The girl whose birthday was in June was
% born on Sunday.
member([_, june, sunday], S),
% Tara was born before Brenda, whose birthday
% wasn't on Friday.
Day2 == friday,
% Mary wasn't born in July.
Month3 == july.
更新 根据chac的答案，我能够解决难题。遵循相同的配方，我们(工作中的编程语言能力小组(也能够解决第二个难题。我已经在 GitHub 上发布了 complemete 实现和示例输出作为要点。
使用 maplist/2 将大大缩短您的代码。例如：
maplist(is_month, [Month1,Month2,Month3,Month4,Month5]).
month/1 可能是比 is_month/1 更好的谓词名称。要声明两个项不同，请使用约束 dif/2。使用 maplist/2 和 dif/2，您可以描述列表包含成对不同的元素：
all_dif([]).
all_dif([L|Ls]) :-
maplist(dif(L), Ls),
all_dif(Ls).
例：
?- all_dif([X,Y,Z]).
dif(X, Z),
dif(X, Y),
dif(Y, Z).
solve/1 是一个命令性名称 - 您正在描述解决方案，因此最好将其称为解决方案/1。
也许谜语未指定，或者您的解决方案不完整：测试您的代码，我得到
?- solve(X),maplist(writeln,X).
[abigail,february,monday]
[brenda,july,wednesday]
[mary,june,sunday]
[paula,march,friday]
[tara,december,saturday]
X = [[abigail, february, monday], [brenda, july, wednesday], [mary, june, sunday], [paula, march, friday], [tara, december, saturday]] ;
[abigail,february,monday]
[brenda,december,wednesday]
[mary,june,sunday]
[paula,march,friday]
[tara,july,saturday]
X = [[abigail, february, monday], [brenda, december, wednesday], [mary, june, sunday], [paula, march, friday], [tara, july, saturday]]
以及更多解决方案。那么布伦达什么时候出生呢？
唯一性的"交易技巧"是使用 select/3 谓词，或者简单地排列/2。使用最后一个代码，代码变成类似
solve(S) :-
S = [[Name1, Month1, Day1],
[Name2, Month2, Day2],
[Name3, Month3, Day3],
[Name4, Month4, Day4],
[Name5, Month5, Day5]],
Girls = [abigail, brenda, mary, paula, tara],
Girls = [Name1, Name2, Name3, Name4, Name5],
Months = [february, march, june, july, december],
Days = [sunday, monday, wednesday, friday, saturday],
permutation(Months, [Month1, Month2, Month3, Month4, Month5]),
permutation(Days, [Day1, Day2, Day3, Day4, Day5]),
% Paula was born in March but not on Saturday.
member([paula, march, C1], S), C1 = saturday,
...
关于"年份之前"的关系可以这样编码：
...
% The girl whose birthday is on Monday was born
% earlier in the year than Brenda and Mary.
member([_, C3, monday], S),
member([brenda, C4, C10], S), before_in_year(C3, C4, Months),
member([mary, C5, _], S), before_in_year(C3, C5, Months),
...
使用服务谓词
before_in_year(X, Y, Months) :-
nth1(Xi, Months, X),
nth1(Yi, Months, Y),
Xi < Yi.
"出生在周末"可以这样编码
...
% Tara wasn't born in February, and
% her birthday was on the weekend.
member([tara, C6, C7], S), C6 = february, (C7 = saturday ; C7 = sunday),
% Mary was not born in December nor was her
% birthday on a weekday.
member([mary, C8, C9], S), C8 = december, (C9 = saturday ; C9 = sunday),
...
等等。重写后，我得到了独特的解决方案
?- solve(X),maplist(writeln,X).
[abigail,february,monday]
[brenda,december,wednesday]
[mary,june,sunday]
[paula,march,friday]
[tara,july,saturday]
X = [[abigail, february, monday], [brenda, december, wednesday], [mary, june, sunday], [paula, march, friday], [tara, july, saturday]] ;
false.
编辑
我刚才注意到我引入了一些冗余成员/2 和自由变量，例如 member([brenda, C4, C10], S),... .那些 C4、C10 可以像原始代码一样被绑定到 Brenda 的变量替换为 Month2、Day2。
这是一个对问题空间使用暴力搜索的解决方案。 说我不为此感到自豪还远远不够。 当然，这个问题有一个更优雅的解决方案。
无论如何：
month(january).
month(february).
month(march).
month(april).
month(may).
month(june).
month(july).
month(august).
month(september).
month(october).
month(november).
month(december).
precedes(january, february).
precedes(february, march).
precedes(march, april).
precedes(april, may).
precedes(may, june).
precedes(june, july).
precedes(july, august).
precedes(august, september).
precedes(september, october).
precedes(october, november).
precedes(november, december).
earlier(M1, M2) :- precedes(M1, M2).
earlier(M1, M2) :- month(M1), month(M2), precedes(M1, X), month(X), earlier(X, M2).
weekday(monday).
weekday(tuesday).
weekday(wednesday).
weekday(thursday).
weekday(friday).
weekend(saturday).
weekend(sunday).
birthmonth(abigail, M) :-
month(M),
M == march.
birthmonth(brenda, M) :-
month(M),
M == march.
birthmonth(paula, march).
birthmonth(mary, M) :-
month(M),
M == march, M == december, M == july.
birthmonth(tara, M) :-
month(M),
M == march,
M == february.
birthday(abigail, D) :-
weekday(D),
D == friday, D == wednesday.
birthday(brenda, D) :-
weekday(D),
D == friday,
D == monday.
birthday(mary, D) :- weekend(D).
birthday(paula, D) :- weekday(D), D ==saturday.
birthday(tara, D) :- weekend(D).
answer(M, D):-
candidate(M, D),
member(june, M),
member(sunday, D),
nth(IM, M, june),
nth(ID, D, sunday),
IM =:= ID,
nth(5, M, MTARA),
nth(2, M, MBRENDA),
earlier(MTARA, MBRENDA),
nth(3, M, MMARY),
nth(IMONDAY, D, monday),
nth(IMONDAY, M, MMONDAY),
earlier(MMONDAY, MBRENDA),
earlier(MMONDAY, MMARY).
candidate([M1,M2,M3,M4,M5], [D1,D2,D3,D4,D5]):-
birthday(abigail, D1),
birthday(brenda, D2),
D1 == D2,
birthday(mary, D3),
D1 == D3,
D2 == D3,
birthday(paula, D4),
D1 == D4,
D2 == D4,
D3 == D4,
birthday(tara, D5),
D1 == D5,
D2 == D5,
D3 == D5,
D4 == D5,
birthmonth(abigail, M1),
birthmonth(brenda, M2),
M1 == M2,
birthmonth(mary, M3),
M1 == M3,
M2 == M3,
birthmonth(paula, M4),
M1 == M4,
M2 == M4,
M3 == M4,
birthmonth(tara, M5),
M1 == M5,
M2 == M5,
M3 == M5,
M4 == M5.
更好的答案是将排序约束作为birthmonth/2或birthday/2子句的一部分实现。 到目前为止，我还没有能够让它发挥作用。
candidate/2实现了相当于几个嵌套for()循环，你看不到，但 WAN(Prolog 的沃伦抽象机器(通过阴谋来迭代值D1, D2, D3......等。
要查看可能的答案，请使用：
answer(M,D).
继续按分号或gprolog中的"a"以查看所有答案。 每个名单的要素按字母顺序对应女孩。
在这种问题中，我喜欢遵循拼图的文本( 与SWI Prolog一起工作6.3.0( ：
week_end(Day) :-
member(Day, [saturday, sunday]).
day(Day) :-
member(Day, [monday, wednesday, friday, saturday, sunday]).
month(Month) :-
member(Month, [february, march, june, july, december]).
before(M1, M2) :-
nth0(I1, [february, march, june, july, december], M1),
nth0(I2, [february, march, june, july, december], M2),
I1 < I2.
names([person(abigail, _, _),
person(brenda, _, _),
person(mary, _, _),
person(paula, _, _),
person(tara, _, _)]).
solve(L) :-
maplist(X^(X = person(_, Day, Month),
day(Day),
month(Month)),
L),
forall((select(X,L, L1), select(Y, L1, _)),
( X = person(_, D1, M1),
Y = person(_, D2, M2),
D1 = D2,
M1 = M2)).
/*
1.Paula was born in March but not on Saturday. Abigail's birthday was not on Friday or Wednesday.
*/
rule_1(L) :-
member(person(paula, D, march), L),
D == saturday,
member(person(abigail, D1, _M), L),
day(D1),
+ member(D1, [friday, wednesday]).
/*
2.The girl whose birthday is on Monday was born earlier in the year than Brenda and Mary.
*/
rule_2(L) :-
member(person(_N, monday, M), L),
member(person(brenda, _D1, M1), L),
member(person(mary, _D2, M2), L),
before(M, M1),
before(M, M2).
/*
3.Tara wasn't born in February and her birthday was on the weekend.
*/
rule_3(L) :-
member(person(tara, D, M), L),
M == february,
week_end(D).
/*
4.Mary was not born in December nor was her birthday on a weekday. The girl whose birthday was in June was born on Sunday.
*/
rule_4(L) :-
member(person(mary, D, M), L),
week_end(D),
M == december,
member(person(_N, sunday, june), L).
/*
5.Tara was born before Brenda, whose birthday wasn't on Friday. Mary wasn't born in July.
*/
rule_5(L) :-
member(person(tara, _DT, MT), L),
member(person(brenda, DB, MB), L),
before(MT, MB),
% DB == friday,
day(DB),
DB = friday,
member(person(mary, _D, M), L),
M == july.
puzzle :-
names(L),
rule_1(L),
rule_2(L),
rule_3(L),
rule_4(L),
rule_5(L),
solve(L),
maplist(writeln, L).
我得到 ：
?- time(puzzle).
person(abigail,monday,february)
person(brenda,wednesday,december)
person(mary,sunday,june)
person(paula,friday,march)
person(tara,saturday,july)
% 45,144 inferences, 0.016 CPU in 0.031 seconds (50% CPU, 3294080 Lips)
true .
从
域中预先唯一选择所有实体可以实现简单易用、"既清晰又密集"的代码。使用数值域便于比较：
day( d(_,D,_), D).
fname( d(N,_,_), N). % first name
month( d(_,_,M), M).
sistersP(X):-
maplist( fname, X, ['Paula', 'Abigail', 'Brenda', 'Mary', 'Tara']),
maplist( month, X, [PM, AM, BM, MM, TM]),
maplist( day, X, [PD, AD, BD, MD, TD]),
permutation( [PM,AM,BM,MM,TM], [2,3,6,7,12]), % months of year
permutation( [PD,AD,BD,MD,TD], [sun,mon,wed,fri,sat]), % days of week
PM = 3, PD == sat, AD == fri, AD == wed, % the five rules,
day(G,mon), member(G,X), month(G,GM), GM < BM, GM < MM, % one per line
TM == 2, (TD == sat ; TD == sun),
MM == 12, (MD == sat ; MD == sun), month(G2,6), day(G2,sun), member(G2,X),
TM < BM, BD == fri, MM == 7.
这只找到一个解决方案，仅使用拼图中提到的一年中的月份和星期几：
?- sistersP(X).
X = [d('Paula', fri, 3), d('Abigail', mon, 2), d('Brenda', wed, 12),
d('Mary', sun, 6), d('Tara', sat, 7)] ;
No
?- time( sistersP(_) ).
% 19,537 inferences, 0.01 CPU in 0.01 seconds (100% CPU, 2624221 Lips)
Yes
?- time( (sistersP(_),fail;true) ). % exhaust the search space
% 56,664 inferences, 0.03 CPU in 0.04 seconds (75% CPU, 2441285 Lips)
Yes
尽快测试，增量选择，可以产生更高效的代码。我喜欢使用我自己的select/2，它让我可以从域中唯一地选择列表元素(即另一个列表，允许比第一个列表长，因此无法使用permutation/2(。
select([A|As],S):- select(A,S,S1),select(As,S1).
select([],_).
sisters(X):-
maplist(fname, X, ['Paula', 'Abigail', 'Brenda', 'Mary', 'Tara']),
maplist(month, X, [PM, AM, BM, MM, TM]),
maplist(day, X, [PD, AD, BD, MD, TD]),
Months = [2,3,6,7,12], %%% [1,2,3,4,5,6,7,8,9,10,11,12],
Days = [sun,mon,wed,fri,sat], %%% [sun,mon,tue,wed,thu,fri,sat],
select(3,Months,M2), PM = 3,
select(PD,Days,D2), PD == sat, % 1a
select(AD,D2,D3), AD == fri, AD == wed, % 1b
select(TM,M2,M3), TM == 2, % 3a
select(MM,M3,M4), MM == 12, MM == 7, % 4a1 % 5c
select(TD,D3,D4), select([TD,MD],[sat,sun]), % 3b % 4a2
month(G,6), day(G,sun), member(G,X), % 4b
select([MD,BD],D4), BD == fri, % 5a
select([BM,AM],M4), TM < BM, % 5b
day(G2,mon), member(G2,X),
month(G2,G2M), G2M < BM, G2M < MM. % 2
运行它：
?- sisters(X).
X = [d('Paula', fri, 3), d('Abigail', mon, 2), d('Brenda', wed, 12),
d('Mary', sun, 6), d('Tara', sat, 7)] ;
No
?- time(sisters(_)).
% 2,071 inferences, 0.00 CPU in 0.00 seconds (?% CPU, Infinite Lips)
Yes
?- time( (sisters(_),fail;true) ). % exhaust the search space
% 2,450 inferences, 0.00 CPU in 0.00 seconds (?% CPU, Infinite Lips)
Yes
使用一年中的所有 12 个月和一周中的 7 天(不幸的是，我一开始是这样做的，:)(，有 4561 个解决方案，第二个代码找到得足够快(0.16 秒，424,600 个推论(。第一个代码，使用 select/2 代替 permutation/2 ，需要 180,400,000 次推理和 75 秒才能产生第一个答案，而第二个更快的代码在 0.01 秒内需要 19,400 个 infs。
一种 #clpfd 的方法 prolog：-
:-use_module(library(clpfd)).
puzzle(Sisters,Months,Days):-
Sisters=[Paula, Brenda, Abigail, Mary, Tara], Sisters ins 1..5,
Months=[Feburary, March, June, July, December], Months ins 1..5,
Days=[Monday, Wednesday, Friday, Saturday, Sunday], Days ins 1..5,
Paula#=March,
Paula#=Saturday,
Abigail#=Friday #/ Abigail #=Wednesday,
Tara#=Feburary #/ (Tara#=Saturday #/ Tara#=Sunday),
Mary#=December #/ (Mary#=Saturday #/ Mary#=Sunday),
Tara#=Brenda-1,
Brenda#=Friday,
Mary#=July,
June#=Sunday,
Brenda #=Monday #/ Mary #=Monday,
all_different(Sisters),
all_different(Months),
all_different(Days),
labeling([], Sisters), labeling([],Months), labeling([], Days).
?-puzzle(Sisters,Months,Days).
OUTPUT:
Days = [1, 3, 4, 2, 5],
Months = [3, 1, 5, 2, 4],
Sisters = [1, 3, 4, 5, 2]
Days = [4, 3, 1, 2, 5],
Months = [3, 1, 5, 2, 4],
Sisters = [1, 3, 4, 5, 2]
Days = [1, 3, 4, 2, 5],
Months = [3, 1, 5, 4, 2],
Sisters = [1, 3, 4, 5, 2]
......