/* 

  Railway routes in Picat.

  From Adrian Groza "Modelling Puzzles in First Order Logic"
  See https://www.researchgate.net/publication/374588335_Measuring_reasoning_capabilities_of_ChatGPT
  """
  Puzzle 35. Railway rou

  The graph below represents a simplified railway system, and we want to know how many
  different ways there are of going from A to E, if we never go twice along the same line
  in any journey. From A to B there is route r1. From B to C there are three routes: de-
  noted with r3, r5, and r7. From B to D there are 2 routes: r2 and r9. From C to D there
  are three routes: denoted with r4, r6, and r8. From D to E there is a single route: r10.
  Of course, if there is a route from x to y, then there is a route from y to x. This is a
  very simple proposition, but practically impossible to solve until you have hit on some
  method of recording the routes. You see there are many ways of going, from the short
  route ABDE, taking one of the large loops, up to the long route ABCDBCDBCDE, which
  takes you over every line on the system and can itself be varied in order in many ways.
  How many different ways of going are there? (puzzle 424 from Dudeney (20
  """

  There is 2501 different routes, for example:

    [[a,to,b,1],[b,to,c,3],[c,to,d,4],[d,to,e,10]]
    [[a,to,b,1],[b,to,c,3],[c,to,d,4],[d,to,b,2],[b,to,c,5],[c,to,d,6],[d,to,e,10]]
    [[a,to,b,1],[b,to,c,3],[c,to,d,4],[d,to,b,2],[b,to,c,5],[c,to,d,6],[d,to,b,9],[b,to,c,7],[c,to,d,8],[d,to,e,10]]
    [[a,to,b,1],[b,to,c,3],[c,to,d,4],[d,to,b,2],[b,to,c,5],[c,to,d,6],[d,to,c,8],[c,to,b,7],[b,to,d,9],[d,to,e,10]]


  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

main => go.

go =>
  path(a,e,[],Path),
  println(path=Path),
  fail,
  nl.

% Just count the number of routes
go2 =>
  println(count=count_all(path(a,e,[],_Path))).


% The different routes
table
r(1,a,b).
r(3,b,c). r(5,b,c). r(7,b,c).
r(2,b,d). r(9,b,d).
r(4,c,d). r(6,c,d). r(8,c,d).
r(10,d,e).
% The reverse route
r(N,X,Y) :- r(N,Y,X).

table
path(X,Y,Visited,Path) :-
   Path=[[X,to,Y,N]],
   r(N,X,Y).
path(X,Y,Visited,Path) :-
   Path = [[X,to,Z,N]|PathR],
   r(N,X,Z),
   % Do not repeat the exact same route (neither way)
   not membchk([X,to,Z,N],Visited),
   not membchk([Z,to,X,N],Visited),   
   path(Z,Y,[[X,to,Z,N]|Visited],PathR).