// Generate all possible solutions to the N queens problem.
// The board is represented by board[1:N], which records
// for each column whether there is a queen in that column,
// and if so, which row it occupies.  In particular,
//   board[j] = i if there is a queen in row i of column j
//            = 0 otherwise

class nQueens {
   static int N = 8;
   static int solution = 0;

   static boolean safe(int row, int column, int board[]) {
//  Check whether it is safe to place a queen at row, column;
//    i.e., is board[column]=row a safe configuration?
      for (int j=1; j<column; j++) {
         if (board[column-j] == row   ||
             board[column-j] == row-j ||
             board[column-j] == row+j) {
            return false;
         }
      }
      return true;
   }

   static void place(int column, int board[]) {
//  Place a queen in all safe positions of column c,
//  then try placing a queen in the next column.
//  If a position in column N is safe, print the board.
      for (int row = 1; row <= N; row++) {
         board[column] = row;
         if (safe(row, column, board)) {
            if (column==N) solution++;      // we have a solution
            else place(column+1, board);    // try next column
         }
      board[column] = 0;                    // unrecord that a queen was placed
      }
   }

   public static void main(String args[]) {
      System.out.println("nQueens loaded");
      try {
         N = Integer.parseInt(args[0]);
      } catch (ArrayIndexOutOfBoundsException e) {
      } catch (NumberFormatException e) {
      }
      System.out.println("nQueens: N=" + N);
      int board[] = new int[N+1];          // N+1 since need board[1]...board[N]
      place(1, board);
      System.out.println("nQueens: solution=" + solution);
      System.out.println("nQueens done");
   }
}

/* ............... Example compile and run(s)

% time ./SRqueens 8
Solutions to the 8 queens problem:
There are 92 solutions.

real        1.8
user        1.6
sys         0.2
% /homeb/shartley/Java/java/bin/javac nQueens.java
% time /homeb/shartley/Java/java/bin/java nQueens 8
nQueens loaded
nQueens: N=8
nQueens: solution=92
nQueens done

real        3.2
user        1.7
sys         1.3
% time ./SRqueens 9
Solutions to the 9 queens problem:
There are 352 solutions.

real        7.5
user        7.3
sys         0.1
% time /homeb/shartley/Java/java/bin/java nQueens 9
nQueens loaded
nQueens: N=9
nQueens: solution=352
nQueens done

real        7.7
user        6.2
sys         1.1
% time ./SRqueens 10
Solutions to the 10 queens problem:
There are 724 solutions.

real       36.5
user       36.3
sys         0.2
% time /homeb/shartley/Java/java/bin/java nQueens 10
nQueens loaded
nQueens: N=10
nQueens: solution=724
nQueens done

real       31.3
user       29.7
sys         1.2
                                              */