%%% Exercise 4: Efficient solution

%%% nqueens(N,Qs) succeeds if Qs is a list of N integers representing a
%%% solution to the N-Queens problem:  If the ith element of Qs is j, then
%%% a Queen is placed on square (i,j)
    
nqueens(N, Qs) :- fast_queens(N, N, Qs).

%%% fast_queens(N,K,Queens) succeeds if Queens is list of K (<= N) integers 
%%% representing a partial solution (K Queens) of the N-Queens problem.

fast_queens(N, 1, [Q]) :- pos(Q, N).  % One Queen, 
                                      % place it anywhere between 1-N

fast_queens(N, M, [Q|Qs]) :- 
                     M1 is M - 1, M1 > 0, 
                     fast_queens(N, M1, Qs), %Place (M-1) Queens on board
                     pos(Q, N),              %Place the M Queen on board
                     safe(Q, 1, Qs).         %See if this Queen can attack
                                             %any of the other Queens

%%% pos(K,N) succeeds if K is a number between 1 and N

pos(N, N).
pos(K, N) :- N1 is N - 1, N1 > 0, pos(K, N1).

%%% safe(Q,N,Qs) succeeds if Q cannot attack any of the Queens in Qs.  The
%%% integer N represents the number of rows separating Q and the first
%%% element of Qs (used for computing diagonal attacks).

safe(_, _, []).  % Qs is empty, so we always succeed

safe(Q, N, [Q1|Qs]) :- noattack(Q, N, Q1),  % check that Q cannot attack Q1
                      N1 is N + 1,
                      safe(Q, N1, Qs).      % check that Q cannot attack
                                            % remaining Queens

%%% noattack(Q,N,Q1) succeeds if Queen Q cannot attack Q1.  N is the number
%%% of rows separating the Queends

noattack(Q, N, Q1) :- not(Q = Q1),         % Not is same column
                  X is Q1 - N, not(Q = X), % Not along one diagonal
                  Y is Q1 + N, not(Q = Y). % Not along the other diagonal

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
