% labyrinthe.pro
%
% Searches a path through a numerical labyrinth.
% Passage from one cell to another is only allowed
% if they have a common divisor > 1.
%
% Start searching simply with ?- start.
%
% Michael Vorburger, 04/20/97
%



% -----------------------------------------------------------------------------
% Prolog rules for finding the biggest common denominator
% -----------------------------------------------------------------------------

pgcd(P,0,P) :- !.                   % The CUT here is essential!
pgcd(P,Q,X) :- P<0, pgcd(-P,Q,X).
pgcd(P,Q,X) :- Q<0, pgcd(P,-Q,X).
pgcd(P,Q,X) :- P<Q, pgcd(Q,P,X). 
pgcd(P,Q,X) :- M is P mod Q, pgcd(Q,M,X).

% -----------------------------------------------------------------------------




% -----------------------------------------------------------------------------
%  Rule for finding the nextcell
%
% NOTES
%   - PD = previous direction (down, up, right, left)
%   - It is not neccessairy to perfom checks like X<5, Y>1 because point()
%      simply fails if the given coordinate is out of bound.
% -----------------------------------------------------------------------------

nextcell(X,Y,_,Cost) :- point(X,Y,13), X=\=1, Y=\=1,
                        Cost2 is 2*Cost, write('Total cost='), write(Cost2), nl,
                        ! .

nextcell(X,Y,PD,Cost) :- PD \= up, point(X,Y,I), NX is X+1, point(NX,Y,J),
                         pgcd(I,J,PGCD), PGCD>1, 
                         NewCost is Cost+PGCD,
                         nextcell(NX,Y,down,NewCost),
                         write('went down to cell '), write(J),
                         write(', paid '), write(PGCD), nl.
   
nextcell(X,Y,PD,Cost) :- PD \= down, point(X,Y,I), NX is X-1, point(NX,Y,J),
                         pgcd(I,J,PGCD), PGCD>1, 
                         NewCost is Cost+PGCD,
                         nextcell(NX,Y,up,NewCost),
                         write('went up to cell '), write(J), 
                         write(', paid '), write(PGCD), nl.

nextcell(X,Y,PD,Cost) :- PD \= left, point(X,Y,I), NY is Y+1, point(X,NY,J),
                         pgcd(I,J,PGCD), PGCD>1, 
                         NewCost is Cost+PGCD,
                         nextcell(X,NY,right,NewCost),
                         write('went right to cell '), write(J), 
                         write(', paid '), write(PGCD), nl.

nextcell(X,Y,PD,Cost) :- PD \= right, point(X,Y,I), NY is Y-1, point(X,NY,J), 
                         pgcd(I,J,PGCD), PGCD>1, 
                         NewCost is Cost+PGCD,
                         nextcell(X,NY,left,NewCost),
                         write('went left to cell '), write(J), 
                         write(', paid '), write(PGCD), nl.


start :- nextcell(1,1,nothing,0).          % That's just a gadget.

% -----------------------------------------------------------------------------




% -----------------------------------------------------------------------------
% Fact database of the big (13x13) labyrinthe
% Format: point(row,column,value)	
%
% Generated by text-labyrinthe-2-prolog.c
% -----------------------------------------------------------------------------

  point(1,1,13).
 point(1,2,26).
 point(1,3,91).
 point(1,4,35).
 point(1,5,95).
 point(1,6,57).
 point(1,7,33).
 point(1,8,55).
 point(1,9,45).
 point(1,10,25).
 point(1,11,85).
 point(1,12,65).
 point(1,13,70).
 point(2,1,39).
 point(2,2,17).
 point(2,3,68).
 point(2,4,27).
 point(2,5,85).
 point(2,6,19).
 point(2,7,38).
 point(2,8,69).
 point(2,9,23).
 point(2,10,68).
 point(2,11,81).
 point(2,12,57).
 point(2,13,77).
 point(3,1,15).
 point(3,2,85).
 point(3,3,44).
 point(3,4,21).
 point(3,5,17).
 point(3,6,68).
 point(3,7,51).
 point(3,8,81).
 point(3,9,92).
 point(3,10,85).
 point(3,11,25).
 point(3,12,95).
 point(3,13,44).
 point(4,1,64).
 point(4,2,76).
 point(4,3,77).
 point(4,4,42).
 point(4,5,88).
 point(4,6,55).
 point(4,7,40).
 point(4,8,64).
 point(4,9,69).
 point(4,10,17).
 point(4,11,51).
 point(4,12,33).
 point(4,13,88).
 point(5,1,82).
 point(5,2,19).
 point(5,3,95).
 point(5,4,65).
 point(5,5,39).
 point(5,6,26).
 point(5,7,91).
 point(5,8,38).
 point(5,9,27).
 point(5,10,57).
 point(5,11,95).
 point(5,12,80).
 point(5,13,11).
 point(6,1,27).
 point(6,2,21).
 point(6,3,28).
 point(6,4,77).
 point(6,5,87).
 point(6,6,85).
 point(6,7,78).
 point(6,8,95).
 point(6,9,55).
 point(6,10,26).
 point(6,11,16).
 point(6,12,65).
 point(6,13,22).
 point(7,1,69).
 point(7,2,47).
 point(7,3,94).
 point(7,4,35).
 point(7,5,45).
 point(7,6,25).
 point(7,7,13).
 point(7,8,78).
 point(7,9,11).
 point(7,10,39).
 point(7,11,10).
 point(7,12,30).
 point(7,13,27).
 point(8,1,23).
 point(8,2,92).
 point(8,3,77).
 point(8,4,66).
 point(8,5,58).
 point(8,6,33).
 point(8,7,77).
 point(8,8,49).
 point(8,9,91).
 point(8,10,51).
 point(8,11,25).
 point(8,12,98).
 point(8,13,57).
 point(9,1,75).
 point(9,2,32).
 point(9,3,49).
 point(9,4,33).
 point(9,5,29).
 point(9,6,11).
 point(9,7,19).
 point(9,8,76).
 point(9,9,77).
 point(9,10,85).
 point(9,11,91).
 point(9,12,49).
 point(9,13,95).
 point(10,1,55).
 point(10,2,98).
 point(10,3,85).
 point(10,4,90).
 point(10,5,64).
 point(10,6,88).
 point(10,7,57).
 point(10,8,81).
 point(10,9,21).
 point(10,10,50).
 point(10,11,77).
 point(10,12,86).
 point(10,13,38).
 point(11,1,10).
 point(11,2,35).
 point(11,3,68).
 point(11,4,17).
 point(11,5,51).
 point(11,6,95).
 point(11,7,56).
 point(11,8,98).
 point(11,9,91).
 point(11,10,95).
 point(11,11,99).
 point(11,12,81).
 point(11,13,39).
 point(12,1,22).
 point(12,2,49).
 point(12,3,77).
 point(12,4,44).
 point(12,5,27).
 point(12,6,35).
 point(12,7,26).
 point(12,8,49).
 point(12,9,96).
 point(12,10,34).
 point(12,11,85).
 point(12,12,68).
 point(12,13,57).
 point(13,1,99).
 point(13,2,81).
 point(13,3,45).
 point(13,4,65).
 point(13,5,78).
 point(13,6,49).
 point(13,7,70).
 point(13,8,55).
 point(13,9,33).
 point(13,10,77).
 point(13,11,25).
 point(13,12,55).
 point(13,13,95).
 
% -----------------------------------------------------------------------------