Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import java.util.ArrayList;
public class NQueens {
public ArrayList<String[]> solveNQueens(int n) {
ArrayList<String[]> result = new ArrayList<String[]>();
String[][] board = new String[n][n];
int[][] boardStatus = new int[n][n];
solveNQueens(result, board, boardStatus, 0, n);
return result;
}
private void solveNQueens(ArrayList<String[]> result, String[][] board,
int[][] boardStatus, int level, int n) {
if (level == n) {
result.add(getBoardString(board, n));
return;
}
for (int i = 0; i < n; i++) {
if (boardStatus[level][i] == 0) {
board[level][i] = "Q";
updateBoardStatus(level, i, boardStatus, n, false); // be sure to update the cell (level, i) correctly
solveNQueens(result, board, boardStatus, level + 1, n);
// undo
board[level][i] = null;
updateBoardStatus(level, i, boardStatus, n, true);
}
}
}
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; // j++ on this row only!!! I made a mistake using j++ on both rows, stuipd me.
}
boardStatus[level][i] -= change; // we updated twice to this cell in the loop above so we need to correct it
// 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;
}
private String[] getBoardString(String[][] board, int n) {
String[] boardStr = new String[n];
for (int i = 0; i < n; i++) {
StringBuilder builder = new StringBuilder();
for (int j = 0; j < n; j++) {
if (board[i][j] != null)
builder.append("Q");
else
builder.append(".");
}
boardStr[i] = builder.toString();
}
return boardStr;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment