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



上图为 8 皇后问题的一种解法。

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

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

示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 

package Leetcode;

import java.util.ArrayList;
import java.util.List;

public class n皇后3刷 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        if (n == 0) return res;
        dfs(res, new ArrayList<>(),0,n);
        return res;
    }
    private static void dfs(List<List<String>> res, List<String> list, int row, int n) {
        if (row == n && list.size() == n) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isValid(list,i,n)) {
                list.add(generateQ(i,n));
                dfs(res,list,row + 1, n);
                list.remove(list.size() - 1);
            }
        }

    }
    private static boolean isValid(List<String> list,int i, int n) {
        for (int j = 0; j < list.size(); j++) {
            if (list.get(j).charAt(i) == 'Q') return false;
        }

        for (int j = list.size() - 1, count = 1; j >= 0; j--, count++) {
            if (i + count < n) {
                if (list.get(j).charAt(i + count) == 'Q') return false;
            }
            if (i - count >= 0) {
                if (list.get(j).charAt(i - count) == 'Q') return false;
            }
        }

        return true;
    }
    private static String generateQ(int i, int n) {
        StringBuilder res = new StringBuilder();
        for (int j = 0; j < n; j++) {
            if (j == i) {
                res.append('Q');
            } else {
                res.append(".");
            }
        }
        return res.toString();
    }
}