Jason Niklas' Prolog Project

From www.norsemathology.org

Jump to: navigation, search

Contents

Description of the Problem

For my project, I decided to pick Corry Dringenburg and Alex Povkov's Prolog Project, which they were not able to successfully implement. This problem illustrates the problem solving capabilities of Prolog. Given a problem, we can plug the clues and the unknowns into Prolog, and it will piece all of the factors together to produce the solution.

The problem reads:

Image:Smoker_problem.jpg

Description of the Database

FACT - There are 4 men:

  • Mr. Crumpet
  • Mr. Tray
  • Mr. Small
  • Mr. Lighter

FACT - There are 4 seats (Left-to-Right):

  • Seat 1
  • Seat 2
  • Seat 3
  • Seat 4

FACT - There are 4 tobacco choices:

  • Pipe
  • Cigar
  • Cigarette
  • None

The relationships:

  • Mr. Crumpet does not smoke cigarettes.
  • Neither Mr. Crumpet nor Mr. Tray will sit in the third position.
  • Mr. Crumpet will not smoke cigars.
  • The cigar smoker is sitting on the end.
  • The pipe smoker will sit to the right of Mr. Lighter.
  • The cigarette smoker will sit to the immediate left of Mr. Small.
  • The cigarette smoker is just to the right of the cigar smoker.

How It Works

For my implementation, I chose to encapsulate the seats into a Prolog list data structure. Lists are the basic data structure used in logic (and functional) programming. Lists are a recursive data structure so recursion occurs naturally in the definitions of various list operations.

Lists contain elements, so the first step was to define what an element looks like.

% List element: seat ( Position, Name, Smokes )
%    Position: Seat number
%    Name    : Name of person in that seat
%    Smokes  : What that person smokes

