回溯算法-N皇后

N皇后

51. N 皇后

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

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

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

提示：

• 1 <= n <= 9
• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        //记录Q放的位置，一维数组即可
        int[] queens = new int[n];
        Arrays.fill(queens,-1);
        //记录列的使用
        Set<Integer> col = new HashSet<>();
        //记录正对角线的使用
        Set<Integer> diagonal1 = new HashSet<>();
        //记录斜对角线的使用
        Set<Integer> diagonal2 = new HashSet<>();
        dfs(res,queens,n,0,col,diagonal1,diagonal2);
        return res;
    }
    public void dfs(List<List<String>> res,int[] queens,int n,int row,Set<Integer> col,Set<Integer> diagonal1,Set<Integer> diagonal2){
        if(row == n){
            List<String> result = getString(queens,n);
            res.add(result);
        }else{
            //i是列数
            for(int i = 0; i < n; ++i){
                if(col.contains(i)){
                    continue;
                }
                //正对角任意一行行列相减为同一个数
                int dia1 = row - i;
                if(diagonal1.contains(dia1)){
                    continue;
                }
                //斜对角任意一行行列相加为同一个数
                int dia2 = row + i;
                if(diagonal2.contains(dia2)){
                    continue;
                }

                //记录第row行i列放Q
                queens[row] = i;
                col.add(i);
                diagonal1.add(dia1);
                diagonal2.add(dia2);
                dfs(res,queens,n,row+1,col,diagonal1,diagonal2);
                queens[row] = -1;
                col.remove(i);
                diagonal1.remove(dia1);
                diagonal2.remove(dia2);
            }
        }
    }
    public List<String> getString(int[] queens,int n){
        List<String> list = new ArrayList<>();
        for(int i = 0; i < n; ++i){
            char[] row = new char[n];
            Arrays.fill(row,'.');
            //queens[i]才是列数
            row[queens[i]] = 'Q';
            list.add(new String(row));
        }
        return list;
    }
}