:- module(_,_).
:- use_package(clpfd).

% -------------------------------------------------------------------
% - N Queens in CLP(fd)

% We represent the state as a list holding in which column the queen
% is placed for each row. E.g., for 4 queens:
% 
% -----------------
% |   | Q |   |   | 
% -----------------
% |   |   |   | Q | 
% -----------------
% | Q |   |   |   | 
% -----------------
% |   |   | Q |   | 
% -----------------
%
% is represented as [2, 4, 1, 3]

% General idea: from a partial solution, non-deterministically
% select a new queen, check safety of new queen against those
% already placed, if OK add new queen to partial solution and 
% contine, otherwise backtrack to the selection and choose
% another possible queen.

% ** CLP(fd) version

queens_fd(N, Qs, Type) :-
        constrain_values(N, N, Qs),
        all_different(Qs),  % built-in constraint
        labeling(Type,Qs).

constrain_values(0, _N, []).
constrain_values(N, Range, [X|Xs]) :-
        N > 0, N1 is N - 1, X in 1 .. Range,
        constrain_values(N1, Range, Xs), no_attack(Xs, X, 1).

no_attack([], _Queen, _Nb).
no_attack([Y|Ys], Queen, Nb) :-
        Queen #\= Y + Nb, Queen #\= Y - Nb, Nb1 is Nb + 1,
        no_attack(Ys, Queen, Nb1).

% Queries:
% ?- time(queens_fd(20, Q, [ff])).
% ?- time(queens_pl(20,Q)).
% ?- time(queens_fd(100, Q, [ff])). 
% ?- time(queens_pl(100,Q)).
% (Takes a long time...)
% -> CLP(fd) very good at finding a solution!

% What about finding all solutions?
fd_all(N,L) :- findall(X, queens_fd(N,X,[ff]),S), length(S,L).
pl_all(N,L) :- findall(X, queens_pl(N,X),S),      length(S,L).

% ?- time(pl_all(11, L)).
% ?- time(fd_all(11, L)).
% ?- time(pl_all(12, L)).
% ?- time(fd_all(12, L)).
% ?- time(pl_all(13, L)).
% ?- time(fd_all(13, L)).
% -> CLP(fd) (at least this program) not so good for all solutions!

% - The standard Prolog version

queens_pl(N, Qs) :- 
	queens_pl_list(N, Ns), 
	queens_pl_(Ns, [], Qs).

queens_pl_([], Qs, Qs).
queens_pl_(Unplaced, Placed, Qs) :-
    selectq(Unplaced, Q, NewUnplaced), 
    pl_no_attack(Placed, Q, 1),
    queens_pl_(NewUnplaced, [Q|Placed], Qs).

pl_no_attack([], _Queen, _Nb).
pl_no_attack([Y|Ys], Queen, Nb) :-
    Queen =\= Y + Nb, Queen =\= Y - Nb, Nb1 is Nb + 1,
    pl_no_attack(Ys, Queen, Nb1).

selectq([X|Ys], X, Ys).
selectq([Y|Ys], X, [Y|Zs]) :- selectq(Ys, X, Zs).

queens_pl_list(0, []).
queens_pl_list(N, [N|Ns]) :- N > 0, N1 is N - 1, queens_pl_list(N1, Ns).