52. N皇后 II

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

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

示例:
输入: 4
输出: 2

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

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

提示：

• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

方法(回溯法)

因为在每一行都有在0到n-1中的哪一列放皇后这n种选择，进行完这次选择之后，在下一行又会面临同样的选择，因此考虑用回溯法。

回溯法需要考虑三件事：路径、选择、结束条件：

• 路径：也即棋盘（只有经过的行放好了皇后）
• 选择：该行的n个位置，除了与其他皇后有冲突的位置，剩下的位置都可以作为放皇后的选择。
• 结束条件：棋盘上所有的行都已经放好了皇后

代码

class Solution {
    int res = 0;
    public int totalNQueens(int n) {
        //构建并初始化象棋棋盘,初始化时所有位置都没有皇后
        String[][] board = new String[n][n];
        for (String[] strings : board) 
            Arrays.fill(strings, ".");
        backtrack(board, 0);
        return res;
    }

    public void backtrack(String[][] board, int row) {
        //结束条件
        if (board.length == row) {
            res++;
            return;
        }
        for (int col = 0; col < board[row].length; col++) {
            //剪枝:如果board[row][col]不能放置皇后，则跳过
            if (!isValid(board, row, col)) 
                continue;
            //做选择
            board[row][col] = "Q";
            //进入下一行
            backtrack(board, row + 1);
            //撤销选择
            board[row][col] = ".";
        }
    }

    //判断是否可以在board[row][col]处放置皇后
    //注：任何两个皇后都不能处于同一条横行、纵行或斜线上。
    //由于我们在做选择时，每一横行只放了一个皇后，因此只需要判断纵行和斜线即可。
    public boolean isValid(String[][] board, int row, int col) {
        //因为我们从上到下在每一行上放置皇后，因此只需要考虑小于row的行上有没有皇后冲突即可。
        //检查同一列是否有皇后冲突
        for(int i = row - 1; i >= 0; i--){
            if(board[i][col].equals("Q"))
                return false;
        }
        //检查左上的斜线上有没有皇后冲突
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if(board[i][j].equals("Q"))
                return false;
        }
        //检查右上的斜线上有没有皇后冲突
        for(int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++){
            if(board[i][j].equals("Q"))
                return false;
        }
        return true;
    }

51.N皇后

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

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

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

示例：
输入：4
输出：[
[".Q..",  // 解法 1
"...Q",
"Q...",
"..Q."],

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

提示：

• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

方法（回溯法）

方法大体与上一道题相同，只是输出不同。具体见以下代码。

代码

class Solution {
    private int n;
    private List<List<String>> result = new LinkedList<>();
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        //构建并初始化象棋棋盘,初始化时所有位置都没有皇后
        String[][] board = new String[n][n];
        for (String[] strings : board) 
            Arrays.fill(strings, ".");
        backtrack(board, 0, result);
        return result;
    }
    public void backtrack(String[][] board, int row, List<List<String>> result) {
        //结束条件
        if (board.length == row) {
            List<String> list = new LinkedList<>();
            for(int i = 0; i < board.length; i++){
                String temp = "";
                for(int j = 0; j < board[0].length; j++)
                    temp += board[i][j];
                list.add(temp);
            }
            result.add(list);
            return;
        }
        for (int col = 0; col < board[row].length; col++) {
            //剪枝:如果board[row][col]不能放置皇后，则跳过
            if (!isValid(board, row, col)) 
                continue;
            //做选择
            board[row][col] = "Q";
            //进入下一行
            backtrack(board, row + 1, result);
            //撤销选择
            board[row][col] = ".";
        }
    }

    public boolean isValid(String[][] board, int row, int col) {
        //检查同一列是否有皇后冲突
        for(int i = row - 1; i >= 0; i--){
            if(board[i][col].equals("Q"))
                return false;
        }
        //检查左上的斜线上有没有皇后冲突
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if(board[i][j].equals("Q"))
                return false;
        }
        //检查右上的斜线上有没有皇后冲突
        for(int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++){
            if(board[i][j].equals("Q"))
                return false;
        }
        return true;
    }
}