I have a problem with backtracking in Prolog when calculation solution for all possible knight positions in n moves with knowing the exact path.
My solution print some of the first results and then never terminate while looking for impossible results.
This is my code:
move([X, Y], [A, B]) :- X + 1 < 8, Y + 2 < 8, A is X + 1, B is Y + 2.
move([X, Y], [A, B]) :- X + 2 < 8, Y + 1 < 8, A is X + 2, B is Y + 1.
move([X, Y], [A, B]) :- X + 2 < 8, Y - 1 >= 0, A is X + 2, B is Y - 1.
move([X, Y], [A, B]) :- X + 1 < 8, Y - 2 >= 0, A is X + 1, B is Y - 2.
move([X, Y], [A, B]) :- X - 1 >= 0, Y - 2 >= 0, A is X - 1, B is Y - 2.
move([X, Y], [A, B]) :- X - 2 >= 0, Y - 1 >= 0, A is X - 2, B is Y - 1.
move([X, Y], [A, B]) :- X - 2 >= 0, Y + 1 < 8, A is X - 2, B is Y + 1.
move([X, Y], [A, B]) :- X - 1 >= 0, Y + 2 < 8, A is X - 1, B is Y + 2.
knight_move(X,Y,[X,Y],1) :- move(X,Y).
knight_move(X,Y,[X|P],C) :- move(X,Z), knight_move(Z,Y,P,Cn), C is Cn+1.
predict_moves(X,C,P) :- knight_move(X,_,P,C).
Sample call:
predict_moves([1,1],3,P).
In result I expect all possible paths in n 3 moves. Can sb help me with adding condition to my code to stop my code from backtracking to move and looping to infinity?
The problem: you write:
knight_move(X,Y,[X|P],C) :- move(X,Z), knight_move(Z,Y,P,Cn), C is Cn+1.
there is no cut nor any other mechanism that prevents you from taking this branch, so Prolog can keep taking this branch. Furthermore you should decrement the counter Cn is C-1 and do this before the recursive call.
First of all, I think it is better to construct some sort of validation predicate instead of writing all these bounds checks:
valid_position(X,Y) :-
X >= 0,
Y >= 0,
X < 8,
Y < 8.
We can also construct a predicate plusneg/3 such that for posneg(X,DX,Y), Y is both X+DX and X-DX:
posneg(X,DX,Y) :-
Y is X+DX.
posneg(X,DX,Y) :-
Y is X-DX.
then we can describe the "possible moves" of the knight:
possible(X, Y, A, B) :-
posneg(X,2,A),
posneg(Y,1,B).
possible(X, Y, A, B) :-
posneg(X,1,A),
posneg(Y,2,B).
but these are not per se "valid moves", since we need to check if the new coordinate is valid. So we can write:
move([X,Y], [A,B]) :-
possible(X,Y,A,B),
valid_position(A,B).
although this introduces some additiona predicates, and is perhaps a litte less efficient, it is now clear that all the moves are valid ones.
Now for the knigt_move/4 with the counter, we can write a clause that says that if the counter has dropped below zero, no more moves are done:
knight_move(P1,P1,[P1],C) :-
C < 1.
In case the count is one or more, the knight can still do a move, so we can write it as:
knight_move(P1,PZ,[P1|PT],C) :-
C >= 1,
C1 is C-1,
move(P1,P2),
knight_move(P2,PZ,PT,C1).
Or putting this all together:
valid_position(X,Y) :-
X >= 0,
Y >= 0,
X < 8,
Y < 8.
posneg(X,DX,Y) :-
Y is X+DX.
posneg(X,DX,Y) :-
Y is X-DX.
possible(X, Y, A, B) :-
posneg(X,2,A),
posneg(Y,1,B).
possible(X, Y, A, B) :-
posneg(X,1,A),
posneg(Y,2,B).
move([X,Y], [A,B]) :-
possible(X,Y,A,B),
valid_position(A,B).
knight_move(P1,P1,[P1],C) :-
C < 1.
knight_move(P1,PZ,[P1|PT],C) :-
C >= 1,
C1 is C-1,
move(P1,P2),
knight_move(P2,PZ,PT,C1).
If we ask what fields we reach with exactly two moves (and how), we got:
?- knight_move([1,1],End,Path,2).
End = [5, 3],
Path = [[1, 1], [3, 2], [5, 3]] ;
End = [5, 1],
Path = [[1, 1], [3, 2], [5, 1]] ;
End = [1, 3],
Path = [[1, 1], [3, 2], [1, 3]] ;
End = [1, 1],
Path = [[1, 1], [3, 2], [1, 1]] ;
End = [4, 4],
Path = [[1, 1], [3, 2], [4, 4]] ;
End = [4, 0],
Path = [[1, 1], [3, 2], [4, 0]] ;
End = [2, 4],
Path = [[1, 1], [3, 2], [2, 4]] ;
End = [2, 0],
Path = [[1, 1], [3, 2], [2, 0]] ;
End = [5, 1],
Path = [[1, 1], [3, 0], [5, 1]] ;
End = [1, 1],
Path = [[1, 1], [3, 0], [1, 1]] ;
End = [4, 2],
Path = [[1, 1], [3, 0], [4, 2]] ;
End = [2, 2],
Path = [[1, 1], [3, 0], [2, 2]] ;
End = [4, 4],
Path = [[1, 1], [2, 3], [4, 4]] ;
End = [4, 2],
Path = [[1, 1], [2, 3], [4, 2]] ;
End = [0, 4],
Path = [[1, 1], [2, 3], [0, 4]] ;
End = [0, 2],
Path = [[1, 1], [2, 3], [0, 2]] ;
End = [3, 5],
Path = [[1, 1], [2, 3], [3, 5]] ;
End = [3, 1],
Path = [[1, 1], [2, 3], [3, 1]] ;
End = [1, 5],
Path = [[1, 1], [2, 3], [1, 5]] ;
End = [1, 1],
Path = [[1, 1], [2, 3], [1, 1]] ;
End = [2, 4],
Path = [[1, 1], [0, 3], [2, 4]] ;
End = [2, 2],
Path = [[1, 1], [0, 3], [2, 2]] ;
End = [1, 5],
Path = [[1, 1], [0, 3], [1, 5]] ;
End = [1, 1],
Path = [[1, 1], [0, 3], [1, 1]] ;
false.
So we can make 24 paths with exactly two moves. Note that there are duplicates, if we use setof/3 we can determine that we can reach 15 squares with two moves. For three moves there are 148 paths to reach 30 squares:
?- findall(End,knight_move([1,1],End,_,2),Ends), length(Ends,N).
Ends = [[5, 3], [5, 1], [1, 3], [1, 1], [4, 4], [4, 0], [2, 4], [2|...], [...|...]|...],
N = 24.
?- setof(End,Pa^knight_move([1,1],End,Pa,2),Ends), length(Ends,N).
Ends = [[0, 2], [0, 4], [1, 1], [1, 3], [1, 5], [2, 0], [2, 2], [2|...], [...|...]|...],
N = 15.
?- findall(End,knight_move([1,1],End,_,3),Ends), length(Ends,N).
Ends = [[7, 4], [7, 2], [3, 4], [3, 2], [6, 5], [6, 1], [4, 5], [4|...], [...|...]|...],
N = 148.
?- setof(End,Pa^knight_move([1,1],End,Pa,3),Ends), length(Ends,N).
Ends = [[0, 1], [0, 3], [0, 5], [0, 7], [1, 0], [1, 2], [1, 4], [1|...], [...|...]|...],
N = 30.