You're an adventurer, and you've heard that there is a vast gold treasure hidden inside a cave. Many people before you have tried to find it, but to no avail. The cave is a labyrinth of galleries connecting different rooms in which there are dangerous beings, like monsters and robbers. In your favor is the fact that the treasure is all in one room. Which route should you follow to get to the treasure and escape unhurt with it? Consider the following map of the cave:

Figure 16.2: The Labyrinth of Galleries

You can construct a Visual Prolog representation of the map to help you find a safe route. Each gallery is described by a fact. The predicates go and route give rules. Give the program the goal

    go(entry, exit).

The answer will consist of a list of the rooms you should visit to capture the treasure and return safely with it.

An important design feature of this program is that the rooms already visited are collected in a catalog. This happens thanks to the route predicate, which is defined recursively. If you're standing in the exit room, the third parameter in the route predicate will be a list of the rooms you've already visited. If the gold_treasure room is a member of this list, you'll have achieved your aim. Otherwise, the list of rooms visited is enlarged with Nextroom, provided Nextroom is not one of the dangerous rooms and has not been visited before.

/* Program ch16e03.pro */

DOMAINS

    room     =  symbol

    roomlist = room*

PREDICATES

    nondeterm gallery(room,room)

        % There is a gallery between two rooms

        % Necessary because it does not matter

        % which direction you go along a gallery

    nondeterm neighborroom(room,room)

    avoid(roomlist)

    nondeterm go(room,room)

    nondeterm route(room,room,roomlist)

        % This is the route to be followed.

        % roomlist consists of a list of rooms already visited.

    nondeterm member(room,roomlist)

CLAUSES

    gallery(entry,monsters).                   gallery(entry,fountain).

    gallery(fountain,hell).                       gallery(fountain,food).

    gallery(exit,gold_treasure).               gallery(fountain,mermaid).

    gallery(robbers,gold_treasure).          gallery(fountain,robbers).

    gallery(food,gold_treasure).              gallery(mermaid,exit).

    gallery(monsters,gold_treasure).       gallery(gold_treasure,exit).

 

    neighborroom(X,Y):-gallery(Y,X).

    avoid([monsters,robbers]).

 

    go(_,_).

 

        member(gold_treasure,VisitedRooms),

        write(VisitedRooms),nl.

    route(Room,Way_out,VisitedRooms):-

        neighborroom(Room,Nextroom),

        avoid(DangerousRooms),

        not(member(NextRoom,DangerousRooms)),

        not(member(NextRoom,VisitedRooms)),

        route(NextRoom,Way_out,[NextRoom|VisitedRooms]).

    member(X,[X|_]).

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

After verifying that the program does find a solution to the goal

    go(entry, exit).

you might want to try adding some more galleries, for example,

    gallery(mermaid, gold_treasure).

Or you can add some additional nasty things to avoid.

Even though--once you've made these additions--there is more than one possible solution to the problem, your program will only come up with one solution. To obtain all the solutions, you must make Visual Prolog backtrack as soon as it has found one solution. You can do this by adding the fail predicate to the first rule for route:

    route(Room, Room, VisitedRooms) :-
        member(gold_treasure, VisitedRooms),
        write(VisitedRooms), nl, fail.

To get a neater output, you could use a list-writing predicate, write_a_list, to write the list of names without the containing square brackets ([ and ]) or the separating commas. However, the rooms you've visited are collected in the VisitedRooms list in reverse order (exit first and entry last). Therefore, you need to reverse the list or make the list-writing predicate write the list in reverse.