Archive

Posts Tagged ‘fact’

Solving Logic Puzzles in Prolog: Puzzle 3 of 3

December 27, 2015 Leave a comment

In this post we solve another small logic puzzle in Prolog, similar to the previous two logic puzzles (these are available here and here).

The puzzle

There are four researchers: Ainsley, Madeline, Sophie and Theodore. The goal is to find out their sports competition discipline, birth year and research interests (while knowing that each of the mentioned attributes is different amongst them). In order so solve the puzzle, a couple of hints is provided from which the solution can be derived:

  1. The competition for Theodore or Ainsley is javelin.
  2. The researcher interested in hurricane research has relay as sports subject.
  3. Sophie is not the researcher who has relay as sports subject.
  4. Either the researcher who has longjump as sports subject or Theodore was born in 1933 – the other one was born in 1921.
  5. The researcher with relay as sports subject was born before Theodore.
  6. The researcher interested in wildfires was born after the researcher doing longjumps for sports.
  7. Neither Sophie nor Ainsley are researching wildfires.
  8. The researcher interested in earthquakes has either hurdle or javelin as sports interest.
  9. The researcher interested in earthquakes was born in 1933.
  10. Madeline was not born in 1921.

Solving the puzzle in Prolog

In our Prolog implementation we ask for a solution that a) ensures that all sports subjects, research interests and birth years exist once and b) fulfills the rules mentioned above:

% ####################################################################
% Logic puzzle solver.
%
% Read definition to prolog:
%   ['puzzle.pl'].
%
% 2) Ask for solutions:
%   solve(Ainsley, Madeline, Sophie, Theodore).
%
% Rainhard Findling
% 10/2015
% ####################################################################
all_members([H],L2) :- member(H,L2).
all_members([H|T],L2) :- member(H,L2), all_members(T, L2).

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

solve(Ainsley, Madeline, Sophie, Theodore) :-
    All = [Ainsley, Madeline, Sophie, Theodore],
    Ainsley = [Ainsley_Year, Ainsley_Competition, Ainsley_Disaster],
    Madeline = [Madeline_Year, Madeline_Competition, Madeline_Disaster],
    Sophie = [Sophie_Year, Sophie_Competition, Sophie_Disaster],
    Theodore = [Theodore_Year, Theodore_Competition, Theodore_Disaster],
    % we know what all variable must be
    all_members([1920, 1921, 1933, 1973], [Ainsley_Year, Madeline_Year, Sophie_Year, Theodore_Year]),
    all_members([hurdle, relay, javelin, longjump], [Ainsley_Competition, Madeline_Competition, Sophie_Competition, Theodore_Competition]),
    all_members([earthquakes, hurricanes, tornados, wildfires], [Ainsley_Disaster, Madeline_Disaster, Sophie_Disaster, Theodore_Disaster]),
    % c1
    or([Ainsley_Competition = javelin, Theodore_Competition = javelin]),
    % c2
    member([_, relay, hurricanes], All),
    % c3
    not(Sophie_Competition = relay),
    % c4
    member([C4_Year, longjump, _], All),
    or([and([Theodore_Year = 1921, C4_Year = 1933]), and([Theodore_Year = 1933, C4_Year = 1921])]),
    % c5
    member([C5_Year, relay, _], All),
    Theodore_Year > C5_Year,
    % c6
    member([C6_1_Year, longjump, _], All),
    member([C6_2_Year, _, wildfires], All),
    C6_1_Year < C6_2_Year,
    % c7
    not(Sophie_Disaster = wildfires),
    not(Ainsley_Disaster = wildfires),
    % c8
    member([_, C8_competition, earthquakes], All),
    not(C8_competition = hurdle),
    not(C8_competition = javelin),
    % c9
    member([1933, _, earthquakes], All),
    % c10
    not(Madeline_Year = 1921).

Using this implementation, if we ask for a solution, the single possible solution is presented:

['puzzle.prolog'].
% puzzle.prolog compiled 0.00 sec, 13 clauses
true.

?- solve(Ainsley, Madeline, Sophie, Theodore).
Ainsley = [1920, relay, hurricanes],
Madeline = [1973, hurdle, wildfires],
Sophie = [1933, longjump, earthquakes],
Theodore = [1921, javelin, tornados] ;

Solving Logic Puzzles in Prolog: Puzzle 2 of 3

November 29, 2015 1 comment

This post is about solving the 2nd of 3 small logic puzzles in Prolog. The previous post is available here.

The puzzle

Eilen, Ada, Verena and Jenny participated in a painting competition. Find out who painted which subject and who took which place in the competition, using the hints provided. Hints:

    1. Eilen painted a constable and was not last in the competition
    2. Jenny took the third place
    3. The person painting the Monet took the first place
    4. Ada beat the person painting a talyor, and the person painting a Van Gogh beat Vera

Solving the puzzle in Prolog

We just translate the hints into rules that ensure that a) places 1-4 and all mentioned painting subjects exist in our solution and b) the mentioned hints are fulfilled:

% ####################################################################
% Logic puzzle solver.
%
% Read definition to prolog:
% ['puzzle.pl'].
%
% 2) Ask for solutions:
% solve(Eilen, Ada, Vera, Jenny).
%
% Rainhard Findling
% 10/2015
% ####################################################################
all_members([H],L2) :- member(H,L2).
all_members([H|T],L2) :- member(H,L2), all_members(T, L2).

