N-Queens

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.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
[".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

N皇后的问题，典型的用回溯法解决的NP问题，用循环递归来处理。从第0行开始，我们创建一个长度为n的数组colInRow[]，数组的下标代表行，数组中的元素代表对应行中皇后在列上的位置，例如colInRow[2] = 3, 代表第2行第三列的位置有皇后。每一次递归我们都将一个皇后放在对应行中的某一列中，如果递归到了第n行，我们就将这个结果放入结果集中。在往前寻找的时候，我们要判断加入皇后的位置是否合法，也就是在同一行同一列还有斜对角线上只能有一个皇后，同一行上肯定有只有一个皇后，因为我们递归每一行时，只加一个皇后，如果合法就递归下一行，所以我们只需要检查同一列和同一斜对角线上是否合法。对于同一列上，我们只需要比较当前行之前的行中在这一列是否有皇后即可；对于斜对角线上，符合一个规律|colInRow[i] - colInRow[row] |==  row - i , 其中i < row， 满足这个条件都在一个对角线上。代码如下：

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<List<String>>();
        int[] colInRow = new int[n];
        solveNQueens(0, n, colInRow, result);
        return result;
    }
    private void solveNQueens(int row, int n, int[] colInRow, List<List<String>> result) {
        if(row == n) {
            printBoard(n, colInRow, result);
            return;
        } else {
            for(int i = 0; i < n; i++) {
                colInRow[row] = i;
                if(isValid(row, colInRow)) {
                    solveNQueens(row + 1, n, colInRow, result);
                }
            }
        }
    }
    private boolean isValid(int row, int[] colInRow) {
        for(int i = 0; i < row; i++) {
            if(colInRow[i] == colInRow[row] || Math.abs(colInRow[i] - colInRow[row]) == row - i)
                return false;
        }
        return true;
    }
    
    private void printBoard(int n, int[] colInRow, List<List<String>> result) {
        List<String> list = new ArrayList<String>();
        for(int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < n; j++) {
                if(j == colInRow[i])
                    sb.append("Q");
                else
                    sb.append(".");
            }
            list.add(sb.toString());
        }
        result.add(list);
    }
}