1% 4 queens
    2%
    3% Models: ((1,2),(2,4),(3,1),(4,3)) and ((1,3),(2,1),(3,4),(4,2))
    4% Retargetable N-queens program.
    5
    6nqueens(N, Q) :-
    7    nqueens(N, N, Q).
    8
    9nqueens(X, N, [q(X, Y) | T]) :-
   10    X > 0,
   11    hasqueen(X, Y, N),
   12    X1 is X - 1,
   13    nqueens(X1, N, T).
   14nqueens(0, X, []).
   15
   16hasqueen(X, Y, N) :-
   17    X > 0,
   18    pickqueen(X, Y, N),
   19    testrow(N, X, Y),
   20    testcol(N, X, Y),
   21    testdiag1(X, Y),
   22    testdiag2(X, Y, N),
   23    testdiag3(X, Y, N),
   24    testdiag4(X, Y, N).
   25hasqueen(0, Y, N).
   26
   27% pick a queen for each row, ruling out others in the row at the same time
   28pickqueen(X, Y, Y) :-
   29    Y > 0,
   30    q(X, Y).
   31pickqueen(X, Y, N) :-
   32    N > 1,
   33    N1 is N - 1,
   34    pickqueen(X, Y, N1).
   35
   36% rule out queens in same row as q(X,Y).
   37testrow(C, X, Y) :-
   38    C > 0,
   39    C \= X,
   40    not q(C, Y),
   41    C1 is C - 1,
   42    testrow(C1, X, Y).
   43testrow(C, X, Y) :-
   44    C = X,
   45    C1 is C - 1,
   46    testrow(C1, X, Y).
   47testrow(0, _, _).
   48
   49% rule out queens in same column as q(X,Y).
   50testcol(C, X, Y) :-
   51    C > 0,
   52    C \= Y,
   53    not q(X, C),
   54    C1 is C - 1,
   55    testcol(C1, X, Y).
   56testcol(C, X, Y) :-
   57    C = Y,
   58    C1 is C - 1,
   59    testrow(C1, X, Y).
   60testcol(0, _, _).
   61
   62% rule out queens in same diagonal as q(X,Y).
   63testdiag1(X, Y) :-
   64    X > 1,
   65    Y > 1,
   66    X1 is X - 1,
   67    Y1 is Y - 1,
   68    not q(X1, Y1),
   69    testdiag1(X1, Y1).
   70testdiag1(1, X) :-
   71    X \= 1.
   72testdiag1(X, 1).
   73
   74testdiag2(X, Y, N) :-
   75    X > 1,
   76    Y < N,
   77    X1 is X - 1,
   78    Y1 is Y + 1,
   79    not q(X1, Y1),
   80    testdiag2(X1, Y1, N).
   81testdiag2(1, X, N) :-
   82    X \= N.
   83testdiag2(X, N, N).
   84
   85testdiag3(X, Y, N) :-
   86    X < N,
   87    Y > 1,
   88    X1 is X + 1,
   89    Y1 is Y - 1,
   90    not q(X1, Y1),
   91    testdiag3(X1, Y1, N).
   92testdiag3(X, 1, N) :-
   93    X \= N.
   94testdiag3(N, X, N).
   95
   96testdiag4(X, Y, N) :-
   97    X < N,
   98    Y < N,
   99    X1 is X + 1,
  100    Y1 is Y + 1,
  101    not q(X1, Y1),
  102    testdiag4(X1, Y1, N).
  103testdiag4(N, Y, N) :-
  104    Y \= N.
  105testdiag4(X, N, N).
  106
  107q(X, Y) :- not negq(X, Y).
  108negq(X, Y) :- not q(X, Y).
  109
  110?- nqueens(4, Q).