0

女王统治给定一个 n×n 棋盘，统治数是攻击或占领每个方格所需的女王（或其他棋子）的最小数量。当 n=8 时，皇后的支配数是 5。写一个谓词解（N），得到覆盖所有方格所需的最小皇后数。

4

1 回答 1

4

这是一个愚蠢的“所有解决方案”片段：

queens_coverage(N, Places) :-
    findall(X/Y, (between(1,N,X), between(1,N,Y)), B),
    placement(B, [], Places).

placement([], Placement, Placement).
placement(Unplaced, SoFar, Placement) :-
    select(Place, Unplaced, Places),
    remove_attacks(Place, Places, Remains),
    placement(Remains, [Place|SoFar], Placement).

remove_attacks(X/Y, [U/V|Places], Remains) :-
    ( U == X ; V == Y ; abs(U-X) =:= abs(V-Y) ),
    !, remove_attacks(X/Y, Places, Remains).
remove_attacks(P, [A|Places], [A|Remains]) :-
    remove_attacks(P, Places, Remains).
remove_attacks(_, [], []).

与排列问题一样，该代码效率低下是无可救药的：

?- setof(L-Ps, (queens_coverage(4,Ps),length(Ps,L)), R), length(R, T).
R = [3-[1/1, 2/3, 4/2], 3-[1/1, 2/4, 3/2], 3-[1/1, 2/4, 4/3], 3-[1/1, 3/2, 2/4], 3-[1/1, 3/4, ... / ...], 3-[1/1, ... / ...|...], 3-[... / ...|...], 3-[...|...], ... - ...|...],
T = 144.

?- setof(L-Ps, (queens_coverage(5,Ps),length(Ps,L)), R), length(R, T).
R = [3-[1/1, 2/4, 4/3], 3-[1/1, 3/4, 4/2], 3-[1/1, 3/4, 5/3], 3-[1/1, 3/5, 4/3], 3-[1/1, 4/2, ... / ...], 3-[1/1, ... / ...|...], 3-[... / ...|...], 3-[...|...], ... - ...|...],
T = 2064.

?- setof(L-Ps, (queens_coverage(6,Ps),length(Ps,L)), R), length(R, T).
R = [4-[1/1, 2/3, 3/6, 6/2], 4-[1/1, 2/3, 6/2, 3/6], 4-[1/1, 2/4, 4/5, 5/2], 4-[1/1, 2/4, 4/5, ... / ...], 4-[1/1, 2/4, ... / ...|...], 4-[1/1, ... / ...|...], 4-[... / ...|...], 4-[...|...], ... - ...|...],
T = 32640.

?- setof(L-Ps, (queens_coverage(7,Ps),length(Ps,L)), R), length(R, T).
ERROR: Out of global stack

当然，存储所有列表是一种真正的浪费。

?- integrate(min, qc(7), R).
R = 4-[1/2, 2/6, 4/1, 5/5] .

?- integrate(min, qc(8), R).
R = 5-[1/1, 2/3, 3/5, 4/2, 5/4]

而不是 select/3 您应该应用适当的启发式方法。一个简单的可能是贪婪的选择......

编辑

这里是整合：

integrate(min, Goal, R) :-
    State = (_, _),
    repeat,
    (   call(Goal, V),
        arg(1, State, C),
        ( ( var(C) ; V @< C ) -> U = V ; U = C ),
        nb_setarg(1, State, U),
        fail
    ;   arg(1, State, R)
    ),
    !.

nb_setarg/3 是内置的 SWI-Prolog，arg/3 是 ISO。如果你的 Prolog 错过了它们，你应该用 assert/retract 替换——例如——。

Integrate 接受一个谓词，并使用附加参数调用它以与存储的当前最小值进行比较：这里是：

qc(N, L-Ps) :- queens_coverage(N,Ps),length(Ps,L).

至于贪心启发式，放置的第二个子句可以替换为

placement(Unplaced, SoFar, Placement) :-
    integrate(min, peek_place_of_min_remain(Unplaced), (_Count,Place,Remains)),
    !, placement(Remains, [Place|SoFar], Placement).

peek_place_of_min_remain(Unplaced, (Count,Place,Remains)) :-
    select(Place, Unplaced, Places),
    remove_attacks(Place, Places, Remains),
    length(Remains, Count).
于 2013-08-02T17:42:07.113 回答