%%  Implementation of the NQUEENS problem.

%%  zboard just associates a variable, Ci, with each row, i.

zboard([rc(1,C1),rc(2,C2),rc(3,C3),rc(4,C4),rc(5,C5),rc(6,C6),rc(7,C7),rc(8,C8)]).

%%  zqueens(Brd) holds if none of the queens on the Board attack any other

%%  Base Case:  The board is empty... no attacks possible.

zqueens([]).

%%  Recursive Case:  Check that the queen in the first row doesn_t attack
%%    any others, and then recursively check the "rest" of the Board.

zqueens([ rc(R,C) | Rest ]) :-
  zqueens(Rest),
  member(C, [1,2,3,4,5,6,7,8]),
  zsafe(rc(R,C), Rest).

%%  zsafe(rc(R,C), RestBoard)  holds if the queen positioned at row R and column C
%%    does not attack any of the queens on the REST of the Board.

%%  Base Case:  RestBoard is empty; no queens to attack!

zsafe(rc(_R,_C), []).

%%  Recursive Case:  Check the queen in the first row of RestBoard
%%    and then recursively check the rest of RestBoard.

zsafe(rc(R,C), [ rc(R1,C1) | Rest ]) :-
  C =\= C1,
  C1 - C =\= R1 - R,
  C1 - C =\= R - R1,
  zsafe(rc(R,C), Rest).

%%  testQueens(Board) holds if Board contains a queen in each row
%%    and none of the queens attack any other.

testQueens(Board) :-
  zboard(Board),
  zqueens(Board).

%%% ==============================
%%%  Dealing with arbitrarily large boards
%%% ==============================

%%%  makeBoard makes a board containing any number of rows

makeBoard([],0).
makeBoard([rc(R,_)|Resty],R) :- 
    NextR is R-1,
    NextR >= 0,
    makeBoard(Resty,NextR).

%% makeNums(Listy,N) holds if Listy contains the numbers from N down to 1.
%%  Example:  makeNums([3,2,1], 3).

makeNums([],0).
makeNums([N|Resty],N) :-
  NextN is N-1,
  NextN >= 0,
  makeNums(Resty,NextN).

%%  yqueens(Board, Nums) holds if none of the queens on the Board attack
%%    any other.  Nums is a list of possible column numbers.

yqueens([],_).

yqueens([ rc(R,C) | Rest ], Nums) :-
  yqueens(Rest,Nums),
  member(C,Nums),
  zsafe(rc(R,C), Rest).

%% newQueens(Brd,Num) holds if Brd is a Num-by-Num chessboard with a queen
%%  in each row such that no queen attacks any other.

newQueens(Brd,Num) :-
  makeBoard(Brd,Num),
  makeNums(Nums,Num),
  yqueens(Brd,Nums).