Prolog: Shortest Path for Knight

Question

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.

Answer 1

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.