这个 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，则约束将 fire，将B的域缩小为B in 2..3。因为它不能再有值 1.

在safe(L)之后，我们就把所有的约束都添加到约束存储中了，然后labeling/2就可以开始搜索解了。

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

How does this n-queens Prolog solution work?

algorithm

prolog

n-queens