LeetCode Hot100 51.N皇后

题目：

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

思路：

class Solution {
    private int n;
    private int[] col;
    private List<List<String>> ans = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        col = new int[n];
        dfs(0);
        return ans;
    }

    private void dfs(int r) {
        if (r == n) { // 所有皇后放好了
            List<String> tmp = new ArrayList<>();
            for (int i : col) {
                char[] row = new char[n];
                Arrays.fill(row, '.');
                row[i] = 'Q';
                tmp.add(new String(row));
            }
            ans.add(tmp);
            return;
        }
        for (int c = 0; c < col.length; c++) {
            if (valid(r, c)) {
                col[r] = c;
                dfs(r + 1);
            }
        }
    }

    private boolean valid(int r,int c) {
        for (int R = 0; R < r; R++) {
            int C = col[R];
            if ((c == C) || ((R + C) == (r + c) || (R - C) == (r - c)))
                return false;
        }
        return true;
    }
}