CODEWITHSUNDEEP
prolog
Tania
Tania

Reputation:

Prolog Path Finding

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?

Upvotes: 4

Views: 5655

Answers (4)

Matthew Schinckel
Matthew Schinckel

Reputation: 35649

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.

Upvotes: -1

Kaarel
Kaarel

Reputation: 10672

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.

Upvotes: 1

Kaarel
Kaarel

Reputation: 10672

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.

Upvotes: 1

geofftnz
geofftnz

Reputation: 10102

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.

Upvotes: 5

Related Questions