Skip to content

Instantly share code, notes, and snippets.

@jingz8804
Last active August 29, 2015 14:01
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jingz8804/b7c2b10fceae660e73c0 to your computer and use it in GitHub Desktop.
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment