穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞N 皇后

题目： 

 

---

解析：

1.决策树：  

 

---

代码设计： 

 

---

根据决策树剪枝设计： 

 

---

代码： 

class Solution {
    private List<List<String>> ret;
    private char[][] path;
    private boolean[] checkdig1,checkdig2,checkcol;
    int n;

    public List<List<String>> solveNQueens(int _n) {
        n = _n;
        ret = new ArrayList<>();
        path = new char[n][n];
        checkcol = new boolean[n];//判断列有没有n皇后
        checkdig1 = new boolean[2*n];//判断主对角线有没有n皇后
        checkdig2 = new boolean[2*n];//判断副对角线有没有n皇后



        for(int i = 0; i < n; i++)
            Arrays.fill(path[i],'.');    

        dfs(0);
        return ret;
    }

    private void dfs(int row){
        if(row == n){
            List<String> tmp = new ArrayList<>();  
            for(int i = 0; i < n; i++){
                tmp.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
            return;
        } 

        for(int col = 0; col < n; col++){

            //剪枝写法，能不能放N 皇后:
            if(checkcol[col] == false && checkdig1[col-row+n] == false && checkdig2[col+row] == false){
                path[row][col] = 'Q';
                checkcol[col] = checkdig1[col-row+n] = checkdig2[col+row] = true;
                dfs(row+1);

                //恢复现场
                path[row][col] = '.';
                checkcol[col] = checkdig1[col-row+n] = checkdig2[col+row] = false;
            }
        }
    }
}