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