序言中的 N 皇后问题。如何优化皇后选择以提高效率？

Question

我用SWI Prolog实现了N-queen问题，但是我想优化queen的选择，这样效率会更高。这是我的代码：

safe(_,[],pos(A,B)).
safe(N,[pos(X,Y)|Rest],pos(A,B)):-
   safe(N,Rest,pos(A,B)),
   between(1,N,Y),
   noattack(pos(X,Y),Rest,pos(A,B)).

noattack(Queen,[],pos(A,B)).
noattack(pos(X,Y),[pos(X1,Y1)|Rest],pos(A,B)):-
   X=\=X1, Y=\=Y1, Y1-Y=\=X1-X,Y-Y1=\=X-X1,
   A=\=X, B=\=Y, A=\=X1, B=\=Y1, Y-Y1=\=A, X-X1=\=B,
   noattack(pos(X,Y),Rest,pos(A,B)).

template(N,L):-
   findall(pos(I,_),between(1,N,I),L). 

execute(N,N1,L,pos(A,B)):-
   template(N1,L),safe(N,L,pos(A,B)).

solution(L):-
   write('Please give number N and coordinates for super tower:'), nl,
   read(N),
   read(pos(A,B)),
   N1 is N-2,
   execute(N,N1,L,pos(A,B)).

有没有办法在 (1,N,Y) 之间改变，所以 Y 的选择将是 "more intelligent"？

Answer 1

我认为 "low hanging fruit"，我们可以通过动态减少 "domain" 来强制没有两个皇后在同一列上（在每一代中我们确定下一行的位置） .这意味着我们 (a) 永远不会产生两个皇后在同一列上的情况； (b) 我们也可以获得性能，因为我们不再需要检查它。

因此，我们可以从可能列的列表开始，例如 [1, 2, 3, 4]。如果我们为第一个皇后选择 2，我们将列表 [1, 3, 4] 传递给递归调用，无论递归调用选择什么，我们都知道这不能是同一列。为此，我们需要一个谓词来选择一个项目，同时生成一个我们删除该项目的列表，例如：

pick_rem([H|T], H, T).
pick_rem([H|T], P, [H|R]) :-
    pick_rem(T, P, R).

这将生成：

?- pick_rem([1,2,3], P, R).
P = 1,
R = [2, 3] ;
P = 2,
R = [1, 3] ;
P = 3,
R = [1, 2] ;
false.

一个额外的好处是，如果列表是空的，我们已经知道我们到达了棋盘的末尾，因此我们找到了一个有效的解决方案。因此可以使用简单的模式匹配而不是索引的数值比较来检查终止。

我们还需要一个生成范围的谓词，例如：

range(X, Y, []) :-
    X > Y.
range(X, Y, [X|T]) :-
    X =< Y,
    X1 is X + 1,
    range(X1, Y, T).

至于检查皇后是否不对角攻击，我们可以构造一个谓词，它接受两个数字，每次更新这两个数字，如：

not_attack([], _, _).
not_attack([H|T], C, D) :-
    \+ H is C + D,
    \+ H is C - D,
    D1 is D+1,
    not_attack(T, C, D1).

因此我们需要跟踪皇后的位置，并且按 "reverse" 顺序（因此最近的行是该列表的头部）。

所以现在我们可以将其组合在生成谓词中：

gen([], _, []).
gen(Dom, Old, [C|Res]) :-
    pick_rem(Dom, C, Dom1),
    not_attack(Old, C, 1),
    gen(Dom1, [C|Old], Res).

这里第一个参数是 "shrinking" 每次递归调用一个元素的域，第二个参数是一个列表，它由我们放在棋盘上的皇后的列组成。最后一个参数将 "construct" 棋盘的位置。

所以现在我们只需要用一些逻辑将这个谓词包装成一个更方便的：

to_pos(R, C, pos(R, C)).

n_queens(N, Sol) :-
    range(1, N, Dom),
    gen(Dom, [], Res),
    maplist(to_pos, Dom, Res, Sol).

然后为 N=4 和 N=5[=50= 生成 N-queens 解] 相当高效：

?- n_queens(4, S). S = [pos(1, 2), pos(2, 4), pos(3, 1), pos(4, 3)] ; S = [pos(1, 3), pos(2, 1), pos(3, 4), pos(4, 2)] ; false. ?- n_queens(5, S). S = [pos(1, 1), pos(2, 3), pos(3, 5), pos(4, 2), pos(5, 4)] ; S = [pos(1, 1), pos(2, 4), pos(3, 2), pos(4, 5), pos(5, 3)] ; S = [pos(1, 2), pos(2, 4), pos(3, 1), pos(4, 3), pos(5, 5)] ; S = [pos(1, 2), pos(2, 5), pos(3, 3), pos(4, 1), pos(5, 4)] ; S = [pos(1, 3), pos(2, 1), pos(3, 4), pos(4, 2), pos(5, 5)] ; S = [pos(1, 3), pos(2, 5), pos(3, 2), pos(4, 4), pos(5, 1)] ; S = [pos(1, 4), pos(2, 1), pos(3, 3), pos(4, 5), pos(5, 2)] ; S = [pos(1, 4), pos(2, 2), pos(3, 5), pos(4, 3), pos(5, 1)] ; S = [pos(1, 5), pos(2, 2), pos(3, 4), pos(4, 1), pos(5, 3)] ; S = [pos(1, 5), pos(2, 3), pos(3, 1), pos(4, 4), pos(5, 2)] ; false.

在我的机器上，它在 N=19 之前都非常有效。以上当然不是完美。人们可以考虑一些启发式方法等来选择更好的位置，或者提前看到某些模式会失败。现在，如果没有办法将女王放在棋盘上，我们只会停止搜索分支。但有时一些皇后的组合在后面永远不会产生好的结果，可以添加这样的模式以避免穷举搜索分支。

序言中的 N 皇后问题。如何优化皇后选择以提高效率？

N-queen problem in prolog. How to optimize the queen choice to be more efficient?

prolog

n-queens