n 步中所有可能的骑士位置 - prolog 中的无限循环
All possible knight positions in n moves - infinite loop in prolog
在知道确切路径的情况下，当 n 移动中所有可能的骑士位置的计算解决方案时，我在 Prolog 中遇到回溯问题。
我的解决方案打印了一些最初的结果，然后在寻找不可能的结果时从不终止。
这是我的代码：
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).
示例调用：
predict_moves([1,1],3,P).
结果我期望 n 3 次移动中的所有可能路径。有人可以帮助我向我的代码添加条件以阻止我的代码回溯移动并循环到无穷大吗？
问题: 你写:
knight_move(X,Y,[X|P],C) :- move(X,Z), knight_move(Z,Y,P,Cn), C is Cn+1.
没有 cut 也没有任何其他机制阻止您使用此分支，因此 Prolog 可以继续使用此分支。此外，您应该递减计数器Cn is C-1并在递归调用之前执行此操作。
首先，我认为最好构建某种 validation 谓词而不是编写所有这些边界检查：
valid_position(X,Y) :-
X >= 0,
Y >= 0,
X < 8,
Y < 8.
我们还可以构造一个谓词plusneg/3，这样对于posneg(X,DX,Y)，Y既是X+DX又是X-DX：
posneg(X,DX,Y) :-
Y is X+DX.
posneg(X,DX,Y) :-
Y is X-DX.
那么我们可以描述骑士的"possible moves"：
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).
但这些本身不是 "valid moves"，因为我们需要检查新坐标是否有效。所以我们可以这样写：
move([X,Y], [A,B]) :-
possible(X,Y,A,B),
valid_position(A,B).
虽然这引入了一些额外的谓词，而且效率可能有点低，但现在很清楚所有的移动都是有效的。
现在对于带有计数器的 knigt_move/4，我们可以写一个子句，说明如果计数器降到零以下，则不再进行移动：
knight_move(P1,P1,[P1],C) :-
C < 1.
如果计数为1或更多，马仍然可以走一步，所以我们可以写成：
knight_move(P1,PZ,[P1|PT],C) :-
C >= 1,
C1 is C-1,
move(P1,P2),
knight_move(P2,PZ,PT,C1).
或者把这些放在一起：
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).
如果我们问我们恰好通过两次移动（以及如何）到达了哪些领域，我们得到：
?- 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.
所以我们可以用恰好两步走 24 条路。注意这里有重复，如果我们使用 setof/3 我们可以确定我们可以通过两次移动到达 15 个方格。三个动作有 148 条路径到达 30 个方格：
?- 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.
如果您使用 CLP(FD) 对整数进行推理，并更改约束的顺序以便在递归之前约束计数器，这将消除循环问题：
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).
这导致：
| ?- 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
| ?-
在真正解决问题之前，让我们先缩小不终止的来源。就您而言，这特别棘手，因为您会得到很好且正确的答案。只有这样才有问题。缩小问题范围的最简单方法是在程序中添加 false 目标。如果生成的程序仍然循环，我们可以继续添加更多此类目标。这是我想出的：
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.
现在所有被划线的部分对终止完全没有影响。起初这可能有点恼人，因为该代码实际上已执行，但仍然：对终止没有影响。请注意，特别是 knight_move/4 中的变量 C 现在是单例！
您需要修改剩余的可见部分以消除错误。
在知道确切路径的情况下，当 n 移动中所有可能的骑士位置的计算解决方案时，我在 Prolog 中遇到回溯问题。
我的解决方案打印了一些最初的结果，然后在寻找不可能的结果时从不终止。
这是我的代码：
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).
示例调用：
predict_moves([1,1],3,P).
结果我期望 n 3 次移动中的所有可能路径。有人可以帮助我向我的代码添加条件以阻止我的代码回溯移动并循环到无穷大吗？
问题: 你写:
knight_move(X,Y,[X|P],C) :- move(X,Z), knight_move(Z,Y,P,Cn), C is Cn+1.
没有 cut 也没有任何其他机制阻止您使用此分支，因此 Prolog 可以继续使用此分支。此外，您应该递减计数器Cn is C-1并在递归调用之前执行此操作。
首先，我认为最好构建某种 validation 谓词而不是编写所有这些边界检查：
valid_position(X,Y) :-
X >= 0,
Y >= 0,
X < 8,
Y < 8.
我们还可以构造一个谓词plusneg/3，这样对于posneg(X,DX,Y)，Y既是X+DX又是X-DX：
posneg(X,DX,Y) :-
Y is X+DX.
posneg(X,DX,Y) :-
Y is X-DX.
那么我们可以描述骑士的"possible moves"：
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).
但这些本身不是 "valid moves"，因为我们需要检查新坐标是否有效。所以我们可以这样写：
move([X,Y], [A,B]) :-
possible(X,Y,A,B),
valid_position(A,B).
虽然这引入了一些额外的谓词，而且效率可能有点低，但现在很清楚所有的移动都是有效的。
现在对于带有计数器的 knigt_move/4，我们可以写一个子句，说明如果计数器降到零以下，则不再进行移动：
knight_move(P1,P1,[P1],C) :-
C < 1.
如果计数为1或更多，马仍然可以走一步，所以我们可以写成：
knight_move(P1,PZ,[P1|PT],C) :-
C >= 1,
C1 is C-1,
move(P1,P2),
knight_move(P2,PZ,PT,C1).
或者把这些放在一起：
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).
如果我们问我们恰好通过两次移动（以及如何）到达了哪些领域，我们得到：
?- 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.
所以我们可以用恰好两步走 24 条路。注意这里有重复，如果我们使用 setof/3 我们可以确定我们可以通过两次移动到达 15 个方格。三个动作有 148 条路径到达 30 个方格：
?- 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.
如果您使用 CLP(FD) 对整数进行推理，并更改约束的顺序以便在递归之前约束计数器，这将消除循环问题：
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).
这导致：
| ?- 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
| ?-
在真正解决问题之前，让我们先缩小不终止的来源。就您而言，这特别棘手，因为您会得到很好且正确的答案。只有这样才有问题。缩小问题范围的最简单方法是在程序中添加 false 目标。如果生成的程序仍然循环，我们可以继续添加更多此类目标。这是我想出的：
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.
现在所有被划线的部分对终止完全没有影响。起初这可能有点恼人，因为该代码实际上已执行，但仍然：对终止没有影响。请注意，特别是 knight_move/4 中的变量 C 现在是单例！
您需要修改剩余的可见部分以消除错误。