女王统治

Question

女王统治 给定一个n×n板，统治数量是攻击或占领每个方块所需的皇后（或其他棋子）的最小数量。对于n = 8，女王的统治数字为5. 编写谓词解析（N），以获得覆盖所有方块所需的最小皇后数。

Answer 1

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

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来取代 - 比如说。

集成需要谓词，并且与附加的参数调用它与所存储的当前最小进行比较：这里是：

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).