My Prolog program makes a list, but I can't figure out how to make it stop after 2 entries

user_14671252 0
Viewed 74

For some practise; I'm trying to create a program that simulates a maze and shows every possible route between entry and exit. The code creates one of the lists, however it doesn't show both and doesn't stop when it's found them (route 1: entry,a,b,e,f,exit and route 2: entry,a,b,c,d,e,f,exit), and continuously loops into bigger and bigger routes.

% length(X, _), route(entry,exit, X).

%Facts, indicating an adjacent link between one room and another.
link(entry, a).
link(a, b).
link(b, c).
link(c, d).
link(d, e).

link(b, e).
link(e, f).
link(f, c).

link(f, exit).

%Searches for the path in an increasing order of length 'route'.
route(X, Y, [X, Y]) :- link(X,Y).
route(X, Y, [X | TY]) :- link(X, T), route(T, Y, TY).

Example from console:

| ?- route(entry, exit, A). A = [entry,a,b,c,d,e,f,exit] ;

A = [entry,a,b,c,d,e,f,c,d,e,f,exit] ;

A = [entry,a,b,c,d,e,f,c,d,e,f,c,d,e,f,exit] ;

A = [entry,a,b,c,d,e,f,c,d,e,f,c,d,e,f,c,d,e,f,exit]

Can anyone help me?

prolog
2 Answers

The simplest way to make this iterative deepening path search stop from looking for further successes after the first one is to cut at the end of the goal:

?- length(X, _), route(entry,exit, X), !.  
X = [entry,a,b,e,f,exit].

Once success brings Prolog's "finger" past the !, any attempt to redo and move the finger back leftwards is disallowed. So Prolog stops after the first success.

For multiple solutions: hopefully there is something like library(solution_sequences) around.

There we have limit(+Count,:Goal):

?- limit(2,route(entry, exit, A)).
A = [entry,a,b,c,d,e,f,exit] ;
A = [entry,a,b,c,d,e,f,c,d,e,f,exit].

The source code for limit, which is written in Prolog. It uses state-changing predicates, but can it be written without those?

user_8844630

1. First path predicate is the base case.

2. Second path predicate searches all possible routes for the given Start and End Node.

link(entry, a).
link(a, b).
link(b, c).
link(c, d).
link(d, e).
link(b, e).
link(e, f).
%link(f, c).
link(f, exit).

path(Node,Node,[Node]):-!.
path(StartN,EndN,[StartN|List]):-
    link(StartN,NextN),
    path(NextN,EndN,List).

Example:

?-path(entry,exit,Route).
Route = [entry, a, b, c, d, e, f, exit]
Route = [entry, a, b, e, f, exit]
    
?-path(entry,a,Route).
Route = [entry, a]
    
?-path(entry,b,Route).
Route = [entry, a, b]
    
?-path(entry,c,Route).
Route = [entry, a, b, c]
false

?-path(entry,d,Route).
Route = [entry, a, b, c, d]
false

?-path(entry,e,Route).
Route = [entry, a, b, c, d, e]
Route = [entry, a, b, e]

?-path(entry,f,Route).
Route = [entry, a, b, c, d, e, f]
Route = [entry, a, b, e, f]

Note: I had to comment link(f,c) to get the correct route for exit or else it'll give you stack limit exceeded, I'm not sure why.

user_14200560
Related