# 0051. N-Queens
###### tags: `Leetcode` `Hard` `Backtracking` `DFS`
Link: https://leetcode.com/problems/n-queens/
## 思路
经典八皇后问题
不能让任何两个皇后在同一个row 同一个col 同一条对角线上
[八皇后问题讲解](https://zhuanlan.zhihu.com/p/68602868)
## Code

class Solution {
    List<List<String>> ans;
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for(char[] b:board){
            Arrays.fill(b, '.');
        }
        ans = new ArrayList<>();
        putQueens(board, 0);
        return ans;
    }
    private void putQueens(char[][] board, int row){
        int m = board.length, n = board[0].length;
        if(row==m){
            List<String> ansBoard = new ArrayList<>();
            for(int i=0; i<m; i++){
                StringBuilder sb = new StringBuilder();
                for(int j=0; j<n; j++){
                    sb.append(board[i][j]);
                }
                ansBoard.add(sb.toString());
            }
            ans.add(ansBoard);
        }
        for(int i=0; i<n; i++){
            if(isValid(board, row, i)){
                board[row][i] = 'Q';
                putQueens(board, row+1);
                board[row][i] = '.';
            }
        }
    }
    private boolean isValid(char[][] board, int row, int col){
        for(int i=0; i<row; i++){
            if(board[i][col]=='Q') return false;
        }
        for(int i=0; i<col; i++){
            if(board[row][i]=='Q') return false;
        }
        int r = row, c = col;
        while(r>=0 && c>=0){
            if(board[r][c]=='Q') return false;
            r--;
            c--;
        }
        r = row;
        c = col;
        while(r<board.length && c<board[0].length){
            if(board[r][c]=='Q') return false;
            r++;
            c++;
        }
        r = row;
        c = col;
        while(r>=0 && c<board[0].length){
            if(board[r][c]=='Q') return false;
            r--;
            c++;
        }
        r = row;
        c = col;
        while(r<board.length && c>=0){
            if(board[r][c]=='Q') return false;
            r++;
            c--;
        }
        return true;
    }
}