algorithm - 这个 n-queens Prolog 解决方案是如何工作的？

Question

我正在尝试了解 N-Queens Problem‍​..How far can we go? 中的 n-queens Prolog 解决方案作品(原始页面上没有评论)。我试图在我能理解的地方添加评论:

generate([],_).          % A LIST BEING GENERATED
generate([H|T],N) :-
   H in 1..N ,           % NOT CLEAR IF IT INCLUDES ALL COMBINATIONS OR PERMUTATIONS
   generate(T,N).

lenlist(L,N) :- 
   lenlist(L,0,N).

lenlist([],N,N).
lenlist([_|T],P,N) :-
   P1 is P+1,
   lenlist(T,P1,N).

queens(N,L) :-           % MAIN FN: SEND NUMBER OF QUEENS AND GET ANSWER LIST OF LISTS
   generate(L,N),lenlist(L,N),     % GENERATE LIST BASED ON N OF ALL COMBINATIONS
   safe(L),              % CHECK WHICH ONES ARE SAFE (NON-ATTACKING)
   !,
   labeling([ffc],L).    % CHOOSE CORRECT ONES (WHY NEEDED IF ALREADY FOUND SAFE?)

notattack(X,Xs) :-       % FNS TO FIND QUEENS NOT ATTACKING
   notattack(X,Xs,1).

notattack(X,[],N).
notattack(X,[Y|Ys],N) :-
   X #\= Y,
   X #\= Y - N,
   X #\= Y + N,
   N1 is N + 1,
   notattack(X,Ys,N1).

safe([]).                % RECURSIVE FN TO FIND LISTS WITH NON-ATTACKING QUEENS
safe([F|T]) :-
   notattack(F,T),
   safe(T).

我不太清楚初始列表是如何生成的。它是一个全排列列表还是一个随机列表？此外，为什么需要安全和标签功能？提前感谢您的帮助。

Answer 1

你的假设:

safe(L),    % check which ones are safe (non-attacking)

(小写)是错误的:safe(L) 不检查两个蜂后是否在攻击:它将添加约束这样蜂后在标记期间(以及之后)不会攻击。

Safe 是一种递归方法，对于列表 [A, B, C]添加约束:

A #\= B,
A #\= B - 1,
A #\= B + 1,
A #\= C,
A #\= C - 2,
A #\= C + 2,
B #\= C,
B #\= C - 1,
B #\= C + 1.

这些约束不会立即执行，因为这些约束将值分配给 A , B和 C : 添加了这些约束，并且从修改变量域的那一刻起，约束的目标就是减少所涉及的其他变量的域。

例如，如果约束是 A #\= B和两个A in 1..3和 B in 1..3 , 如果 labeling/2将分配 A = 1 ，那么约束将触发，并减少 B 的域至 B in 2..3 .因为它不能再有值 1。

safe(L)之后，因此我们已将所有约束添加到约束存储中，然后是 labeling/2可以开始寻找解决方案。