首页 > 代码库 > 52. N-Queens II

52. N-Queens II

哈哈和51是一毛一样的backtracking,唯一区别就是比起每次找到最后生成一个板子,就是记个数,非常不要脸的发两篇

 

 1     int cnt = 0;
 2     
 3     public int totalNQueens(int n) {
 4         int[] queuePos = new int[n];
 5         queue(queuePos, 0);
 6         return cnt;
 7     }
 8     
 9     private boolean canPlace(int[] queuePos, int row, int col) {
10         for(int i = 0; i < row; i++) {
11             if(queuePos[i] == col) {
12                 return false;
13             }
14             if(Math.abs(i - row) == Math.abs(queuePos[i] - col)) {
15                 return false;
16             }
17         }
18         return true;
19     }
20     
21     private void queue(int[] queuePos, int row) {
22         int n = queuePos.length;
23         if(row == n) {
24             cnt++;
25             return;
26         }
27         for(int i = 0; i < n; i++) {
28             if(canPlace(queuePos, row, i)) {
29                 queuePos[row] = i;
30                 queue(queuePos, row + 1);
31             }
32         }
33     }

 

52. N-Queens II