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