
uniqSols(N, S, C) :- allSols(N, X), removeImages(N, X, S), len(S, C).

allSols(N, B) :- 
  rows(N, 1, R),
  bagof(X, solution(N, R, X, _), B).

rows(N, N, [N])     :- !.
rows(N, I, [I | L]) :- J is I + 1, rows(N, J, L).

len([], 0).
len([_ | L], N) :- len(L, M), N is M + 1.

% Solution of 8 queens, proper...

safe(_, _, []).
safe(Col, Row, [queen(ThreatCol, ThreatRow) | List]) :-
    ThreatDiagU is ThreatCol - ThreatRow + Row,
    Col \== ThreatDiagU,
    ThreatDiagD is ThreatCol + ThreatRow - Row,
    Col \== ThreatDiagD,
    safe(Col, Row, List).
  
solution(0, Rows, [], Rows) :- !.
solution(N, Rows, [queen(N, Row) | List], UnusedRows) :-
    M is N - 1,
    solution(M, Rows, List, FreeRows),
    select(FreeRows, Row, UnusedRows),
    safe(N, Row, List).

select([X | L], X, L).
select([X | L], Y, [X | M]) :- select(L, Y, M).

% Remove redundant symmetry images from list

removeImages(_, [], []).
removeImages(N, [X | Tail], [X | NewTail]) :-
    images(N, X, Images),
    subtract(Tail, Images, TailMinusImages),
    removeImages(N, TailMinusImages, NewTail).

% ``Normalised'' (sorted into reverse column order) list of boards obtained
% by symmetry ops.  (Called with N as 1st arg, `normalise' works
% iff the columns in the queens are a permutation of 1..N).

images(N, X0, [I0, I1, I2, I3, I4, I5, I6, I7]) :-
    normalise(N, X0, I0),
    rotate(N, X0, X1), normalise(N, X1, I1),
    rotate(N, X1, X2), normalise(N, X2, I2),
    rotate(N, X2, X3), normalise(N, X3, I3),
    reflect(N, X0, Y0), normalise(N, Y0, I4),
    rotate(N, Y0, Y1), normalise(N, Y1, I5),
    rotate(N, Y1, Y2), normalise(N, Y2, I6),
    rotate(N, Y2, Y3), normalise(N, Y3, I7).

normalise(_, [], []) :- !.
normalise(N, List, [queen(N, R) | Tail]) :-
    remove(queen(N, R), List, Rest),
    M is N - 1,
    normalise(M, Rest, Tail).

rotate(_, [], []).
rotate(N, [queen(C, R) | L], [queen(CNew, C) | M]) :-
    CNew is N + 1 - R,
    rotate(N, L, M).

reflect(_, [], []).
reflect(N, [queen(C, R) | L], [queen(R, C) | M]) :- reflect(N, L, M).

% ``Set'' operations...

subtract(M, [], M).
subtract(M, [X | I], N) :- remove(X, M, P), subtract(P, I, N).
 
remove(_, [], []).
remove(X, [X | L], L)       :- !.
remove(X, [Y | L], [Y | M]) :- remove(X, L, M).
 
