DCG chain from facts, including "not seen before" condition

Question

I am trying to solve the traditional path-finding puzzle using DCG notation. These are some connected numbers, and they make a chain from start to end. You can step between two numbers if there is a connection one way or the other, as normal. For now there is no other route

connected(start, 1).
connected(1, 2).
connected(2, 3).
connected(3, 4).
connected(4, 5).
connected(5, 6).
connected(6, 7).
connected(7, 8).
connected(8, 9).
connected(9, 10).
connected(10, end).

step(X, Y) :-
    connected(X, Y).
step(X, Y) :-
    connected(Y, X).

I have tried a couple of hours of things without getting much past the start connecting to something, something connecting to the end, and the chain in the middle going into an infinite loop, or finding disconnected steps with no chain between them. Currently I have:

path([start,B,C]) --> { step(start, B), step(B, C) }.
path([A,B|C])     --> { step(A, B) }, path([B|C]).
path([B,C,end])   --> { step(B, C), step(C, end) }.

which produces:

?- phrase(path(Ts), Ls)
Ls = [],
Ts = [start, 1, 2]
Ls = [],
Ts = [start, 1, start]
Stack limit (1.9Mb) exceeded
  Stack sizes: local: 1.4Mb, global: 0.3Mb, trail: 67Kb
  Stack depth: 5,534, last-call: 0%, Choice points: 8,270
  Possible non-terminating recursion:
    [5,532] path([length:2|_1460], _1452, [])
    [5,531] path([length:3|_1494], _1486, [])

I think the chain rule is doing 1 -> 2 -> 1 -> 2 -> 1 ... forever. I don't seem to be able to check \+ memberchk(B, C) as the list C isn't defined yet.

With this length constraint, it generates other patterns:

?- length(Ts, _), phrase(path(Ts), Ls).
<snip>
Ts = [7, 8, 9, 8, 9, 10, end]

or like this:

?- length(Ts, _), phrase(path(Ts), Ls), nth0(0, Ts, start).
<snip>
Ts = [start, 1, 2, 1, start, 1, start, 1, start, 1, start]

but not a nice chain from start to end. Can I add a constraint like "the next step must not have been seen before"? How can I gather "everything which has been seen before" when the DCG style seems to be describing "the list which will be seen in future"? (Is it a problem that I am only trying to make a list from facts and not parse anything separate?)

---

I have looked over https://www.metalevel.at/prolog/dcg and tried to use start, ... and ..., end patterns. Adapted this window function into an overlapping window and tried to work with that. Making [step(1,2), step(2,3) lists instead of [1,2,3. Prepending onto the list more like path([C|A,B] as if that might give me a history to check.

Answer 1

There is nothing to gain in using a DCG in this way... the hidden arguments are never used.

:- module(so_path_finding,
          [path//3]).


connected(start, 1).
connected(1, 2).
connected(2, 3).
connected(3, 4).
connected(4, 5).
connected(5, 6).
connected(6, 7).
connected(7, 8).
connected(8, 9).
connected(9, 10).
connected(10, end).

step(X, Y) :-
    connected(X, Y).
step(X, Y) :-
    connected(Y, X).

path(A,B,P) --> path(A,B,[],P).

path(A,B,S,P) --> {step(A,I),\+memberchk(I,S)},path(I,B,[A|S],P).
path(A,B,S,P) --> {step(A,B),\+memberchk(B,S),reverse([B|S],P)}.

Test:

?- phrase(path(start,end,P),[]),writeln(P).
[start,1,2,3,4,5,6,7,8,9,end]
P = [start, 1, 2, 3, 4, 5, 6, 7, 8|...] ;
false.

Then, using the hidden argument(s) at least to get the output path

:- module(so_path_finding,
          [path//2]).


connected(start, 1).
connected(1, 2).
connected(2, 3).
connected(3, 4).
connected(4, 5).
connected(5, 6).
connected(6, 7).
connected(7, 8).
connected(8, 9).
connected(9, 10).
connected(10, end).

step(X, Y) :-
    connected(X, Y).
step(X, Y) :-
    connected(Y, X).

path(A,B) --> path(A,B,[]).

path(A,B,S) --> {step(A,I),\+memberchk(I,S)},[A],path(I,B,[A|S]).
path(A,B,S) --> {step(A,B),\+memberchk(B,S)},[B].

Now we have a different interface:

?- phrase(path(start,end),P),writeln(P).
[start,1,2,3,4,5,6,7,8,9,end]
P = [start, 1, 2, 3, 4, 5, 6, 7, 8|...] ;
false.

edit

After the clarification in OP' comment, here is an attempt (with a graph simplification to reduce the clutter...)

:- module(so_path_finding,
          [path//0]).

connected(start, 1).
connected(1, 2).
connected(2, 3).
connected(3, 4).
connected(4, end).

step(X, Y) :-
    connected(X, Y).
step(X, Y) :-
    connected(Y, X).

path --> {connected(start,S)}, path(S).

% variables naming convention:
% V: vertex, I: intermediate, N:next
path(V) --> [V], {connected(V,end)}.
path(I) --> [I], {step(I,N)}, path(N).

to be called like

?- phrase(path,P).
P = [1, 2, 3, 4] ;
P = [1, 2, 3, 4, end, 4] ;
...

clearly, it's not complete, but maybe is it going in the right direction ? If this is the case, then it's just matter to reintroduce the 'implementation detail' of the seen-so-far-vertices accumulator and a \+memberchk(.,.) to avoid cycles...

continue

so, let's implement this detail:

path --> {connected(start,S)}, path(S,[]).

path(V,S) --> [V], {\+memberchk(V,S), connected(V,end)}.
path(I,S) --> [I], {\+memberchk(I,S), step(I,N)}, path(N,[I|S]).

and now we have

?- phrase(path,P).
P = [1, 2, 3, 4] ;
false.

as expected.