0

I am trying to solve this puzzle using prolog and I am having difficulty writing down the rules and finishing the solution. This is the puzzle...

Last weekend was the men’s annual bowling tournament, an event of competition and fun for the local townspeople. This year, excitement ran high as five contestants bowled neck and neck for the championship. Each time a bowler won a game, he scored two points and the bowler with the highest number of points at the end of the tournament won. Determine the full name of each bowler, their high score (264 to 288), and how many points each won (28 to 36).

  1. Frank, whose last name wasn’t Thompson, had the highest score but he didn’t win the tournament.

  2. Mr. Smith’s high score was three pins higher than that of the bowler with 30 points.

  3. Steven’s last name wasn’t Stewart. The winner of the tournament, who had 36 points, had an odd number for a high score.

  4. Michael finished the tournament with six points less than Mr. Williams.

  5. The bowler with a high score of 273 had two points more than Mr. Smith but two points less than Craig.

  6. Mr. Thompson won fewer points than Walter but more than Steven Lewis.

And this is what I have so far...

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
false
  • 10,264
  • 13
  • 101
  • 209
Zaywillaa
  • 27
  • 4
  • Useful URLs: https://stackoverflow.com/questions/9252656/einsteins-riddle-prolog and https://rosettacode.org/wiki/Zebra_puzzle#Prolog – brebs Feb 18 '22 at 16:31

2 Answers2

0

This is a fairly simple but slow solution:

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

Result in 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)]].
brebs
  • 3,462
  • 2
  • 3
  • 12
  • Why do we use the H and T in assign persons – Zaywillaa Feb 20 '22 at 14:04
  • H means Head, T means Tail, for standard one-element-at-a-time list processing which also takes advantage of first-element indexing - https://stackoverflow.com/questions/51290263/why-does-this-predicate-leave-behind-a-choicepoint – brebs Feb 20 '22 at 15:13
0

I spent a long time on this wondering why it doesn't solve to a single solution, without looking at the linked picture or your code, and didn't realise there were given values for all the highscores. :-|

Your code last[thompson]. should probably be last(thompson). to mean "thompson is a last name", but from there it's hard to get anything useful from it without building a list of all valid last names. And from there you may as well put the valid last names in a list.

I've chosen a compound term bowler(Firstname, Lastname, Highscore, Points) as the output I want to see, so I've made a list of Bowlers with five of those in it. Then added the clue information to solve for the values in a brute-force search style which works like this:

% 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,

says "the solution is only found when there is a member of Bowlers matching smith as their surname and some highscore for smith, and another member with 30 points and score for them, and the two score variables are 3 points apart". In full:

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

This feels slow, 10 million inferences to solve, and a further 17 million to rule out any other solutions:

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

It searches from the top of the code down generating one permutation of names, one of points, one of scores, then checks frank didn't get thompson as his surname, retraces and tries again until it generates a solution which passes all the checks.

By reordering the clauses to fail faster so it does less work before failing, and adding more hints from the text, the amount of work can be reduced. e.g. from the last clue we know one member is definitely Steven Smith, we know Frank had a score of 288, we can directly write "Mr Smiths score is 3 pins higher than...", to get this version:

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

This version does:

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

Almost 300x faster.

TessellatingHeckler
  • 27,511
  • 4
  • 48
  • 87
  • Okay now I see what is the meaning of the use module library? What does it do and why does it matter? – Zaywillaa Feb 20 '22 at 14:02
  • (I answered in another comment on another question; use_module() loads library code. SWI Prolog will load some libraries automatically, and others it won't. `dif` makes sure things have different values, and cannot be loaded automatically just by using it, it needs use_module to make it available). – TessellatingHeckler Feb 20 '22 at 20:09