# N-Queen

N-Queen problem is a typical recursion problem. Note that we use an int array which each element stands for where the queen is at each row on the board. We also use a boolean array used to mark which column has alread has a queen so that skip checking on the board state to save time.

To output every possible configuration:

public class NQueen {
private List<String> buildBoard(int[] config) {
ArrayList<String> board = new ArrayList<String>(config.length);
for (int i = 0; i < config.length; i++) {
StringBuilder line = new StringBuilder();

for (int j = 0; j < config.length; j++) {
if (j == config[i]) line.append('Q');
else line.append('.');
}

}
return board;
}

private boolean checkValid(int[] config, int pos, int i) {
for (int j = 0; j < pos; j++) {
if (Math.abs(config[j] - i) == Math.abs(j - pos)) return false;
}
return true;
}

private void solveNQueue(int[] config, boolean[] used, int pos, List<List<String>> result) {
if (pos >= config.length) {
return;
}

for (int i = 0; i < config.length; i++) {
if (used[i]) continue;

if (checkValid(config, pos, i)) {
config[pos] = i;
used[i] = true;
solveNQueue(config, used, pos + 1, result);
used[i] = false;
}
}
}

public List<List<String>> solveNQueens(int n) {
ArrayList<List<String>> result = new ArrayList<List<String>>();
int[] config = new int[n];
boolean[] used = new boolean[n];
solveNQueue(config, used, 0, result);
return result;
}
}


To output how many configurations are possible in total:

public class NQueenII {
private boolean checkValid(int[] config, int pos, int i) {
for (int j = 0; j < pos; j++) {
if (Math.abs(config[j] - i) == Math.abs(j - pos)) return false;
}
return true;
}

private int totalNQueens(int[] config, boolean[] used, int pos) {
if (pos >= config.length) return 1;

int count = 0;

for (int i = 0; i < config.length; i++) {
if (used[i]) continue;

if (checkValid(config, pos, i)) {
config[pos] = i;
used[i] = true;
count += totalNQueens(config, used, pos + 1);
used[i] = false;
}
}

return count;
}

public int totalNQueens(int n) {
int[] config = new int[n];
boolean[] used = new boolean[n];