DFS-Recall8

发表于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/n-queens-ii/]

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

给定一个整数 n，返回n 皇后不同的解决方案的数量。

示例:

输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
[“.Q..”, // 解法 1
“…Q”,
“Q…”,
“..Q.”],

[“..Q.”, // 解法 2
“Q…”,
“…Q”,
“.Q..”]
]

算法描述

在建立算法之前，我们来考虑两个有用的细节。

一行只可能有一个皇后且一列也只可能有一个皇后。

这意味着没有必要再棋盘上考虑所有的方格。只需要按列循环即可。

对于所有的主对角线有 行号 + 列号 = 常数，对于所有的次对角线有 行号 - 列号 = 常数.

这可以让我们标记已经在攻击范围下的对角线并且检查一个方格 (行号, 列号) 是否处在攻击位置。

现在已经可以写回溯函数 backtrack(row = 0).

从第一个 row = 0 开始.

循环列并且试图在每个 column 中放置皇后.

如果方格 (row, column) 不在攻击范围内

在(row, column) 方格上放置皇后。
排除对应行，列和两个对角线的位置。
如果所有的行被考虑过，row == N，意味着我们找到了一个解
否则继续考虑接下来的皇后放置 backtrack(row + 1).
回溯：将在 (row, column) 方格的皇后移除.

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int ans;
    vector<bool> row,col,diag,anti_diag;
    int totalNQueens(int n) {
        row = col = vector<bool>(n,false);
        diag = anti_diag = vector<bool>(2*n,false);
        ans = 0;
        dfs(0,0,0,n);
        return ans;
    }
    
    void dfs(int x,int y,int s,int n){
        if(y==n)x++,y=0;
        if(x==n){
            if(s==n)++ans;
            return ;
        }
        
        dfs(x,y+1,s,n);
        
        if(!row[x]&&!col[y]&&!diag[x+y]&&!anti_diag[n-1-x+y]){
            row[x] = col[y] = diag[x+y] = anti_diag[n-1-x+y] = true;
            dfs(x,y+1,s+1,n);
            row[x] = col[y] = diag[x+y] = anti_diag[n-1-x+y] = false;
        }
        
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    
    public int backtrack(int row,int hills,int next_row,int dales,int count,int n){
        int columns = (1<<n)-1;
        if(row == n)
            count++;
        else{
            int free_columns = columns&~(hills|next_row|dales);
            
            while(free_columns != 0){
                int curr_columns = -free_columns&free_columns;
                
                free_columns^=curr_columns;
                
                count = backtrack(row+1,
                                 (hills|curr_columns)<<1,
                                 next_row|curr_columns,
                                 (dales|curr_columns)>>1,
                                count,n);
            }
        }
        return count;
    }
    public int totalNQueens(int n) {
        return backtrack(0,0,0,0,0,n);
    }
}