51. N 皇后

一 题目：

二 思路：

皇后要求：同行，同列，同一斜线只有一个
那么我们可以按照回溯的方式进行
且：我们可以按照行进行从上到下的推进，一行只安排一个

按照题意我们需要检查八个方向是否有其他方向，但实际上我们只需要检查三个方向即可。
因为我们的逻辑是每一行只放一个皇后，所以这个皇后的左边和右边不需要进行检查了。
因为我们是一行一行从上向下放置皇后，所以下方，左下方和右下方不会有皇后（还没放皇后）。
最后我们需要检查的只有上方、左上和右上三个方向

三 代码：

class Solution {
    List<List<String>> res = new ArrayList<>();

    /* 输入棋盘的边长n，返回所有合法的放置 */
    public List<List<String>> solveNQueens(int n) {
        // "." 表示空，"Q"表示皇后，初始化棋盘
        char[][] board = new char[n][n];
        //都预填空值.
        for (char[] c : board) {
            Arrays.fill(c, '.');
        }
        search(board,0);
        return res;

    }

    private void search(char[][] board, int row) {
        //其实题目可以改成，在每一行放置一个皇后，让这些皇后不能相互攻击。（因为每一行最多只有一个皇后）
        // 每一行都成功放置了皇后，记录结果
        if (row==board.length){
            res.add(charToList(board));
            return;
        }

        int c=board[row].length;
        for (int col = 0; col < c; col++) {
            //判断是否可以再(row,c)位置放置点
            if (!isValid(board,row,col)){
                continue;
            }

            //如果该列可以放
            board[row][col]='Q';
            search(board,row+1);
            //复原
            board[row][col]='.';
        }

    }

    /**
     * 按照题意我们需要检查八个方向是否有其他方向，但实际上我们只需要检查三个方向即可。
     * 因为我们的逻辑是每一行只放一个皇后，所以这个皇后的左边和右边不需要进行检查了。
     * 因为我们是一行一行从上向下放置皇后，所以下方，左下方和右下方不会有皇后（还没放皇后）。
     * 最后我们需要检查的只有上方、左上和右上三个方向
     */
    private boolean isValid(char[][] board, int row, int col) {
        //同一列同一行不能靠近
        int n=board.length;

        //检查列上是否有皇后冲突（不同行）
        for (int i =0 ; i <n ; i++) {
            //如果列上有其他皇后
            if (board[i][col]=='Q'){
                return false;
            }
        }

        //检查左上是否有其他皇后(行列都减)
        for (int i = row-1,j=col-1; i >= 0&&j>=0; i--,j--) {
           if (board[i][j]=='Q'){
               return false;
           }
        }

        //检查右上是否有其他皇后(行列都减)
        for (int i = row-1,j=col+1; i >= 0&&j<n; i--,j++) {
            if (board[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }

    public List charToList(char[][] board) {
        List<String> list = new ArrayList<>();

        for (char[] c : board) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }
}