女王統治

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