The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
N皇后问题是一个经典的算法问题，求N×N的国际象棋棋盘上能摆放多少个皇后，且她们之间不相互攻击，要输出所有可能的摆法。皇后的攻击范围是同一行、同一列以及同在两条45°斜线上的棋子。
解本题的关键是选择一个合适的数据结构来记录放皇后的位置，还要方便检验各个位置是否冲突。使用x和y坐标来记录位置是最直接的，然而保存两个数要用额外的数据结构才行（特殊情况可以用一个int打包），记录下来后判断位置是否冲突也比较麻烦。
经过思考，使用一个int[N]数组来保存皇后的位置是最合适的。数组下标代表y坐标，数组中的数0～N-1代表x坐标。这样保证y坐标不会重复（不会在同一行），判断x坐标是否重复只要遍历数组看是否有重复数字，判断是否在同一斜线也很方便：假设当前位置是int[yi]=xi，从当前位置向前移动，判断 (int[yi-1]==xi+1 || int[yi-1]==xi-1), (int[yi-12]==xi+2 || int[yi-2]==xi-2)...即可。
解决了数据结构和位置检查的问题，剩下的算法就很简单：从位置0开始，检查当前位置能放0～N-1中的哪个数，如果能放且是最后一个数，就把数组转换一下输出，如果没到最后一个数，就对下一个位置递归计算。
代码如下，本算法击败了98％的java算法。
public static List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
int[] a = new int[n];
solveNQueens(res, a, 0);
return res;
}
public static void solveNQueens(List<List<String>> res, int[] a, int pos) {
int n = a.length;
for(int j = 0; j < n; j++) {
if(check(a, pos, j)) {
a[pos] = j;
if(pos == n - 1) { // save
char[][] board = new char[n][n];
for(char[] b : board) {
Arrays.fill(b, '.');
}
List<String> list = new ArrayList<>();
for(int i = 0; i < n; i++) {
board[i][a[i]] = 'Q';
list.add(new String(board[i]));
}
res.add(list);
} else solveNQueens(res, a, pos + 1);
}
}
}
public static boolean check(int[] a, int pos, int j) {
for(int k = pos - 1; k >= 0; k--) {
if(a[k] == j) return false;
}
for(int k = pos - 1; k >= 0; k--) {
int diff = pos - k;
if(a[k] == j + diff || a[k] == j - diff) return false;
}
return true;
}
