prolog - 在 Prolog 中解决文本逻辑难题 - 查找生日和月份

Question

我正在阅读“7 天内的 7 种语言”一书，并且已经读到了 Prolog 章节。作为学习练习，我试图解决一些文本逻辑难题。谜题如下：

五姐妹的生日都在不同的月份和一周中的不同日子。使用下面的线索，确定每个姐妹的生日是星期几。

1. 宝拉出生于三月，但不是星期六。阿比盖尔的生日不在周五或周三。
2. 星期一生日的女孩比布伦达和玛丽出生得早。
3. 塔拉不是二月份出生的，她的生日是在周末。
4. 玛丽不是在十二月出生，她的生日也不是在工作日。那个六月份生日的女孩是星期天出生的。
5. 塔拉在布伦达之前出生，布伦达的生日不是星期五。玛丽不是七月出生的。

对于有经验的 Prolog 程序员来说，我当前的实现可能看起来像是一个笑话。代码粘贴在下面。

我希望得到一些关于如何解决问题以及如何使代码既清晰又密集的意见。

IE：

1. 我怎样才能避免输入限制说天数必须是唯一的。
2. 我怎样才能避免输入月份必须是唯一的限制。
3. 添加关于生日排序的限制。

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 上发布了完整的实现和示例输出作为要点。

Answer 1

使用 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 是一个命令式名称 - 您正在描述解决方案，因此最好将其称为 solution/1。

Answer 2

也许谜语没有说明，或者你的解决方案不完整：测试你的代码，我明白了

?- 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.

编辑

我刚才注意到我引入了一些冗余的 member/2 和自由变量，比如member([brenda, C4, C10], S),.... 那些 C4、C10 可以被绑定到 Brenda 的变量替换为 Month2、Day2，就像在原始代码中一样。

Answer 3

这是一个在问题空间上使用蛮力搜索的解决方案。说我不为此感到骄傲是不够的。当然，这个问题有更优雅的解决方案。

反正：

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/2orbirthday/2子句的一部分来实现。到目前为止，我还无法让它发挥作用。

candidate/2实现了相当于几个嵌套for()循环，你看不到，但 WAM（Prolog 的 Warren 抽象机）通过机制来迭代值D1, D2, D3......等等。

要查看可能的答案，请使用：

answer(M,D).

继续按分号或 gprolog 中的“a”以查看所有答案。每个列表的元素按字母顺序对应于女孩。

Answer 4

唯一地——预先从域中选择所有实体可以实现简单、“既清晰又密集”的代码。使用数字域可以轻松进行比较：

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/2used 代替permutation/2，需要180,400,000 次推理和 75 秒才能产生第一个答案，而第二个更快的代码需要 19,400 个 infs 在 0.01 秒内。

Answer 5

在这类问题中，我喜欢按照拼图的文本（与 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 .

Answer 6

#clpfd 方法序言：-

:-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]
......