Queens Domination

Question

Queen Domination Given an n×n board, the domination number is the minimum number of queens (or other pieces) needed to attack or occupy every square. For n=8 the queen's domination number is 5. write a predicate slution(N),to get the minimum number of queens needed to cover all squares.

Answer 1

here is a dumb 'all solutions' snippet:

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(_, [], []).

As usual in permutation problems, that code is hopeless inefficient:

?- 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

Of course, storing all lists is a real waste.

?- 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] 

instead of select/3 you should apply an appropriate heuristic. An easy one could be greedy selection...

edit

here is integrate:

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 is a SWI-Prolog builtin, arg/3 an ISO. If your Prolog miss them, you should replace - for instance - with assert/retract.

Integrate takes a predicate, and call it with the additional argument to be compared with the stored current minimum: here it is:

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

as for the greedy heuristic, the second clause of placement could be replaced by

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