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

Question

我正在阅读"7天内的7种语言“-book，并且已经读到了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上作为gist完成实现和示例输出。

Answer 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]] 

还有更多的解决方案。布伦达什么时候出生的？

惟一性的一个“交易技巧”是使用选择/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，就像原始代码中的那样。

Answer 2

使用maplist/2将大大缩短代码。例如：

maplist(is_month, [Month1,Month2,Month3,Month4,Month5]).

月份/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).

求解/1是一个命令式名称--您正在描述解决方案，所以最好将其称为解决方案/1。

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/2或birthday/2子句的一部分来实现。到目前为止，我还没能让它起作用。

candidate/2实现了相当于两个嵌套for()循环的东西，您看不到这些循环，但是WAM (Prolog的沃伦抽象机器)经过了迭代值D1, D2, D3.等。

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

answer(M,D).

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