1% 4-queens
    2%
    3% Retargetable N-queens program.
    4% Models ((1,2),(2,4),(3,1),(4,3)) and ((1,3),(2,1),(3,4),(4,2))
    5
    6nqueens(N, Q) :-
    7    nqueens(N, N, [], Q).
    8
    9% Pick queens one at a time and test against all previous queens.
   10nqueens(X, N, Qi, Qo) :-
   11    X > 0,
   12    pickqueen(X, Y, N),
   13    not attack(X, Y, Qi),
   14    X1 is X - 1,
   15    nqueens(X1, N, [q(X, Y) | Qi], Qo).
   16nqueens(0, _, Q, Q).
   17
   18
   19% pick a queen for row X.
   20pickqueen(X, Y, Y) :-
   21    Y > 0,
   22    q(X, Y).
   23pickqueen(X, Y, N) :-
   24    N > 1,
   25    N1 is N - 1,
   26    pickqueen(X, Y, N1).
   27
   28% check if a queen can attack any previously selected queen.
   29attack(X, _, [q(X, _) | _]). % same row
   30attack(_, Y, [q(_, Y) | _]). % same col
   31attack(X, Y, [q(X2, Y2) | _]) :- % same diagonal
   32    Xd is X2 - X,
   33    abs(Xd, Xd2),
   34    Yd is Y2 - Y,
   35    abs(Yd, Yd2),
   36    Xd2 = Yd2.
   37attack(X, Y, [_ | T]) :-
   38    attack(X, Y, T).
   39
   40q(X, Y) :- not negq(X, Y).
   41negq(X, Y) :- not q(X, Y).
   42
   43abs(X, X) :- X >= 0.
   44abs(X, Y) :- X < 0, Y is X * -1.
   45
   46?- nqueens(4, Q).