All possible knight positions in n moves - infinite loop in prolog

Question

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?

Answer 1

Before actually removing the problem, let's narrow down the source of non-termination. In your case, it is particularly tricky, for you get answers that are nice and correct. Only then there is a problem. The easiest way to narrow down the problem is by adding false goals into your program. If the resulting program still loops, we can continue adding further such goals. Here is what I came up with:

move([X, Y], [A, B]) :- X+1 < 8, Y+2 < 8, A is X+1, B is Y+2.
move([X, Y], [A, B]) :- false, X+2 < 8, Y+1 < 8, A is X+2, B is Y+1.
move([X, Y], [A, B]) :- false, X+2 < 8, Y-1 >= 0, A is X+2, B is Y-1.
move([X, Y], [A, B]) :- false, 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]) :- false, X-2 >= 0, Y-1 >= 0, A is X-2, B is Y-1.
move([X, Y], [A, B]) :- false, X-2 >= 0, Y+1 < 8, A is X-2, B is Y+1.
move([X, Y], [A, B]) :- false, X-1 >= 0, Y+2 < 8, A is X-1, B is Y+2.

knight_move(X,Y,[X,Y],1) :- false, move(X,Y).
knight_move(X,Y,[X|P],C) :- move(X,Z), knight_move(Z,Y,P,Cn), false, C is Cn+1.

predict_moves(X,C,P) :- knight_move(X,_,P,C), false.

?- predict_moves([1,1],3,P), false.

All parts that are now striked through have no influence at all to termination. That might be a little irritating at first, for that code is actually executed, but still: no influence on termination. Note that in particular the variable C in knight_move/4 is now a singleton!

You need to modify the remaining visible part to remove the error.

Answer 2

If you use CLP(FD) for reasoning over integers, and change the order of your constraints so that you constrain the counter before you recurse, that will eliminate your looping issue:

move([X, Y], [A, B]) :- X + 1 #< 8, Y + 2 #< 8, A #= X + 1, B #= Y + 2.
move([X, Y], [A, B]) :- X + 2 #< 8, Y + 1 #< 8, A #= X + 2, B #= Y + 1.
move([X, Y], [A, B]) :- X + 2 #< 8, Y - 1 #>= 0, A #= X + 2, B #= Y - 1.
move([X, Y], [A, B]) :- X + 1 #< 8, Y - 2 #>= 0, A #= X + 1, B #= Y - 2.
move([X, Y], [A, B]) :- X - 1 #>= 0, Y - 2 #>= 0, A #= X - 1, B #= Y - 2.
move([X, Y], [A, B]) :- X - 2 #>= 0, Y - 1 #>= 0, A #= X - 2, B #= Y - 1.
move([X, Y], [A, B]) :- X - 2 #>= 0, Y + 1 #< 8, A #= X - 2, B #= Y + 1.
move([X, Y], [A, B]) :- X - 1 #>= 0, Y + 2 #< 8, A #= X - 1, B #= Y + 2.


knight_move(X,Y,[X,Y], 1) :- move(X,Y).

# NOTE the constraint of C #= Cn + 1 before the recursive call
knight_move(X,Y,[X|P], C) :- C #> 1, move(X,Z), C #= Cn + 1, knight_move(Z,Y,P,Cn).

predict_moves(X,C,P) :- knight_move(X,_,P,C).

Which results in:

| ?- predict_moves([1,1], 3, P).

P = [[1,1],[2,3],[3,5],[4,7]] ? a

P = [[1,1],[2,3],[3,5],[5,6]]

P = [[1,1],[2,3],[3,5],[5,4]]

P = [[1,1],[2,3],[3,5],[4,3]]

P = [[1,1],[2,3],[3,5],[2,3]]

P = [[1,1],[2,3],[3,5],[1,4]]

P = [[1,1],[2,3],[3,5],[1,6]]

P = [[1,1],[2,3],[3,5],[2,7]]

P = [[1,1],[2,3],[4,4],[5,6]]

P = [[1,1],[2,3],[4,4],[6,5]]

P = [[1,1],[2,3],[4,4],[6,3]]

P = [[1,1],[2,3],[4,4],[5,2]]

P = [[1,1],[2,3],[4,4],[3,2]]

P = [[1,1],[2,3],[4,4],[2,3]]

P = [[1,1],[2,3],[4,4],[2,5]]

P = [[1,1],[2,3],[4,4],[3,6]]

P = [[1,1],[2,3],[4,2],[5,4]]

P = [[1,1],[2,3],[4,2],[6,3]]

P = [[1,1],[2,3],[4,2],[6,1]]

P = [[1,1],[2,3],[4,2],[5,0]]

P = [[1,1],[2,3],[4,2],[3,0]]

P = [[1,1],[2,3],[4,2],[2,1]]

P = [[1,1],[2,3],[4,2],[2,3]]

P = [[1,1],[2,3],[4,2],[3,4]]

P = [[1,1],[2,3],[3,1],[4,3]]

P = [[1,1],[2,3],[3,1],[5,2]]

P = [[1,1],[2,3],[3,1],[5,0]]

P = [[1,1],[2,3],[3,1],[1,0]]

P = [[1,1],[2,3],[3,1],[1,2]]

P = [[1,1],[2,3],[3,1],[2,3]]

P = [[1,1],[2,3],[1,1],[2,3]]

P = [[1,1],[2,3],[1,1],[3,2]]

P = [[1,1],[2,3],[1,1],[3,0]]

P = [[1,1],[2,3],[1,1],[0,3]]

P = [[1,1],[2,3],[0,2],[1,4]]

P = [[1,1],[2,3],[0,2],[2,3]]

P = [[1,1],[2,3],[0,2],[2,1]]

P = [[1,1],[2,3],[0,2],[1,0]]

P = [[1,1],[2,3],[0,4],[1,6]]

P = [[1,1],[2,3],[0,4],[2,5]]

P = [[1,1],[2,3],[0,4],[2,3]]

P = [[1,1],[2,3],[0,4],[1,2]]

P = [[1,1],[2,3],[1,5],[2,7]]

P = [[1,1],[2,3],[1,5],[3,6]]

P = [[1,1],[2,3],[1,5],[3,4]]

P = [[1,1],[2,3],[1,5],[2,3]]

P = [[1,1],[2,3],[1,5],[0,3]]

P = [[1,1],[2,3],[1,5],[0,7]]

P = [[1,1],[3,2],[4,4],[5,6]]

P = [[1,1],[3,2],[4,4],[6,5]]

P = [[1,1],[3,2],[4,4],[6,3]]

P = [[1,1],[3,2],[4,4],[5,2]]

P = [[1,1],[3,2],[4,4],[3,2]]

P = [[1,1],[3,2],[4,4],[2,3]]

P = [[1,1],[3,2],[4,4],[2,5]]

P = [[1,1],[3,2],[4,4],[3,6]]

P = [[1,1],[3,2],[5,3],[6,5]]

P = [[1,1],[3,2],[5,3],[7,4]]

P = [[1,1],[3,2],[5,3],[7,2]]

P = [[1,1],[3,2],[5,3],[6,1]]

P = [[1,1],[3,2],[5,3],[4,1]]

P = [[1,1],[3,2],[5,3],[3,2]]

P = [[1,1],[3,2],[5,3],[3,4]]

P = [[1,1],[3,2],[5,3],[4,5]]

P = [[1,1],[3,2],[5,1],[6,3]]

P = [[1,1],[3,2],[5,1],[7,2]]

P = [[1,1],[3,2],[5,1],[7,0]]

P = [[1,1],[3,2],[5,1],[3,0]]

P = [[1,1],[3,2],[5,1],[3,2]]

P = [[1,1],[3,2],[5,1],[4,3]]

P = [[1,1],[3,2],[4,0],[5,2]]

P = [[1,1],[3,2],[4,0],[6,1]]

P = [[1,1],[3,2],[4,0],[2,1]]

P = [[1,1],[3,2],[4,0],[3,2]]

P = [[1,1],[3,2],[2,0],[3,2]]

P = [[1,1],[3,2],[2,0],[4,1]]

P = [[1,1],[3,2],[2,0],[0,1]]

P = [[1,1],[3,2],[2,0],[1,2]]

P = [[1,1],[3,2],[1,1],[2,3]]

P = [[1,1],[3,2],[1,1],[3,2]]

P = [[1,1],[3,2],[1,1],[3,0]]

P = [[1,1],[3,2],[1,1],[0,3]]

P = [[1,1],[3,2],[1,3],[2,5]]

P = [[1,1],[3,2],[1,3],[3,4]]

P = [[1,1],[3,2],[1,3],[3,2]]

P = [[1,1],[3,2],[1,3],[2,1]]

P = [[1,1],[3,2],[1,3],[0,1]]

P = [[1,1],[3,2],[1,3],[0,5]]

P = [[1,1],[3,2],[2,4],[3,6]]

P = [[1,1],[3,2],[2,4],[4,5]]

P = [[1,1],[3,2],[2,4],[4,3]]

P = [[1,1],[3,2],[2,4],[3,2]]

P = [[1,1],[3,2],[2,4],[1,2]]

P = [[1,1],[3,2],[2,4],[0,3]]

P = [[1,1],[3,2],[2,4],[0,5]]

P = [[1,1],[3,2],[2,4],[1,6]]

P = [[1,1],[3,0],[4,2],[5,4]]

P = [[1,1],[3,0],[4,2],[6,3]]

P = [[1,1],[3,0],[4,2],[6,1]]

P = [[1,1],[3,0],[4,2],[5,0]]

P = [[1,1],[3,0],[4,2],[3,0]]

P = [[1,1],[3,0],[4,2],[2,1]]

P = [[1,1],[3,0],[4,2],[2,3]]

P = [[1,1],[3,0],[4,2],[3,4]]

P = [[1,1],[3,0],[5,1],[6,3]]

P = [[1,1],[3,0],[5,1],[7,2]]

P = [[1,1],[3,0],[5,1],[7,0]]

P = [[1,1],[3,0],[5,1],[3,0]]

P = [[1,1],[3,0],[5,1],[3,2]]

P = [[1,1],[3,0],[5,1],[4,3]]

P = [[1,1],[3,0],[1,1],[2,3]]

P = [[1,1],[3,0],[1,1],[3,2]]

P = [[1,1],[3,0],[1,1],[3,0]]

P = [[1,1],[3,0],[1,1],[0,3]]

P = [[1,1],[3,0],[2,2],[3,4]]

P = [[1,1],[3,0],[2,2],[4,3]]

P = [[1,1],[3,0],[2,2],[4,1]]

P = [[1,1],[3,0],[2,2],[3,0]]

P = [[1,1],[3,0],[2,2],[1,0]]

P = [[1,1],[3,0],[2,2],[0,1]]

P = [[1,1],[3,0],[2,2],[0,3]]

P = [[1,1],[3,0],[2,2],[1,4]]

P = [[1,1],[0,3],[1,5],[2,7]]

P = [[1,1],[0,3],[1,5],[3,6]]

P = [[1,1],[0,3],[1,5],[3,4]]

P = [[1,1],[0,3],[1,5],[2,3]]

P = [[1,1],[0,3],[1,5],[0,3]]

P = [[1,1],[0,3],[1,5],[0,7]]

P = [[1,1],[0,3],[2,4],[3,6]]

P = [[1,1],[0,3],[2,4],[4,5]]

P = [[1,1],[0,3],[2,4],[4,3]]

P = [[1,1],[0,3],[2,4],[3,2]]

P = [[1,1],[0,3],[2,4],[1,2]]

P = [[1,1],[0,3],[2,4],[0,3]]

P = [[1,1],[0,3],[2,4],[0,5]]

P = [[1,1],[0,3],[2,4],[1,6]]

P = [[1,1],[0,3],[2,2],[3,4]]

P = [[1,1],[0,3],[2,2],[4,3]]

P = [[1,1],[0,3],[2,2],[4,1]]

P = [[1,1],[0,3],[2,2],[3,0]]

P = [[1,1],[0,3],[2,2],[1,0]]

P = [[1,1],[0,3],[2,2],[0,1]]

P = [[1,1],[0,3],[2,2],[0,3]]

P = [[1,1],[0,3],[2,2],[1,4]]

P = [[1,1],[0,3],[1,1],[2,3]]

P = [[1,1],[0,3],[1,1],[3,2]]

P = [[1,1],[0,3],[1,1],[3,0]]

P = [[1,1],[0,3],[1,1],[0,3]]

(3 ms) no
| ?-