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

%----------------------------------------
% - N Queens 

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

% ** Standard Prolog

queens_pl(N, Qs) :- 
    queens_list_pl(N, Ns),   % E.g., Ns=[4,3,2,1]
    queens_pl_(Ns, [], Qs).

queens_pl_([], Qs, Qs).      % All queens placed!
queens_pl_(Unplaced, Placed, Qs) :-
    selectq(Unplaced, Q, NewUnplaced), % E.g., Q=4, NewU=[3,2,1]
    no_attack_pl(Placed, Q, 1),        % Fail if Q attacked
    queens_pl_(NewUnplaced, [Q|Placed], Qs).  % OK -> Choose next Q

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

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

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

% Try, e.g., the following queries to better understand 
% the algorithm (also, run on the debugger): 
% ?- queens_list_pl(4,L).
% ?- selectq([4,3,2,1], Q, NewUnplaced). % Try different solutions

% Solving for N queens (can ask for more solutions):
% ?- queens_pl(4,L).
% ?- queens_pl(20,L).
% ?- queens_pl(27,L).
% ?- queens_pl(30,L).

% ** CLP(R) version

queens(N, Qs) :- 
    constrain_values(N, N, Qs),
    place_queens(N, Qs).

constrain_values(0, _N, []).
constrain_values(I, N, [X|Xs]) :-
    I .>. 0,
    X .>. 0, X .=<. N, % All queens between 0 and N
    I1 .=. I - 1,
    constrain_values(I1, N, Xs), no_attack(Xs, X, 1).

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

place_queens(0, _).
place_queens(N, Q) :- 
    N .>. 0, 
    memberq(N, Q), 
    N1 .=. N - 1, 
    place_queens(N1, Q).

memberq(X, [X|_]).
memberq(X, [_|Xs]) :- memberq(X, Xs).

% Solving for N queens (can ask for more solutions):
% ?- queens(4,Qs).
% ?- queens(20,Qs).
% -> This CLP(R) solution does not speed up w.r.t. the 
%    standard Prolog one. 
% -> This problem is more suited to finite domain constraints.

% Try, e.g., the following queries to better understand the code:
% ?- queens(4, Qs).
% ?- memberq(4, [A, B, C, D]).
% ?- place_queens(0, L).
% ?- constrain_values(4, 4, Qs).
% ?- constrain_values(4, 4, Qs), Qs = [3,1|OQs].
% Bad state rejected using constraint (in)consistency: 
% ?- constrain_values(4, 4, Qs), Qs = [3,2|OQs].