% nqueens(N,BOARD) takes an integer N and returns a solution to the N-queens
% problem on an N * N board. A board is represented as a list of pairs
% [ROW, COL]. For example, the board [[4,3], [3,1], [2,4], [1,2]] represents
% the board --- --- Q ---
% Q --- --- ---
% --- --- --- Q
% --- Q --- ---
% a solution to the 4-queens problem.
nqueens(N,BOARD) :- nqueens1(N,N,BOARD).
% nqueens1(N,K,BOARD): Given integers N and K < N, bind BOARD to be the
% a K * N board with K queens. This works by recurring on K. First
% recursively find a K-1 * N board, then place the Kth queen in a safe
% square in the Kth row.
nqueens1(N,0,[]).
nqueens1(N,K, [[K,COL] | BOARD]) :-
K > 0,
K1 is K - 1,
nqueens1(N, K1, BOARD),
pick-int(COL,1,N),
free-square([K,COL], BOARD).
% pick-int(I,BOT,TOP) non-deterministically binds I to be some integer between
% BOT and TOP. That is, it first succeeds with I = BOT; then with I = BOT + 1;
% and so on until succeeding with I = TOP.
pick-int(BOT,BOT,TOP).
pick-int(I,BOT,TOP) :-
BOT < TOP,
B1 is BOT + 1,
pick-int(I,B1,TOP).
% free-square(SQ,BOARD) succeeds if square SQ is free from attack from
% the queens in BOARD. It checks each square of BOARD in turn.
free-square(SQ1, []).
free-square(SQ1, [SQ2 | BOARD]) :-
\+attacks(SQ1,SQ2), free-square(SQ1, BOARD).
% attacks(SQ1,SQ2) computes whether square SQ1 attacks SQ2.
attacks([R,_],[R,_]). % Same row. Never actually occurs in this code.
attacks([_,C],[_,C]). % Same column.
attacks([R1,C1], [R2,C2]) :- % Diagonal: Up-left -> Down-right
0 is (R1 + C1) - (R2 + C2).
attacks([R1,C1], [R2,C2]) :- % Diagonal: Down-left -> Up-right
0 is (R1 - C1) - (R2 - C2).