Prolog Path Finding

4
votes

If I have the following predicate door, which declare that there is a door between the two rooms:

door(office, hall).
door(kitchen, office).
door(hall, "dining room").
door(kitchen, cellar).
door("dining room", kitchen).

And the predicate doorstate which declares the state of a door:

doorstate(hall, office, closed).
doorstate(hall, "dining room", opened).
doorstate("dining room", kitchen, opened).
doorstate(kitchen, office, opened).
doorstate(kitchen, cellar, opened).

There is a pathway between two rooms if all of the doors between them are open.

How can I write a rule to discover if there is such a pathway between two rooms?

4
prolog
If I had editing powers I would put single quotes around "dining room". Otherwise it's a syntax error. Also, I would put a space after each comma, otherwise it's inconsistent and unreadable. – Kaarel
Fixed the syntax. Got over keen and tweaked the language, too. – Matthew Schinckel
@Matthew: "dining room" is a (serialization of a) list, 'dining room' would be an atom. So, I would change "dining room" to 'dining room', because e.g. kitchen is typewise equivalent to 'kitchen'. ;) – Kaarel

4 Answers

5
votes

The abject horror of prolog returns too quickly.

wayopen(Room1,Room2) :- doorstate(Room1, Room2, opened).
wayopen(Room1,Room2) :- doorstate(Room1, RoomX, opened), wayopen(RoomX,Room2).

So I'm not just doing your homework for you, here's how to understand it:

  • The way is open between two rooms if they are joined by a door and the door is open.
  • The way is open between two rooms if the first way has a door open to another room, and there is a way from the other room to the second room.

Note that these rules can only go through doors in one direction. Your homework is to make it work in both directions.

Where can we get to from the hall?

?- wayopen(hall, X).
X = diningroom ;
X = kitchen ;
X = office ;
X = cellar ;
false.

Here are all the rooms you can get from and to:

?- wayopen(Room1,Room2).
Room1 = hall,
Room2 = diningroom ;
Room1 = diningroom,
Room2 = kitchen ;
Room1 = kitchen,
Room2 = office ;
Room1 = kitchen,
Room2 = cellar ;
Room1 = hall,
Room2 = kitchen ;
Room1 = hall,
Room2 = office ;
Room1 = hall,
Room2 = cellar ;
Room1 = diningroom,
Room2 = office ;
Room1 = diningroom,
Room2 = cellar ;
false.
1
votes

You need to describe a relation (exists_way/2) that is symmetric and transitive.

% Base cases
exists_way_(hall, 'dining room').
exists_way_('dining room', kitchen).
exists_way_(kitchen, office).
exists_way_(kitchen, cellar).

% Symmetric
exists_way(R1, R2) :- exists_way_(R1, R2) ; exists_way_(R2, R1).

% Transitive
exists_way(R1, R2) :-
    exists_way_(R1, R3),
    exists_way(R3, R2).

This code over-generates solutions though. So you would need to filter out the duplicates later.

1
votes

You need to describe a relation (exists_way/2) that is symmetric and transitive. In a Prolog that supports tabling (such as XSB), you can express these relations in a very natural way, i.e. as they are expressed in math books.

:- table exists_way/2.

% Open doors
exists_way(hall, 'dining room').
exists_way('dining room', kitchen).
exists_way(kitchen, office).
exists_way(kitchen, cellar).

% Symmetry
exists_way(R1, R2) :-
    exists_way(R2, R1).

% Transitivity
exists_way(R1, R2) :-
    exists_way(R1, R3),
    exists_way(R3, R2).

In this case, the query exists_way(R1, R2) delivers exactly 25 unique solutions.

-1
votes

In the spirit of learning: This is the same problem as the grandparent problem you probably did in the first week of your prolog course.

It turns out that quite a lot of the stuff you will do in prolog will be quite similar in structure. So make sure you grasp the ideas about recursive predicates, and how the order in which the clauses must go, for correction and performance.

For example, you should avoid non-tail-recursion where possible.