solve(Eilen, Ada, Vera, Jenny) :-
% 4 members
All = [Eilen, Ada, Vera, Jenny],
Eilen = [Eilen_place, Eilen_subject],
Ada = [Ada_place, Ada_subject],
Vera = [Vera_place, Vera_subject],
Jenny = [Jenny_place, Jenny_subject],
% we know max place is 4th
all_members([1,2,3,4], [Eilen_place, Ada_place, Vera_place, Jenny_place]),
% we know existing paintings
all_members([constable,taylor,fangogh,monet], [Eilen_subject, Ada_subject, Vera_subject, Jenny_subject]),
% #3 1st was monet
member([1, monet], All),
% #2 Jenny got third
member([3, Jenny_subject], All),
% #1 Eilen painted a constable and was not last
member([Eilen_place, constable], All),
4 > Eilen_place,
% #4 ada beat the taylor painter...
member([Ada_place, Ada_subject], All),
member([H2_taylor_place, taylor], All),
Ada_place < H2_taylor_place, 
% #4 ...and the van gogh painter beat vera member([H4_fangogh_place, fangogh], All), member([Vera_place, Vera_subject], All), Vera_place > H4_fangogh_place.

If we ask for a solution, the single valid solution is presented:

?- solve(Eilen, Ada, Vera, Jenny).
Eilen = [2, constable],
Ada = [1, monet],
Vera = [4, taylor],
Jenny = [3, fangogh] ;

And again, that’s it – problem solved!

Solving Logic Puzzles in Prolog: Puzzle 1 of 3

October 31, 2015 6 comments

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

Who has to attend the party?

March 28, 2013 Leave a comment

As a follow-up to Who lives on which floor?, this is another small problem perfectly fitted for a solution written in Prolog (it’s actually on of the many exercises from the 2. semester Algorithms and Datastructures course, of the Mobile Computing Bachelor program at our university):

Instructions

Uncle Oscar throws one of his boring parties again. Adam, Betty, Camilla and Daisy are invited and argue about who has to go this time — therefore they agree on the following:

  • At least one of them has to go to the party, otherwise Oscar will be aggrieved.
  • Adam does not go together with Daisy.
  • If Betty goes, Camilla has to go with her.
  • If Adam and Camilla go, Betty wants to stay at home.
  • If Adam stays at home, then at least one of the girls (Camilla and Daisy) has to go.

Write a program that gives all possible combinations of who is going to Oscars party.

Solution

All we have to tell Prolog is what valid states for “going” are: either “is going” (true) or “is not going” (false), and that a valid solution contains 4 of those states which don’t violate the points stated above. Those rules are easily written in the form: “if condition matches, this is not a valid combination”.

Prolog knowledge database:

% what are valid states for going?
goes(true).
goes(false).

% rule1 input: A,B,C,D
rule1(false,false,false,false) :- !,fail.
rule1(_,_,_,_).
% rule2 input: A,D
rule2(true,true) :- !,fail.
rule2(_,_) :- !,true.
% rule3 input: B,C
rule3(true,false) :- !,fail.
rule3(_,_).
% rule4 input: A,C,B
rule4(true,true,true) :- !,fail.
rule4(_,_,_).
% rule5 input: A,C,D
rule5(false,false,false) :- !,fail.
rule5(_,_,_).

Prolog query to ask for valid solutions:

goes(A),goes(B),goes(C),goes(D),rule1(A,B,C,D),rule2(A,D),rule3(B,C),rule4(A,C,B),rule5(A,C,D).

And again that’s it, Prolog will present you the 7 possible solutions straight away 😉

Who lives on which floor?

March 24, 2013 1 comment

You might know logic puzzles such as the zebra puzzle/Einstein puzzle: they are perfect examples of what can easily be solved in the logic programming language Prolog. Prolog in a nutshell: you can state a) facts (which represent knowledge about the world) and b) rules (to derive new facts from current facts), and you can ask with queries a) if statements without variables are true, and b) which values the variables in the query have to take to make the statement true. Prolog will search completely on it’s own for a solution using backtracking (working from our goal backwards towards the facts we currently know) — so you don’t actually write a program to solve your problem, but you only state what you know and what a valid solution is. To start with a problem easier than the zebra puzzle, you can try out the following problem:

Instructions

There is a house with 6 floors (floor 1 to 6) with one person (represented by upper-case letters) living on each floor. We know the following about who lives on which floor:

  • E lives on floor 4.
  • D lives somewhere below J.
  • J does not live directly above E.
  • D lives directly below A.
  • H lives above P.
  • P does not live somewhere below D.
  • J lives somewhere above P.

Who lives on which floor?

Solution

All we have to tell Prolog to solve this problem is:

  • There are 6 floors: floor(1) to floor(6).
  • What a valid solution looks like: there are the floors E,D,J,A,P,H with on each the corresponding person living on it, so that the relations between E,D,J,A,P,H stated above are true.

Write down this knowledge in a knowledge database file (floors.pl), as shown below:

%% commands to start:
%  use_module(library(bounds)).
% ['floors.pl'].
%  once((house(E,D,J,H,P,A))).

floor(1).
floor(2).
floor(3).
floor(4).
floor(5).
floor(6).

house(E,D,J,H,P,A) :-
floor(E),
floor(D),
floor(J),
floor(H),
floor(P),
floor(A),
E=:=4,
D<J, J-E=:=1, A-D=:=1, H>P,
P>D,
J>P,
all_different([E,D,J,H,P,A]).

Now you can load the required library for all_different: “use_module(library(bounds)).”, then load this file in the Prolog shell of your choice and finally ask for a valid solution with a single query. That’s all, Prolog will present you the solution then 😉

use_module(library(bounds)).
['floors.pl'].
once((house(E,D,J,H,P,A))).

And just for reasons of completeness: on Ubuntu (12.04) you can easily install the interactive Prolog shell with

sudo apt-get install swi-prolog

and start it with

swipl

to try out Prolog yourself.