% 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).