Home > Artificial Intelligence > Who has to attend the party?

Who has to attend the party?

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 😉

  1. No comments yet.
  1. No trackbacks yet.

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: