求讨论 n皇后的非递归解法

LC51题N皇后

是一道dfs的经典题了，暴力DFS递归，优化的DFS写过，今天下午想用暴力非递归解法写，先自己想写了如下代码(Java)，没有ac，应该是思路有些问题。有同做题的同学，可以帮忙看看思路哪里出现了问题吗？

思路：
- 把 要遍历的 N * N的棋盘，看成是 N 棵树（不是严格意义上的树）。为什么这样想呢？我想根据dfs的非递归写法来改写，在dfs的非递归写法中，是从树的root一个节点开始做dfs的。所以这里我把棋盘的第一行N个位置，看作是N个root。然后从每个root开始对以这个root为根的树做dfs的非递归coding。
- 和原始的dfs不同的一点在于，遍历到一个节点的时候需要知道该节点是在哪一行上，所以使用了变量level来记录
- count[level]是来记录当前level上还有多少个节点没有遍历，如果遍历完了就要向上回溯level--

发现问题的大佬，加6米（你发三条评论，每条我能加2）

1. 
   
2. public class Solution {
   
3.     /*
   
4.      * @param n: The number of queens
   
5.      * @return: All distinct solutions
   
6.      */
   
7. 
   
8.     private Stack<Integer> stack = new Stack<>();
   
9.     public List<List<String>> solveNQueens(int n) {
   
10.         List<List<String>> results = new ArrayList<>();
    
11. 
    
12.         if (n <= 0) {
    
13.             return results;
    
14.         }
    
15. 
    
16.         int[] oneRes = new int[n];
    
17. 
    
18.         // 共有n个root节点
    
19.         for (int i = 0; i < n; i++) {
    
20.             stack.push(i); // push root i (一个节点)
    
21.             int[] count = new int[n];
    
22.             int level = 0;
    
23.             count[level] = 1;
    
24.             while (!stack.isEmpty()) {
    
25.                 int node = stack.pop();
    
26.                 count[level]--;
    
27.                 // process node
    
28.                 boolean available = isAvailable(n, oneRes, level, node);
    
29. 
    
30. 
    
31.                 if (available) {
    
32.                     oneRes[level] = node;
    
33.                     if (level + 1 < n) {
    
34.                         // nodes: 0, 1, 2, ..., n-1
    
35.                         // stack.push(nodes);
    
36.                         level++;
    
37.                         count[level] = n;
    
38.                         for (int j = 0; j < n; j++) {
    
39.                             stack.push(j);
    
40.                         }
    
41.                     } else {
    
42.                         results.add(drawChessboard(oneRes));
    
43.                     }
    
44.                 }
    
45. 
    
46. 
    
47.                 if (count[level] == 0) {
    
48.                     level--;
    
49.                 }
    
50.             }
    
51. 
    
52.         }
    
53. 
    
54. 
    
55.         return results;
    
56.     }
    
57. 
    
58. 
    
59. private List<String> drawChessboard(int[] cols) {
    
60.         List<String> chessboard = new ArrayList<>();
    
61.         for (int i = 0; i < cols.length; i++) {
    
62.             StringBuilder sb = new StringBuilder();
    
63.             for (int j = 0; j < cols.length; j++) {
    
64.                 sb.append(j == cols[i] ? 'Q' : '.');
    
65.             }
    
66.             chessboard.add(sb.toString());
    
67.         }
    
68.         return chessboard;
    
69.     }
    
70. 
    
71.     private boolean isAvailable(int n, int[] queen, int row, int col) {
    
72.          for (int i = 1; row - i >= 0; i++) {
    
73.             int prevQ = queen[row - i];
    
74.             if (col == prevQ) {
    
75.                 return false;
    
76.             }
    
77.             if (col - i >= 0 && col - i == prevQ) {
    
78.                 return false;
    
79.             }
    
80.             if (col + i < n && col + i == prevQ) {
    
81.                 return false;
    
82.             }
    
83.         }
    
84.         return true;
    
85.     }
    
86. }
    

复制代码

have 刷题 smooth day!

错误原因是：
当某层的所有col位置用完了，我们要向上回溯的时候，可能不是仅仅level--向上只减一那么简单。比如
[x, ?, ?]
[x, x, x]
[x, x, x]
row: based-0-index, col: based-0-index
x 表示已经试过，? 表示没有试过。现在假设刚试完[2,2]位置上的col，此时row == 2的这层都试完了。此时向上回溯，我们应该回溯到row == 0 而不是 row == 1.
应该回溯的level 是 count数组从右向左数第一个非0的index.

改正后可以ac的代码:

1. 
   
2. public class Solution {
   
3.     /*
   
4.      * @param n: The number of queens
   
5.      * @return: All distinct solutions
   
6.      */
   
7. 
   
8.     private Stack<Integer> stack = new Stack<>();
   
9.     public List<List<String>> solveNQueens(int n) {
   
10.         List<List<String>> results = new ArrayList<>();
    
11. 
    
12.         if (n <= 0) {
    
13.             return results;
    
14.         }
    
15. 
    
16.         int[] oneRes = new int[n];
    
17. 
    
18.         // 共有n个root节点
    
19.         
    
20.         int[] count = new int[n];
    
21.         for (int i = 0; i < n; i++) {
    
22.             stack.push(i);
    
23.         }
    
24. 
    
25.         int level = 0;
    
26.         count[level] = n;
    
27. 
    
28.         while (!stack.isEmpty()) {
    
29.             int col = stack.pop();
    
30.             
    
31.             count[level]--;
    
32.             // process col
    
33.             boolean available = isAvailable(n, oneRes, level, col);
    
34. 
    
35. 
    
36.             if (available) {
    
37.                 oneRes[level] = col;
    
38.                 if (level + 1 < n) {
    
39.                     // cols: 0, 1, 2, ..., n-1
    
40.                     // stack.push(cols);
    
41.                     level++;
    
42.                     count[level] = n;
    
43.                     for (int j = 0; j < n; j++) {
    
44.                         stack.push(j);
    
45.                     }
    
46.                 } else if (level + 1 == n){
    
47.                     results.add(drawChessboard(oneRes));
    
48.                 }
    
49.             }
    
50. 
    
51. 
    
52.             if (count[level] == 0) {
    
53.                 // level--;
    
54.                 level = updateLevel(count, level);
    
55.             }
    
56.         }
    
57. 
    
58.         
    
59. 
    
60. 
    
61. 
    
62.         return results;
    
63.     }
    
64. 
    
65.     private int updateLevel(int[] count, int curLevel) {
    
66.         int i = curLevel;
    
67.         while (i >= 1) {
    
68.             if (count[--i] != 0) break;
    
69.         }
    
70.         return i;
    
71.     }
    
72. 
    
73. 
    
74. private List<String> drawChessboard(int[] cols) {
    
75.         List<String> chessboard = new ArrayList<>();
    
76.         for (int i = 0; i < cols.length; i++) {
    
77.             StringBuilder sb = new StringBuilder();
    
78.             for (int j = 0; j < cols.length; j++) {
    
79.                 sb.append(j == cols[i] ? 'Q' : '.');
    
80.             }
    
81.             chessboard.add(sb.toString());
    
82.         }
    
83.         return chessboard;
    
84.     }
    
85. 
    
86.     private boolean isAvailable(int n, int[] queen, int row, int col) {
    
87.          for (int i = 1; row - i >= 0; i++) {
    
88.             int prevQ = queen[row - i];
    
89.             if (col == prevQ) {
    
90.                 return false;
    
91.             }
    
92.             if (col - i >= 0 && col - i == prevQ) {
    
93.                 return false;
    
94.             }
    
95.             if (col + i < n && col + i == prevQ) {
    
96.                 return false;
    
97.             }
    
98.         }
    
99.         return true;
    
100.     }
     
101. }
     
102. 
     

复制代码

我debug出来了！如果已经有look into的同学，不明白的可以私聊我！

求刷题的经验和方法zszs感谢🙏