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('.');
}
board.add(line.toString());
}
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) {
result.add(buildBoard(config));
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];
return totalNQueens(config, used, 0);
}
}