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;}
}