首先：
这里发生了什么？
要了解发生了什么，请查看以下内容后记定义让我们可视化搜索：
/n 5 def
340 n div dup scale
-0.9 0.1 translate % leave room for line strokes
/Palatino-Roman 0.8 selectfont
/coords { n exch sub translate } bind def
/num { 3 1 roll gsave coords 0.5 0.2 translate
5 string cvs dup stringwidth pop -2 div 0 moveto show
grestore } bind def
/clr { gsave coords 1 setgray 0 0 1 1 4 copy rectfill
0 setgray 0.02 setlinewidth rectstroke grestore} bind def
1 1 n { 1 1 n { 1 index clr } for pop } for
这些定义为您提供了两个过程：
例如，如果您将这些定义保存到tour.ps然后调用 PostScript 解释器鬼脚本 with:
gs -r72 -g350x350 tour.ps
然后输入以下指令：
1 2 3 num
1 2 clr
2 3 4 num
you get:
PostScript 是一种用于可视化搜索过程的出色编程语言，我还建议您查看一下后记 /questions/tagged/postscript了解更多信息。
我们可以轻松修改您的程序以发出合适的 PostScript 指令，让我们直接观察搜索。我强调相关的补充：
constrain_entries([], _Square, _X, _Y).
constrain_entries([E|Es], Square, X, Y) :-
freeze(E, postscript(X, Y, E)),
constrain_entry(E, Square, X, Y),
X1 #= X + 1,
constrain_entries(Es, Square, X1, Y).
postscript(X, Y, N) :- format("~w ~w ~w num\n", [X,Y,N]).
postscript(X, Y, _) :- format("~w ~w clr\n", [X,Y]), false.
我也冒昧地改变了(is)/2 to (#=)/2使程序更加通用。
假设您将 PostScript 定义保存在tour.ps和你的 Prolog 程序tour.pl，以下 SWI-Prolog 和 Ghostscript 的调用说明了这种情况：
swipl -g "number_puzzle_(_, Vs), label(Vs)" tour.pl | gs -g350x350 -r72 tour.ps -dNOPROMPT
例如，我们在突出显示的位置看到大量回溯：
然而，根本问题已经完全存在于其他地方：
突出显示的方块都不是有效的移动！
From this, we see that your current formulation does not—at least not sufficiently early—let the solver recognize when a partial assignment cannot be completed to a solution! This is bad news, since failure to recognize inconsistent assignments often leads to unacceptable performance. For example, in order to correct the 1 → 3 transition (which can never occur in this way, yet is already one of the first choices made in this case), the solver would have to backtrack over approximately 8 squares, after enumerating—as a very rough estimate—258 = 152587890625 partial solutions, and then start all over at only the second position in the board.
在约束文献中，这种回溯被称为殴打。意味着重复的失败由于同样的原因.
这怎么可能？您的模型似乎是正确的，可以用来检测解决方案。那挺好的！然而，一个好的约束公式不仅可以识别解，还可以识别解。快速检测部分赋值cannot完成解决方案。这使得求解器能够有效地修剪搜索，正是在这个重要方面，您当前的公式存在不足。造成这种情况的原因之一与约束传播有关具体化的限制您正在使用的。特别是，考虑以下查询：
?- (X + 1 #= 3) #<==> B, X #\= 2.
直觉上，我们期望B = 0。但事实并非如此！相反，我们得到：
X in inf..1\/3..sup,
X+1#=_3840,
_3840#=3#B,
B in 0..1.
因此，求解器不会非常强烈地传播具体化平等。也许应该如此！仅够用feedbackProlog 实践者将判断约束求解器的这个区域是否应该改变，可能会牺牲一点速度来换取更强的传播。此反馈的高度相关性是我建议只要有机会（即每次推理时）就使用 CLP(FD) 约束的原因之一integers.
对于这个特殊情况，我可以告诉您，在这个意义上使求解器变得更强并不会产生太大的影响。本质上，您最终会得到一个核心问题仍然存在的主板版本，其中许多转换（其中一些在下面突出显示）在任何解决方案中都无法发生：
解决核心问题
我们应该消除回溯的原因其核心。为了修剪搜索，我们必须尽早识别不一致的（部分）分配。
直觉上，我们正在寻找一个互联旅游，并希望在明确旅行无法按预期方式继续时立即原路返回。
为了实现我们想要的目标，我们至少有两个选择：
- 更改分配策略以考虑连通性
- 以更强烈地考虑连通性的方式对问题进行建模。
方案一：分配策略
CLP(FD) 约束的一个主要吸引力在于它们让我们decouple来自搜索的任务描述。当使用CLP(FD)约束时，我们经常通过以下方式执行搜索label/1 or labeling/2。但是，我们可以自由地为变量赋值以任何我们想要的方式。如果我们遵循（就像您所做的那样）将“约束发布”部分放入其自己的谓词（称为核心关系.
例如，这里有一个custom确保旅行始终保持连接的分配策略：
allocation(Vs) :-
length(Vs, N),
numlist(1, N, Ns),
maplist(member_(Vs), Ns).
member_(Es, E) :- member(E, Es).
通过这个策略，我们从头开始得到了 5×5 实例的解决方案：
?- number_puzzle_(Square, Vars), time(allocation(Vars)).
% 5,030,522 inferences, 0.907 CPU in 0.913 seconds (99% CPU, 5549133 Lips)
Square = square(row(1, 8, 5, 2, 11), ...),
Vars = [1, 8, 5, 2, 11, 16, 21, 24, 15|...]
该策略有多种修改值得尝试。例如，当允许多个方格时，我们可以尝试通过考虑方格的数量来做出更明智的选择剩余域元素的正方形。我将尝试此类改进视为一项挑战。
从标准标签策略来看，min在这种情况下，标签选项实际上与此策略非常相似，并且实际上它也找到了 5×5 情况的解决方案：
?- number_puzzle_(Square, Vars), time(labeling([min], Vars)).
% 22,461,798 inferences, 4.142 CPU in 4.174 seconds (99% CPU, 5422765 Lips)
Square = square(row(1, 8, 5, 2, 11), ...),
Vars = [1, 8, 5, 2, 11, 16, 21, 24, 15|...] .
然而，即使是拟合分配策略也无法完全补偿弱约束传播。对于 10×10 实例，经过一番搜索后，棋盘看起来像这样min option:
请注意，我们还必须调整n在 PostScript 代码中将其可视化为预期的效果。
理想情况下，我们应该以能够从强传播中受益的方式制定任务，然后also使用良好的分配策略。
选项2：改造
良好的 CLP 公式可以传播尽可能强烈（在可接受的时间内）。因此，我们应该努力使用约束，使求解器能够更容易地推理任务最重要的要求。在这个具体的例子中，这意味着我们应该尝试找到一个更合适的表述来表达目前所表达的具体化约束的析取，如上所示，不允许太多的传播。理论上，约束求解器可以自动识别此类模式。然而，这对于许多用例来说是不切实际的，因此我们有时必须通过手动尝试几种有前途的公式来进行实验。不过，同样在这种情况下：有了应用程序程序员的足够反馈，这种情况更有可能得到改进和处理！
我现在使用 CLP(FD) 约束circuit/1明确我们正在寻找哈密顿电路在特定的图表中。该图表示为整数变量列表，其中每个元素表示其位置接班人在列表中。
例如，一个包含 3 个元素的列表恰好包含 2 个哈密顿回路：
?- Vs = [_,_,_], circuit(Vs), label(Vs).
Vs = [2, 3, 1] ;
Vs = [3, 1, 2].
I use circuit/1描述解决方案封闭式游览。这意味着，如果我们找到这样的解决方案，那么我们可以通过从找到的游览中最后一个方格开始的有效移动从头开始：
n_tour(N, Vs) :-
L #= N*N,
length(Vs, L),
successors(Vs, N, 1),
circuit(Vs).
successors([], _, _).
successors([V|Vs], N, K0) :-
findall(Num, n_k_next(N, K0, Num), [Next|Nexts]),
foldl(num_to_dom, Nexts, Next, Dom),
V in Dom,
K1 #= K0 + 1,
successors(Vs, N, K1).
num_to_dom(N, D0, D0\/N).
n_x_y_k(N, X, Y, K) :- [X,Y] ins 1..N, K #= N*(Y-1) + X.
n_k_next(N, K, Next) :-
n_x_y_k(N, X0, Y0, K),
( [DX,DY] ins -2 \/ 2
; [DX,DY] ins -3 \/ 0 \/ 3,
abs(DX) + abs(DY) #= 3
),
[X,Y] ins 1..N,
X #= X0 + DX,
Y #= Y0 + DY,
n_x_y_k(N, X, Y, Next),
label([DX,DY]).
请注意现在如何将可接受的后继者表示为域elements，减少约束的数量并完全消除具体化的需要。最重要的是，现在在搜索过程中的每个点都会自动考虑并强制执行预期的连接性。谓词n_x_y_k/4涉及(X,Y)坐标来列出索引。您可以通过更改此程序轻松地适应其他任务（例如，骑士之旅）n_k_next/3。我将概括留给open旅行作为一种挑战。
这里有一些额外的定义，让我们print更易读的形式的解决方案：
:- set_prolog_flag(double_quotes, chars).
print_tour(Vs) :-
length(Vs, L),
L #= N*N, N #> 0,
length(Ts, N),
tour_enumeration(Vs, N, Es),
phrase(format_string(Ts, 0, 4), Fs),
maplist(format(Fs), Es).
format_(Fs, Args, Xs0, Xs) :- format(chars(Xs0,Xs), Fs, Args).
format_string([], _, _) --> "\n".
format_string([_|Rest], N0, I) -->
{ N #= N0 + I },
"~t~w~", call(format_("~w|", [N])),
format_string(Rest, N, I).
tour_enumeration(Vs, N, Es) :-
length(Es, N),
maplist(same_length(Es), Es),
append(Es, Ls),
foldl(vs_enumeration(Vs, Ls), Vs, 1-1, _).
vs_enumeration(Vs, Ls, _, V0-E0, V-E) :-
E #= E0 + 1,
nth1(V0, Ls, E0),
nth1(V0, Vs, V).
在具有强传播的配方中，预定义的ff搜索策略通常是一个好的策略。事实上，它可以让我们在商用机器上几秒钟内解决整个任务，即原始的 10×10 实例：
?- n_tour(10, Vs),
time(labeling([ff], Vs)),
print_tour(Vs).
% 5,642,756 inferences, 0.988 CPU in 0.996 seconds (99% CPU, 5710827 Lips)
1 96 15 2 97 14 80 98 13 79
93 29 68 94 30 27 34 31 26 35
16 3 100 17 4 99 12 9 81 45
69 95 92 28 67 32 25 36 33 78
84 18 5 83 19 10 82 46 11 8
91 23 70 63 24 37 66 49 38 44
72 88 20 73 6 47 76 7 41 77
85 62 53 86 61 64 39 58 65 50
90 22 71 89 21 74 42 48 75 43
54 87 60 55 52 59 56 51 40 57
Vs = [4, 5, 21, 22, 8, 3, 29, 26, 6|...]
为了获得最佳性能，我建议您也尝试使用其他 Prolog 系统。商业级 CLP(FD) 系统的效率通常是购买 Prolog 系统的重要原因。
还要注意，这绝不是该任务唯一有前途的 Prolog 甚至 CLP(FD) 表述，我将其他表述视为一项挑战。
