public class main { private int[][] board; private int[] curRow; private int count; private int size; public void solveNQueensHelper(int size) { this.size = size; this.count = 0; board = new int[size][size]; curRow = new int[size]; for (int i = 0; i < size; i++) { curRow[i] = -1; } } public void solveNQueens() { System.out.println(board.length); for (int column = 0; column <= board.length;) { int row = getNextRow(column); if (row == -1) { if (column == 0 && getCurRow(column) == size - 1) { // WE END HERE return; } // means next not possible in this column // go back and try (backtracking) // also remove the Queen from this column if (curRow[column] != -1) { board[curRow[column]][column] = 0; } curRow[column] = -1; column--; continue; } // if all ok then put the Queen at this position if (curRow[column] != -1) board[curRow[column]][column] = 0; board[row][column] = 1; curRow[column] = row; // if we just filled up the last queen successfully print the board // and go back if (column == size - 1) { count++; printBoard(board); // clear off board[row][column] = 0; curRow[column] = -1; column--; continue; } column++; } } public int getNextRow(int col) { // see first the next row to attempt int nextRow = getCurRow(col) + 1; if (nextRow >= size) return -1; for (int i = nextRow; i < size; i++) { // check for validity if (isValid(i, col)) { return i; } } // return -1 when no next row is found return -1; } public int getCurRow(int col){ //return the current row for the column return curRow[col]; } public boolean isValid(int row, int column) { // check left for (int i = 0; i < column; i++) { int j = curRow[i]; if (j == row) { return false; } // check diagonal if (Math.abs(row - j) == Math.abs(column - i)) { return false; } } return true; } public void printBoard(int[][] board) { System.out.println("============================="); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { System.out.print("[" + board[i][j] + "]"); } System.out.println(); } System.out.println("============================="); } public int getCount() { return count; } /** * @param args */ public static void main(String[] args) { main ch9_9 = new main(); ch9_9.solveNQueensHelper(8); ch9_9.solveNQueens(); System.out.println("Number of Backtracks:"+ch9_9.getCount()); } }