Home > Artificial Intelligence > Solving Logic Puzzles in Prolog: Puzzle 1 of 3

Solving Logic Puzzles in Prolog: Puzzle 1 of 3

Recently I played around with Prolog again to solve 3 small logic puzzles. This post is about solving the first puzzle. This first puzzle consists of 2 individual puzzles that follow the exact same internal structure, so can be solved the exact same way of stating rules in Prolog (just with different content).

The small puzzle: problem and question

There are 4 students: Carrie, Erma, Ora und Tracy. Each has one scholarship and one major subject they study. The goal is to find out which student has which scholarship and studies which subject (with all scholarships and majors being different from each other) from the hints provided. The available scholarships are: 25000, 30000, 35000 and 40000 USD. The available majors are: Astronomy, English, Philosophy, Physics. The following hints are given to solve the problem:

  1. The student who studies Astronomy gets a smaller scholarship than Ora.
  2. Ora is either the one who studies English or the one who studies Philosophy.
  3. Erna has a 10000 USD bigger scholarship than Carrie.
  4. Tracy has a bigger scholarship than the student that studies English.

The small puzzle: the Prolog solution

One way of solving this puzzle in Prolog to ask for a solution (which in our example consists of the 4 students and their associated attributes) that fulfills the rules that we can derive from the 4 hints from above. This is actually pretty short and easy in Prolog syntax:

% ####################################################################
% Logic puzzle solver.
%
% Read definition to prolog:
%   ['puzzle.pl'].
%
% 2) Ask for solutions:
%   solve(Carrie,Erma,Ora,Tracy).
%
% Rainhard Findling
% 10/2015
% ####################################################################

all_members([H],L2) :- member(H,L2).
all_members([H|T],L2) :- member(H,L2), all_members(T, L2).

or([H]) :- H,!.
or([H|_]) :- H,!.
or([_|T]) :- or(T).

solve(Carrie,Erma,Ora,Tracy) :-
% all students
Carrie = [Carrie_scholarship, Carrie_major],
Erma = [Erma_scholarship, Erma_major],
Ora = [Ora_scholarship, Ora_major],
Tracy = [Tracy_scholarship, Tracy_major],
% grouping
All = [Carrie,Erma,Ora,Tracy],
% ensure all values exist once
all_members([25, 30, 35, 40], [Carrie_scholarship, Erma_scholarship, Ora_scholarship, Tracy_scholarship]),
all_members([astronomy, english, philosophy, physics], [Carrie_major, Erma_major, Ora_major, Tracy_major]),
% clue 1
member([C1_scholarship,astronomy], All),
Ora_scholarship > C1_scholarship,
% clue 2
or([Ora_major = english, Ora_major = philosophy]),
% clue 3
member([C3_scholarship, physics], All),
C3_scholarship - Carrie_scholarship =:= 5,
% clue 4
Erma_scholarship - Carrie_scholarship =:= 10,
% clue 5
member([C5_scholarship, english], All),
Tracy_scholarship > C5_scholarship.

If we ask for the solution, the single possible solution is presented:

?- solve(Carrie,Erma,Ora,Tracy).
Carrie = [25, english],
Erma = [35, astronomy],
Ora = [40, philosophy],
Tracy = [30, physics] ;

The slightly bigger puzzle: problem and question

There are 5 car renting contracts. Each has a duration, a pickup location, a car brand and a customer associated to it. The goal is to find out for all contracts, what the customer, duration, car brand and pickup location is (again given the fact that each attribute is unique amongst the contracts). The pickup locations are: Brownfield, Durham, Iowa Falls, Los Altos and Redding. The car brands are: Dodge, Fiat, Hyundai, Jeep and Nissan. The contract duration are 2, 3, 4, 5 and 6 days. And the customer names are Freda, Opal, Penny, Sarah and Vicky. The following hints are given to solve the problem:

  1. The contracts of Vicky, the one with pickup location in Los Altos, the one with pickup location in Durham and the one with the Fiat are all different contracts.
  2. The contract with the Jeep is not in Iowa Falls.
  3. The contract of Vicky and the one with the Nissan are picked up in either Los Altos or Redding.
  4. Penny’s contract is not for 6 days.
  5. The contract in Iowa Falls is for 5 days.
  6. The contract with the Durham is 3 days longer than the contract of Opal.
  7. Of the contract with Nissan and the 2 day contract, one is picked up in Redding and the other is Freda’s contract.
  8. The contract with the Jeep is not for 6 days.
  9. The contract of Opal is 1 day longer than the one with the Hyundai.

The slightly bigger puzzle: the Prolog solution

Again, we can define a solution to fulfill the stated rules:

% ####################################################################
% Logic puzzle solver.
%
% Read definition to prolog:
%   ['puzzle.pl'].
%
% 2) Ask for solutions:
%   solve(Freda, Opal, Penny, Sarah, Vicky).
%
% Rainhard Findling
% 10/2015
% ####################################################################

all_members([H],L2) :- member(H,L2).
all_members([H|T],L2) :- member(H,L2), all_members(T, L2).

all_not([H]) :- not(H).
all_not([H|T]) :- not(H), all_not(T).

all_not_members([H],L2) :- not(member(H,L2)).
all_not_members([H|T],L2) :- not(member(H,L2)), all_not_members(T, L2).

and([H]) :- H.
and([H|T]) :- H, and(T).
or([H]) :- H,!.
or([H|_]) :- H,!.
or([_|T]) :- or(T).

solve(Freda, Opal, Penny, Sarah, Vicky) :-
    % all runners
    Freda = [Freda_car, Freda_location, Freda_days],
    Opal = [Opal_car, Opal_location, Opal_days],
    Penny = [Penny_car, Penny_location, Penny_days],
    Sarah = [Sarah_car, Sarah_location, Sarah_days],
    Vicky = [Vicky_car, Vicky_location, Vicky_days],
    % grouping
    All = [Freda, Opal, Penny, Sarah, Vicky],
    % ensure all values exist once
    all_members([dodge, fiat, hyundai, jeep, nissan], [Freda_car, Opal_car, Penny_car, Sarah_car, Vicky_car]),
    all_members([brownfield, durham, iowafalls, losaltos, redding], [Freda_location, Opal_location, Penny_location, Sarah_location, Vicky_location]),
    all_members([2,3,4,5,6], [Freda_days, Opal_days, Penny_days, Sarah_days, Vicky_days]),
    % clues from easy (fast) to hard (slow)
    % clue 5
    member([_,iowafalls,5], All),
    % clue 9
    member([hyundai,_,C9_days], All),
    Opal_days - C9_days =:= 1,
    % clue 6
    member([_,durham,C6_days], All),
    C6_days - Opal_days =:= 3,
    % clue 4
    not(Penny_days = 6),
    % clue 2
    member([C2_car,iowafalls,_], All),
    not(C2_car = jeep),
    % clue 8
    member([C8_car,_,6], All),
    not(C8_car = jeep),
    % clue 3
    member([nissan,C3_location,_], All),
    or([and([C3_location = losaltos, Vicky_location = redding]), and([C3_location = redding, Vicky_location = losaltos])]),
    % clue 7
    member([nissan, C7_1_location,_], All),
    member([_,C7_2_location, 2], All),
    or([and([Freda_location = C7_1_location, C7_2_location = redding]), and([Freda_location = C7_2_location, C7_1_location = redding])]),
    % clue 1
    member([C1_1_car,losaltos,_], All),
    member([C1_2_car,durham,_], All),
    member([fiat,C1_3_location,_], All),
    all_not_members([C1_1_car, C1_2_car, Vicky_car],[fiat]), %car
    all_not_members([C1_3_location, Vicky_location],[losaltos, durham]). %location

… and ask for it, which again presents the single solution:

?- solve(Freda, Opal, Penny, Sarah, Vicky).
Freda = [nissan, losaltos, 4],
Opal = [jeep, brownfield, 3],
Penny = [fiat, iowafalls, 5],
Sarah = [dodge, durham, 6],
Vicky = [hyundai, redding, 2] ;
  1. April 7, 2016 at 04:40

    Could someone explain what this part of the code does:

    all_members([H],L2) :- member(H,L2).
    all_members([H|T],L2) :- member(H,L2), all_members(T, L2).

    Thanks!

    • April 7, 2016 at 11:00

      Hi, sure:

      the first line simply maps all_members to member if there is only a single element in the list.
      the second line is for lists with multiple elements: it calls member for the first element (“head”), then repeats the process for all remaining elements in the list (“tail”) using tail recursion.
      Hence, a call to all_members only is true if all of the elements in the first list (“[H|T]”) are members of the second list (“L2”).

      Hope this helps.

  2. savo
    May 11, 2017 at 17:48

    Thanks for an awsome article, but I think that the first problem statement is invalid. It says that Ora studies either English or Philosophy and the solution states that she is a Physics major, also it says that Astronomy student gets bigger scholarship than Ora, but solution contradicts it. Hope this helps. Cheers!

    • May 12, 2017 at 09:30

      Thanks for pointing that out! The problem statement and solution have been fixed.

  1. November 29, 2015 at 15:31
  2. December 29, 2015 at 13:37

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: