Archive

Posts Tagged ‘einstein’

Einstein Riddle/Zebra Puzzle in Prolog

einsteinIn this post we solve another logic puzzle deriving rules from the puzzle and stating them in Prolog. And this time it is a rather famous puzzle one: the Zebra puzzle (also called Einstein riddle/puzzle).

The puzzle

The setting is as follows: there is a group of 5 people. Each person lives in exactly one house, has exactly one nationality and exactly one pet, drinks exactly one drink and smokes exactly one brand of cigarettes. Different goals are possible: a famous one is “who drinks water and who owns the zebra”. But one could instead also define the goal to derive for all houses and people: who lives is which house, has which nationality and which pet, drinks which drink and smokes which brand of cigarettes – given the fact, that each of these attributes is unique among the people in our group. This is the question we are going to answer. The following hints are provided (from Wikipedia):

  1.     There are five houses.
  2.     The Englishman lives in the red house.
  3.     The Spaniard owns the dog.
  4.     Coffee is drunk in the green house.
  5.     The Ukrainian drinks tea.
  6.     The green house is immediately to the right of the ivory house.
  7.     The Old Gold smoker owns snails.
  8.     Kools are smoked in the yellow house.
  9.     Milk is drunk in the middle house.
  10.     The Norwegian lives in the first house.
  11.     The man who smokes Chesterfields lives in the house next to the man with the fox.
  12.     Kools are smoked in the house next to the house where the horse is kept.
  13.     The Lucky Strike smoker drinks orange juice.
  14.     The Japanese smokes Parliaments.
  15.     The Norwegian lives next to the blue house.

Puzzle solution in Prolog

We now need to write the knowledge from above as Prolog rules and ask for a solution fulfilling these rules:

% ####################################################################
% Zebra puzzle solver. A house is a list with 6 attributes:
% 1. Color
% 2. Nationality
% 3. Drink
% 4. Cigarettes
% 5. Pet
% 6. The housenumber (fixed by hand to avoid redundant solutions)
%
% Steps to obtain the solution:
%
% 1) Read definition to prolog:
%   ['zebra_puzzle.pl'].
%
% 2) Ask for solutions:
%   solve(H1,H2,H3,H4,H5).
%
% Rainhard Findling
% 09/2015
% ####################################################################

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

% ####################################################################
% RULES
% ####################################################################

% rule 1 (5 houses) is implicit for our implementation

rule2(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [red,england,_,_,_,_].

rule3(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [_,spain,_,_,dog,_].

rule4(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [green,_,coffee,_,_,_].

rule5(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [_,ukraine,tea,_,_,_].

rule6(H1,H2,H3,H4,H5) :-
    member(HL,[H1,H2,H3,H4,H5]),
    member(HR,[H1,H2,H3,H4,H5]),
    HL = [white,_,_,_,_,NrL],
    HR = [green,_,_,_,_,NrR],
    NrR-NrL =:= 1.

rule7(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [_,_,_,altemgold,snails,_].

rule8(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [yellow,_,_,kools,_,_].

rule9(_,_,H3,_,_) :-
    H3 = [_,_,milk,_,_,3].

rule10(H1,_,_,_,_) :-
    H1 = [_,norway,_,_,_,1].

rule11(H1,H2,H3,H4,H5) :-
    member(HL,[H1,H2,H3,H4,H5]),
    member(HR,[H1,H2,H3,H4,H5]),
    HL = [_,_,_,chesterfield,_,NrL],
    HR = [_,_,_,_,fox,NrR],
    abs(NrL-NrR,1).

rule12(H1,H2,H3,H4,H5) :-
    member(HL,[H1,H2,H3,H4,H5]),
    member(HR,[H1,H2,H3,H4,H5]),
    HL = [_,_,_,kools,_,NrL],
    HR = [_,_,_,_,horse,NrR],
    abs(NrL-NrR,1).

rule13(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [_,_,orange,luckystrike,_,_].

rule14(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [_,japan,_,parliament,_,_].

rule15(H1,H2,H3,H4,H5) :-
    member(HL,[H1,H2,H3,H4,H5]),
    member(HR,[H1,H2,H3,H4,H5]),
    HL = [_,norway,_,_,_,NrL],
    HR = [blue,_,_,_,_,NrR],
    abs(NrL-NrR,1).

% ####################################################################
% solve the puzzle
% ####################################################################

solve(H1,H2,H3,H4,H5) :-
    % bind houses to position to avoid multiple solutions with switched variables
    H1 = [H1_col,H1_nat,H1_drink,H1_cig,H1_pet,1],
    H2 = [H2_col,H2_nat,H2_drink,H2_cig,H2_pet,2],
    H3 = [H3_col,H3_nat,H3_drink,H3_cig,H3_pet,3],
    H4 = [H4_col,H4_nat,H4_drink,H4_cig,H4_pet,4],
    H5 = [H5_col,H5_nat,H5_drink,H5_cig,H5_pet,5],
    % the rules
    rule2(H1,H2,H3,H4,H5),
    rule3(H1,H2,H3,H4,H5),
    rule4(H1,H2,H3,H4,H5),
    rule5(H1,H2,H3,H4,H5),
    rule6(H1,H2,H3,H4,H5),
    rule7(H1,H2,H3,H4,H5),
    rule8(H1,H2,H3,H4,H5),
    rule9(H1,H2,H3,H4,H5),
    rule10(H1,H2,H3,H4,H5),
    rule12(H1,H2,H3,H4,H5),
    rule13(H1,H2,H3,H4,H5),
    rule14(H1,H2,H3,H4,H5),
    rule15(H1,H2,H3,H4,H5),
    % for all variable ensure that all values exist
    all_members([white, green, red, blue, yellow], [H1_col,H2_col,H3_col,H4_col,H5_col]),
    all_members([spain, japan, england, ukraine, norway], [H1_nat,H2_nat,H3_nat,H4_nat,H5_nat]),
    all_members([orange, coffee, milk, tea, water], [H1_drink,H2_drink,H3_drink,H4_drink,H5_drink]),
    all_members([luckystrike, parliament, altemgold, chesterfield, kools], [H1_cig,H2_cig,H3_cig,H4_cig,H5_cig]),
    all_members([dog, zebra, snails, horse, fox], [H1_pet,H2_pet,H3_pet,H4_pet,H5_pet]).

If executed, two possible solutions are printed:

['zebra_puzzle.pl'].
solve(H1,H2,H3,H4,H5).

H1 = [yellow, norway, water, kools, zebra, 1],
H2 = [blue, ukraine, tea, chesterfield, horse, 2],
H3 = [red, england, milk, altemgold, snails, 3],
H4 = [white, spain, orange, luckystrike, dog, 4],
H5 = [green, japan, coffee, parliament, fox, 5] ;

H1 = [yellow, norway, water, kools, fox, 1],
H2 = [blue, ukraine, tea, chesterfield, horse, 2],
H3 = [red, england, milk, altemgold, snails, 3],
H4 = [white, spain, orange, luckystrike, dog, 4],
H5 = [green, japan, coffee, parliament, zebra, 5] ;

That’s it, puzzle solved! 😉