Instantly share code, notes, and snippets.

# jingz8804/NQueensII.java Last active Aug 29, 2015

Follow-up question for NQueens here: http://jznest.wordpress.com/2014/05/10/n-queens/
 public class NQueensII { public int totalNQueens(int n) { int num = 0; int[][] boardStatus = new int[n][n]; // use Integer object and void is a bad move. It seems the reference is not working. // we probably need to wrap it in another object? // in fact Integer is not necessary. We only increase the counter in the base case. num = solveNQueens(num, boardStatus, 0, n); return num; } private int solveNQueens(Integer num, int[][] boardStatus, int level, int n) { if (level == n) return ++num; for (int i = 0; i < n; i++) { if (boardStatus[level][i] == 0) { updateBoardStatus(level, i, boardStatus, n, false); // as well num = solveNQueens(num, boardStatus, level + 1, n); // undo updateBoardStatus(level, i, boardStatus, n, true); } } return num; } private void updateBoardStatus(int level, int i, int[][] boardStatus, int n, boolean isUndo) { int change = isUndo ? -1 : 1; int j = 0; while (j < n) { boardStatus[level][j] += change; boardStatus[j++][i] += change; } boardStatus[level][i] -= change; // we updated twice to this cell in the loop above // update the cross int k = level; int m = i; while (--k >= 0 && --m >= 0) boardStatus[k][m] += change; k = level; m = i; while (++k < n && ++m < n) boardStatus[k][m] += change; k = level; m = i; while (++k < n && --m >= 0) boardStatus[k][m] += change; k = level; m = i; while (--k >= 0 && ++m < n) boardStatus[k][m] += change; } }