Home > Artificial Intelligence > Who lives on which floor?

Who lives on which floor?

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.

  1. No comments yet.
  1. March 28, 2013 at 11:30

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: