2

Hi so before I get told that this question has been asked many times, I have looked through a bunch of questions but none of them relate to Prolog. Which is what I'm having difficulty with.

I am trying to find the shortest path between two points on a chess board. The code I have is specifically for a knight. This is my code so far: 

move1( (X1,Y1), (X2,Y2) ) :- up1( X1, X2 ), up2( Y1, Y2 ).
move1( (X1,Y1), (X2,Y2) ) :- up2( X1, X2 ), up1( Y1, Y2 ).
move1( (X1,Y1), (X2,Y2) ) :- up1( X1, X2 ), down2( Y1, Y2 ).
move1( (X1,Y1), (X2,Y2) ) :- up2( X1, X2 ), down1( Y1, Y2 ).
move1( (X1,Y1), (X2,Y2) ) :- down1( X1, X2 ), up2( Y1, Y2 ).
move1( (X1,Y1), (X2,Y2) ) :- down2( X1, X2 ), up1( Y1, Y2 ).
move1( (X1,Y1), (X2,Y2) ) :- down1( X1, X2 ), down2( Y1, Y2 ).
move1( (X1,Y1), (X2,Y2) ) :- down2( X1, X2 ), down1( Y1, Y2 ).

up1( U, V ) :- successor( U, V ).
up2( U, W ) :- successor( U, V ), successor( V, W ).
down1( U, V ) :- up1( V, U ).
down2( U, V ) :- up2( V, U ).

successor( 1, 2 ).
successor( 2, 3 ).
successor( 3, 4 ).
successor( 4, 5 ).

edge((X1,Y1) , (X2,Y2)) :- move1( (X1,Y1), (X2,Y2) ).

path((X1,Y1), (X2,Y2),N,[(X1,Y1), (X2,Y2)]) :- N > 0, edge((X1,Y1), (X2,Y2)).
path((X1,Y1), (X3,Y3),N,[(X1,Y1)|P1]) :- N > 0, N1 is N-1, path((X2,Y2), (X3,Y3),N1,P1), edge((X1,Y1), (X2,Y2)), nonmember((X1,Y1),P1).

shortest((X1,Y1),(X2,Y2),P) :- path((X1,Y1),(X2,Y2),24,P),!.

visit((X1,Y1),P,N) :-  path((X1,Y1), (X2,Y2),N,P),N2 is N+1,len(P,N2).

len([],0).
len([_|T],N)  :-  len(T,X),  N is X+1. 

nonmember(X,[]).
nonmember(X,[U|Y]) :- X \= U, nonmember(X,Y).

As you can see, I only find the first path rather than the shortest path. I'm not sure how to code in prolog and figure out a way to get all the shortest paths. I was thinking about making a list of all the possible paths then going through and finding the shortest but I cannot seem to write the code. 

findAll((X1,Y1),(X2,Y2),P,L) :- path((X1,Y1),(X2,Y2),24,P),length(P,L).

Gives me the length of every path but I'm not sure what to do with it. Any help in how to code in Prolog to find the shortest path would be very helpful and is what I am looking for.

false
  • 10,264
  • 13
  • 101
  • 209
helpCompSci
  • 21
  • 2

1 Answers1

0

To follow your approach which seem to enumerate all paths and find the minimum, I would go with the aggregate library.

But first, I would suggest some cleanup of your code as I'm not sure it would work correctly that way (but I have just checked very quickly).

In particular, you want to arrive to a predicate path((X1, Y1),(X2, Y2),Path) that would allow for an enumeration of all the paths (if you retry it multiple times) and then stops. Yours seem to loop indefinitely once all paths have been exhausted. You can find some inpiration on how to enumerate all non looping paths here.

Once that is fixed, you can use aggregate/3 in the following way:

:-use_module(library(aggregate)).    

find_min(Start, End, Path) :-
    aggregate(
        min(Length, Path),
        (path(Start, End, Path), length(Path, Length)),
        min(_,P)
     ).

find_min(Start, End, Path) will then allow you to enumerate all shortest paths from one cell to another. Note that there may be multiple shortest path from Start to End; this will return all shortest paths, not just one.

Another possible solution would be to implement Djikstra's shortest path algorithm, which is likely be much more efficient than enumerating all the paths and finding the minimum like we are doing here. But that would be a totally different approach.

EDIT: With a small board 4x4 or 5x5 then the enumerating all paths and finding the min approach may work, but on a 8x8 board the complexity will become unmangeable. Here, the best way would be to change your approach and implement, e.g., Djikstra's algorithm.

Community
  • 1
  • 1
Regis Alenda
  • 479
  • 3
  • 6
  • Could you try with `\+ memberchk` instead of your `nonmember` predicate? – Regis Alenda Dec 18 '16 at 21:28
  • yeah sorry I deleted my comments because I sort of figured it out, if I call nonmember last then it works as P1 now has values in it. Also, I tried to use the code that you gave above, and I can't seem to get it work. Using the shortest path call of: shortest( (1,1), (4,4) , P ). It just keeps looping. – helpCompSci Dec 18 '16 at 21:31
  • With my code I noticed that when I call shortest path without the cut, it starts with the shortest path and continues to list longer and longer paths. Is it safe to say that my code finds the shortest path first then continues on to find the longer ones? – helpCompSci Dec 18 '16 at 21:34
  • Might be the case, yes. The first clause of your path predicate checks for a path of length 1; the second one checks for a path of length n+1. So you are incrementally building paths of increasing length. – Regis Alenda Dec 18 '16 at 23:00
  • This is also why it does not terminate: the recursive call to path is the first thing you do; you check that the path is valid only after. So it will keep generating paths of increasing length even if they should all be discarded due to, e.g., a loop. In any case, I strongly suggest that you look into Djikstra's algorithm. – Regis Alenda Dec 18 '16 at 23:11