我已经写了一些代码，做的Prolog回溯产生的所有可能的路径，从最初的一个（代理）到达黄金细胞。 getAllPaths的输入是在地图大小为NxN。 当我和6×6地图它完美和打印所有可能的路径，但是，当运行它我输入任何地图大小> = 7它打印所述第一路径，并且当我需要与下一个可能的解决方案被卡在那里; 。 这里是我的代码：
gold(3, 3).
agent(1, 1).
getAllPaths(MS) :-
agent(X, Y),
assertz(worldSize(MS)),
getAllPathsRec(X, Y, [], []).
% Positions, Visited list, and Path list
getAllPathsRec(X, Y, V, L) :-
\+member((X, Y), V), append(V, [(X, Y)], VP),
((gold(X, Y), print(L)) ; move(X, Y, VP, L)).
% Left
move(X, Y, V, L) :-
XP is X - 1, XP > 0,
append(L, [l], LP),
getAllPathsRec(XP, Y, V, LP).
% Right
move(X, Y, V, L) :-
XP is X + 1, worldSize(MS), XP =< MS,
append(L, [r], LP),
getAllPathsRec(XP, Y, V, LP).
% Up
move(X, Y, V, L) :-
YP is Y + 1, worldSize(MS), YP =< MS,
append(L, [u], LP),
getAllPathsRec(X, YP, V, LP).
% Down
move(X, Y, V, L) :-
YP is Y - 1, YP > 0,
append(L, [d], LP),
getAllPathsRec(X, YP, V, LP).
输出：
?- getAllPaths(6).
[r,r,r,r,r,u,l,l,l,l,l,u,r,r]
true ;
[r,r,r,r,r,u,l,l,l,l,l,u,r,u,l,u,r,r,r,r,r,d,l,l,l,d]
true ;
[r,r,r,r,r,u,l,l,l,l,l,u,r,u,l,u,r,r,r,r,r,d,l,l,d,l]
true ;
[...]
?- getAllPaths(7).
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r]
true ;
% It gets stuck here forever...
首先，我认为这将是对于一些深度递归的限制，但它是如此奇怪，因为地图尺寸仅增加36至49，我可能会得到一些警告或错误，但它不显示任何内容。 任何线索？
这是我的变化。
getAllPaths_01(MS, R) :-
agent(X, Y),
getAllPathsRec_01(MS, X, Y, [], R).
getAllPathsRec_01(_MS, X, Y, _V, []) :-
gold(X,Y), !.
% Positions, Visited list, and Path list
getAllPathsRec_01(MS, X, Y, V, R) :-
\+ memberchk((X, Y), V),
move_01(MS, X, Y, [(X, Y)|V], R).
% Left
move_01(MS, X, Y, V, [l|R]) :-
XP is X - 1, XP > 0,
getAllPathsRec_01(MS, XP, Y, V, R).
% Right
move_01(MS, X, Y, V, [r|R]) :-
XP is X + 1, XP =< MS,
getAllPathsRec_01(MS, XP, Y, V, R).
% Up
move_01(MS, X, Y, V, [u|R]) :-
YP is Y + 1, YP =< MS,
getAllPathsRec_01(MS, X, YP, V, R).
% Down
move_01(MS, X, Y, V, [d|R]) :-
YP is Y - 1, YP > 0,
getAllPathsRec_01(MS, X, YP, V, R).
count(S,N) :-
bagof(L,getAllPaths_01(S,L),Ls),
length(Ls,N).
这消除了使用assertz / 1 ，以便重新运行查询不添加多个事实，改变构件/ 2到memerchk / 2为效率，在回溯以避免构建路径附加/ 3 ，并增加了一个切口，以除去重复的答案。
由于结果返回到顶级，加计数/ 2，显示计数，而不是名单。
?- count(3,N).
N = 12.
?- count(4,N).
N = 132.
?- count(5,N).
N = 6762.
?- count(6,N).
N = 910480
此代码提高性能。 我认为这是一个不好的设计混合搜索和结果的打印。
gold(3, 3).
agent(1, 1).
getAllPaths(MS, L) :-
agent(X, Y),
retractall(worldSize(_)),
assertz(worldSize(MS)),
getAllPathsRec(X, Y, [], [], L).
% Positions, Visited list, and Path list
getAllPathsRec(X, Y, _V, L, NL) :-
gold(X, Y),
reverse(L, NL).
% Positions, Visited list, and Path list
getAllPathsRec(X, Y, V, CL, L) :-
\+member((X, Y), V),
% useless
% append(V, [(X, Y)], VP),
move(X, Y, CL, NX, NY, NL),
% No need to use append to build the list of visited nodes
getAllPathsRec(NX, NY, [(X,Y) | V], NL, L).
% Left
move(X, Y, L, NX, Y, [l|L]) :-
X > 1 ,NX is X - 1.
% Right
move(X, Y, L, NX, Y, [r|L]) :-
worldSize(MS), X < MS,NX is X + 1.
% Up
move(X, Y, L, X, NY, [u|L]) :-
worldSize(MS), Y < MS, NY is Y + 1.
% Down
move(X, Y, L, X, NY, [d|L]) :-
Y > 1, NY is Y - 1.
我得到：
?- getAllPaths(7, V), writeln(V).
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,l]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,r,r,r,u,l,l,l,l,d]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,r,r,r,u,l,l,l,u,l,l,l,d,r,r,d]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,r,r,r,u,l,l,l,u,l,l,u,l,d,d,r,r,d]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,r,r,r,u,l,l,l,u,l,l,u,r,r,r,r,r,u,l,l,l,l,l,l,d,d,d,r,r,d]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,r,r,r,u,l,l,l,u,l,l,u,r,r,r,r,u,l,l,l,l,l,d,d,d,r,r,d]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,r,r,r,u,l,l,l,u,l,l,u,r,r,r,r,d,r,u,u,l,l,l,l,l,l,d,d,d,r,r,d]
V = [r, r, r, r, r, r, u, l, l|...] .
