N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

public class Test34 {
    public static void main(String[] args) {
        System.out.println(solveNQueens(4));
    }
    static List<List<String>> returnList = new ArrayList<>();
    public static List<List<String>> solveNQueens(int n) {
        char[][] broad = new char[n][n];
        for (int i = 0; i < broad.length; i++) {
            for (int j = 0; j < broad[i].length; j++) {
                broad[i][j] = '.';
            }
        }
        backtrack(broad, 0);
        return returnList;

    }
    private static void backtrack(char[][] broad, int colIndex) {
        if (colIndex == broad.length) {
            returnList.add(construct(broad));
        }

        for (int rowIndex = 0; rowIndex < broad.length; rowIndex++) {
            if (validate(broad, rowIndex, colIndex)) {
                broad[rowIndex][colIndex] = 'Q';
                backtrack(broad, colIndex + 1);
                //前一列找到位置，colIndex+1，继续定位下一列。
                broad[rowIndex][colIndex] = '.';
            }
        }
    }
    private static boolean validate(char[][] broad, int i, int colIndex) {
        for (int x = 0; x < broad.length; x++) {
            for (int y = 0; y < colIndex; y++) {
                /**
                 * x ==i 是水平方向
                 * x + colIndex = i +y  是斜左上角
                 * x + y = colIndex + i 是斜左下角
                 */
                if (broad[x][y] == 'Q' && (x == i || x + colIndex == i + y || x + y == i + colIndex)) {
                    return false;
                }
            }
        }
        return true;
    }
    private static List<String> construct(char[][] broad) {
        List<String> list = new LinkedList<>();
        for (int i = 0; i < broad.length; i++) {
            String s = new String(broad[i]);
            list.add(s);
        }
        return list;
    }

}