0

我正在尝试使用 prolog 解决这个难题,但我很难写下规则并完成解决方案。这就是谜...

上周末是男子一年一度的保龄球锦标赛,对当地市民来说是一场竞赛和乐趣。今年,五位参赛者为冠军争先恐后地打了一场比赛,兴奋之情溢于言表。投球手每赢得一场比赛,他就得到两分,比赛结束时得分最高的投球手获胜。确定每个投球手的全名、他们的高分(264 到 288)以及每个人赢得的分数(28 到 36)。

  1. 弗兰克的姓氏不是汤普森,他的得分最高,但他没有赢得比赛。

  2. 史密斯先生的高分比投球手的 30 分高 3 针。

  3. 史蒂文的姓不是斯图尔特。获得36分的比赛获胜者以奇数获得高分。

  4. 迈克尔以比威廉姆斯先生少 6 分的成绩完赛。

  5. 得分为 273 的投球手比史密斯先生多两分,但比克雷格少两分。

  6. 汤普森先生赢得的分数比沃尔特少,但比史蒂文刘易斯多。

这就是我到目前为止所拥有的......

first[craig].
first[frank].
first[michael].
first[steven].
first[walter].

last[thompson].
last[williams].
last[smith].
last[lewis].
last[stewart].

high[264].
high[288].
high[276].
high[276].
high[273].
high[285].

points[32].
points[34].
points[28].
points[30].
points[36].'''

'''Sol=[[first(craig),last(Thompson), first(FrankWilliams)]]'''

Please help me
[Logic Diagram picture][1]


  [1]: https://i.stack.imgur.com/Wi5lE.png
4

2 回答 2

0

这是一个相当简单但缓慢的解决方案:

go(Persons):-
    length(Persons, 5),
    permutation_persons(Persons),

    % Clue 1
    member(p(frank, FrankSur, FrankScore, 288), Persons),
    FrankSur \= thompson,
    FrankScore \= 36,

    % Clue 2
    member(p(_, smith, SmithScore, SmithHigh), Persons),
    member(p(_, _, 30, Bowler30High), Persons),
    SmithScore \= 30,
    SmithHigh is Bowler30High + 3,

    % Clue 3a
    member(p(steven, StevenSur, _, _), Persons),
    StevenSur \= stewart,

    % Clue 3b
    member(p(_, _, 36, OddHigh), Persons),
    1 is OddHigh mod 2,

    % Clue 4
    member(p(michael, _, MichaelScore, _), Persons),
    member(p(_, williams, WilliamsScore, _), Persons),
    MichaelScore is WilliamsScore - 6,

    % Clue 5
    member(p(_, _, Bowler273Score, 273), Persons),
    Bowler273Score is SmithScore + 2,
    member(p(craig, _, CraigScore, _), Persons),
    Bowler273Score is CraigScore - 2,

    % Clue 6b
    member(p(steven, lewis, StevenScore, _), Persons),

    % Clue 6a
    member(p(_, thompson, ThompsonScore, _), Persons),
    ThompsonScore > StevenScore,
    member(p(walter, _, WalterScore, _), Persons),
    ThompsonScore < WalterScore.


permutation_persons(Persons) :-
    FirstNames = [craig, frank, michael, steven, walter],
    Surnames = [thompson, williams, smith, lewis, stewart],
    Points = [28, 30, 32, 34, 36],
    HighScores = [264, 288, 276, 273, 285],
    permute(FirstNames, FP),
    permute(Surnames, SP),
    permute(HighScores, HP),
    assign_persons(Persons, FP, SP, Points, HP).


assign_persons([], _, _, _, _).
assign_persons([H|T], [HF|TF], [HS|TS], [HP|TP], [HH|TH]) :-
    H = p(HF, HS, HP, HH),
    assign_persons(T, TF, TS, TP, TH).


% Fast permutation (rearrangement)
permute([], []).
permute([X|Rest], L) :-
    permute(Rest, L1),
    select(X, L, L1).

结果 swi-prolog:

?- time(findall(P, go(P), Ps)).
% 27,505,015 inferences, 3.287 CPU in 3.247 seconds (101% CPU, 8367859 Lips)
Ps = [[p(michael,smith,28,276),p(steven,lewis,30,273),p(craig,thompson,32,264),p(frank,williams,34,288),p(walter,stewart,36,285)]].
于 2022-02-19T16:05:57.127 回答
0

我花了很长时间想知道为什么它不能解决一个单一的解决方案,而不查看链接的图片或您的代码,并且没有意识到所有高分都有给定的值。:-|

您的代码last[thompson].可能应该last(thompson).表示“汤普森是一个姓氏”,但是如果不构建所有有效姓氏的列表,就很难从中获得任何有用的东西。从那里您也可以将有效的姓氏放入列表中。

我选择了一个复合词bowler(Firstname, Lastname, Highscore, Points)作为我想看到的输出,所以我列出了Bowlers其中的五个。然后添加线索信息以解决暴力搜索样式中的值,其工作方式如下:

% Mr. Smith’s high score was three pins higher than that of the bowler with 30 points.
member(bowler(_, smith, Hsmith, _), Bowlers),
member(bowler(_, _, H_30, 30), Bowlers),
Hsmith is H_30 + 3,

说“只有当有一个 Bowlers 的成员匹配 smith 作为他们的姓氏并为 smith 匹配了一些高分,而另一个成员匹配了 30 分并为他们得分,并且两个得分变量相差 3 分时,才能找到解决方案。” 在全:

:- use_module(library(dif)).

solve(Bowlers) :-
    % bowler(Firstname, Lastname, Highscore, Points).
    Bowlers = [ bowler(frank,   L1, H1, P1),
                bowler(michael, L2, H2, P2),
                bowler(steven,  L3, H3, P3),
                bowler(craig,   L4, H4, P4),
                bowler(walter,  L5, H5, P5) ],
    
    % everyone has last names from the text
    permutation([L1, L2, L3, L4, L5], [smith, stewart, williams, thompson, lewis]),

    % apparently the scores are evenly distributed one per person, no dupes.
    permutation([P1, P2, P3, P4, P5], [28, 30, 32, 34, 36]),
    
    % the valid high scores, one per person, no dupes.
    permutation([H1, H2, H3, H4, H5], [264, 288, 276, 273, 285]),

    % Frank, whose last name wasn’t Thompson, 
    % had the highest score (288) but he didn’t win the tournament (didn't score 36 points).
    member(bowler(frank, Lfrank, 288, Pfrank), Bowlers),
    dif(Lfrank, thompson),
    dif(Pfrank, 36),
   
    % Mr. Smith’s high score was three pins higher than that of the bowler with 30 points.
    member(bowler(_, smith, Hsmith, _), Bowlers),
    member(bowler(_, _, H_30, 30), Bowlers),
    Hsmith is H_30 + 3,

    % Steven’s last name wasn’t Stewart
    member(bowler(steven, Ssteven, _, _), Bowlers),
    dif(Ssteven, stewart),

    % The winner of the tournament, who had 36 points, had an odd number for a high score.
    member(bowler(_, _, Hwin, 36), Bowlers),
    1 is Hwin /\ 1,

    % Michael finished the tournament with six points less than Mr. Williams.
    member(bowler(michael, _, _, Pmichael), Bowlers),
    member(bowler(_, williams, _, Pwilliams), Bowlers),
    Pmichael is Pwilliams - 6,
    
    % The bowler with a high score of 273 had two points more than Mr. Smith but two points less than Craig.
    member(bowler(_, _, 273, P_273), Bowlers),
    member(bowler(_, smith, _, Psmith), Bowlers),
    member(bowler(craig, _, _, Pcraig), Bowlers),
    P_273 is Psmith + 2,
    P_273 is Pcraig - 2,

    % Mr. Thompson won fewer points than Walter but more than Steven Lewis.
    member(bowler(_, thompson, _, Pthompson), Bowlers),
    member(bowler(walter, _, _, Pwalter), Bowlers),
    member(bowler(steven, lewis, _, Plewis), Bowlers),
    Pthompson < Pwalter,
    Pthompson > Plewis.

这感觉很慢,要解决 1000 万个推理,还有 1700 万个要排除任何其他解决方案:

?- time(solve(B)).
10,099,024 inferences, 1.550 CPU in 1.550 seconds (100% CPU, 6517307 Lips)

B = [bowler(frank, williams, 288, 34), bowler(michael, smith, 276, 28), bowler(steven, lewis, 273, 30), bowler(craig, thompson, 264, 32), bowler(walter, stewart, 285, 36)]
1.550 seconds cpu time

17,191,884 inferences, 2.613 CPU in 2.613 seconds (100% CPU, 6579160 Lips)
false

它从代码顶部向下搜索,生成一个名称排列,一个点,一个分数,然后检查frank没有得到thompson他的姓氏,回溯并再次尝试,直到它生成一个通过所有检查的解决方案。


通过重新排序子句以更快地失败,从而减少失败前的工作,并从文本中添加更多提示,可以减少工作量。例如,从最后一条线索我们知道一个成员肯定是 Steven Smith,我们知道 Frank 的分数是 288,我们可以直接写“Mr Smiths 的分数比……高 3 针”,得到这个版本:

:- use_module(library(dif)).

solve(Bowlers) :-
    % bowler(Firstname, Lastname, Highscore, Points).
    Bowlers = [ bowler(frank,   L1,    288, P1),
                bowler(michael, L2,     H2, P2),
                bowler(steven,  lewis,  H3, P3),
                bowler(craig,   L4,     H4, P4),
                bowler(walter,  L5,     H5, P5) ],
    
    dif(L1, thompson),     % Frank, whose last name wasn’t Thompson
    dif(P1, 36),           %   didn’t win (didn't score 36 points).

    dif(L5, thompson),     % Walter isn't Mr Thompson because they scored differently.
    dif(L4, smith),        % Craig isn't Mr Smith because they scored differently.
    dif(L2, williams),     % Michael isn't Mr Williams because they scored differently.

    % everyone has last names from the text
    permutation([L1, L2, L4, L5], [smith, stewart, williams, thompson]),

    % scores are evenly distributed one per person, no dupes.
    permutation([P1, P2, P3, P4, P5], [28, 30, 32, 34, 36]),

    % Michael finished the tournament with six points less than Mr. Williams.
    member(bowler(_, williams, _, Pwilliams), Bowlers),
    P2 is Pwilliams - 6,
    
    % the valid high scores, one per person, no dupes.
    permutation([H2, H3, H4, H5], [264, 276, 273, 285]),

    % The winner of the tournament, who had 36 points, had an odd number for a high score.
    member(bowler(_, _, Hwin, 36), Bowlers),
    1 is rem(Hwin, 2),

    % Mr. Smith’s high score was three pins higher than that of the bowler with 30 points.
    member(bowler(_, _, H_30, 30), Bowlers),
    Hsmith is H_30 + 3,
    member(bowler(_, smith, Hsmith, Psmith), Bowlers),
   
    % The bowler with a high score of 273 had two points more than Mr. Smith but two points less than Craig.
    P_273 is Psmith + 2,
    member(bowler(_, _, 273, P_273), Bowlers),
    Pcraig is P_273 + 2,
    member(bowler(craig, _, _, Pcraig), Bowlers),
    
    % Mr. Thompson won fewer points than Walter but more than Steven Lewis.
    member(bowler(_, thompson, _, Pthompson), Bowlers),
    member(bowler(walter, _, _, Pwalter), Bowlers),
    Pthompson < Pwalter,
    member(bowler(steven, lewis, _, Plewis), Bowlers),
    Pthompson > Plewis.

这个版本可以:

?- time(solve(B)).
34,664 inferences, 0.007 CPU in 0.007 seconds (100% CPU, 5150062 Lips)

B = [bowler(frank, williams, 288, 34), bowler(michael, smith, 276, 28), bowler(steven, lewis, 273, 30), bowler(craig, thompson, 264, 32), bowler(walter, stewart, 285, 36)]

26,321 inferences, 0.011 CPU in 0.011 seconds (100% CPU, 2397565 Lips)
false

快了近 300 倍。

于 2022-02-20T06:45:27.343 回答