Once I have the elements defined, I define the list to contain four(4) seats. The underscore in the definitions denotes an anonymous variable (or don`t care) whose value in immaterial to the definition. The member relation can be used to derive other useful relations.

seats([seat(1,_,_),seat(2,_,_),seat(3,_,_),seat(4,_,_)]).

The list of seats is instantiated and named during the first instruction of program execution.

seats(Seats),

The people and what they smoke are then added as members of the list of seats. Again, note the use of the underscore in the definitions. This will allow Prolog to derive other relations.

%Add people to the list
member(seat(_,crumpet,_),Seats),
member(seat(_,tray,_),Seats),
member(seat(_,lighter,_),Seats),
member(seat(_,small,_),Seats),
%Add smokes to the list
member(seat(_,_,none),Seats),
member(seat(_,_,cigar),Seats),
member(seat(_,_,pipe),Seats),
member(seat(_,_,cigarette),Seats),

The member() predicate accepts an element and a list for its formal parameters. It adds the specified element to the front of the specified list.

member(X,[X|_]).
member(X,[_|Y]) :- member(X,Y).

One of the clues states that the person that smokes the pipe sits to the right of Mr. Lighter. We also know that the person that smokes the cigarette sits to the right of the person that smokes the cigar.

right_of(seat(_,_,pipe),seat(_,lighter,_),Seats),
right_of(seat(_,_,cigarette),seat(_,_,cigar),Seats),

The right_of() predicate accepts two elements and the list for its formal parameters. It returns TRUE if the first element is located to the right of the second element in the specified list. The anonymous variables allow similar elements containing different properties to be compared.

right_of(A,B,[B,A|_]).
right_of(A,B,[_|Y]) :- right_of(A,B,Y).

Another clue indicates that the person that smokes the cigarette sits to the left of the Mr. Small.

left_of(seat(_,_,cigarette),seat(_,small,_),Seats),

The left_of() predicate accepts two elements and the list for its formal parameters. It returns TRUE if the first element is located to the left of the second element in the specified list. The anonymous variables allow similar elements containing different properties to be compared.

left_of(A,B,[A,B|_]).
left_of(A,B,[_|Y]) :- left_of(A,B,Y).

Lastly, we are also told that the cigar smoker sits on one of the ends of the four seats; the cigar smoker will have seat position #1 or seat position #4.

on_end(seat(_,_,cigar),Seats),

The on_end() predicate accepts an element and the list for its formal parameters. It returns TRUE if the specified element is located in the first or last position of the specified list.

on_end(A,[A,_,_,_]).
on_end(A,[_,_,_,A]).
on_end(A,[_|Y]) :- on_end(A,Y).

The print_out() predicate is used to display the specified list, which after Prolog runs its query, should only display one possible combination. If everything is coded correctly, this information should illustrate who sits where, and what each is smoking.

print_out(Seats).
print_out([A|B]) :- !,
write(A),nl,
print_out(B),print_out([]).

The Code

The code as a prolog file (ready for compilation)


%%smoker.pl
% Author:   Jason Niklas
% Email:    niklasj1@nku.edu
% Version:  Last Update 09_23_2010
%%	

%%
% List: seats[]
% List element: seat ( Position, Name, Smokes )
%    Position: Seat number
%    Name    : Name of person in that seat
%    Smokes  : What that person smokes
%%


mightSmoke(crumpet,pipe).
mightSmoke(crumpet,none).

main :-
%Instantiate the list of seats
seats(Seats),

%Add people to the list
member(seat(_,crumpet,_),Seats),
member(seat(_,tray,_),Seats),
member(seat(_,lighter,_),Seats),
member(seat(_,small,_),Seats),

%Add smokes to the list
member(seat(_,_,none),Seats),
member(seat(_,_,cigar),Seats),
member(seat(_,_,pipe),Seats),
member(seat(_,_,cigarette),Seats),

%Add seat numbers to the list
%member(seat(1,_,_),Seats),
%member(seat(2,_,_),Seats),
%member(seat(3,_,_),Seats),
%member(seat(4,_,_),Seats),

right_of(seat(_,_,pipe),seat(_,lighter,_),Seats),
right_of(seat(_,_,cigarette),seat(_,_,cigar),Seats),

left_of(seat(_,_,cigarette),seat(_,small,_),Seats),

right_next(seat(_,crumpet,_),seat(_,_,cigar),Seats),

%not_smoke(seat(_,crumpet_),seat(_,_,cigar),Seats),



not_sit_third(seat(_,crumpet,_),Seats),
not_sit_third(seat(_,tray,_),Seats),

on_end(seat(_,_,cigar),Seats),

print_out(Seats).


seats([
seat(1,_,_),
seat(2,_,_),
seat(3,_,_),
seat(4,_,_)]).

right_next(A,B,[B,A,_,_]).
right_next(A,B,[B,_,A,_]).
right_next(A,B,[B,_,_,A]).
right_next(A,B,[_,B,A,_]).
right_next(A,B,[_,B,_,A]).
right_next(A,B,[_,_,B,A]).
right_next(A,B,[_|Y]) :- right_next(A,B,Y).

right_of(A,B,[B,A|_]).
right_of(A,B,[_|Y]) :- right_of(A,B,Y).

left_of(A,B,[A,B|_]).
left_of(A,B,[_|Y]) :- left_of(A,B,Y).

on_end(A,[A,_,_,_]).
on_end(A,[_,_,_,A]).
on_end(A,[_|Y]) :- on_end(A,Y).

next(A,B,[A,B|_]).
next(A,B,[B,A|_]).
next(A,B,[_|Y]) :- next(A,B,Y).

sit_third(A,[_,_,A,_]).
not_sit_third(A,[_|Y]) :- not(sit_third(A,Y)).

smoke(A,B,[(A and B)|_]).
not_smoke(A,B,[_|Y]) :- not(smoke(A,B,Y)). 


member(X,[X|_]).
member(X,[_|Y]) :- member(X,Y).

print_out([A|B]) :- !,
write(A),nl,
print_out(B),print_out([]).

Example Output

Image:Smoker_output.jpg

References

[1]http://www.brain-fun.com/Brain-Teasers/SmokersRiddle.php

[2]http://norsemathology.org/wiki/index.php?title=Corry_Dringenburg_and_Alex_Povkov's_Prolog_Project

Personal tools