n皇后问题:同一问题构造不同的状态空间树

  |  

摘要: n 皇后问题与回溯法

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


在文章 回溯法的思想、设计与分析 中,我们系统了解了回溯法的思想。

我们知道要用回溯法解决问题,首先需要明确问题的解空间,构成解空间的向量可以表示为 $(x_{0}, x_{1}, \cdots, x_{n-1})$。解空间一般描述为树形结构,称为状态空间树。文章 回溯法三种常见的状态空间树:子集树、排列树、满m叉树 中,我们学习了三种常见的状态空间树。

显式约束规定了待求解问题的所有可能的候选解,这些候选解组成了问题实例的解空间。也就是说,显式约束决定了状态空间树。

隐式约束用于判定一个候选解是否为可行解。根据隐式约束,我们可以设计一个判定函数 $p(x_{0},x_{1},\cdots,x_{n-1})$,若该函数为真,则称候选解 $(x_{0},x_{1},\cdots,x_{n-1})$ 是问题的可行解。

有时对于同一个问题,其中的某个约束条件既可以理解为显式约束、也可以理解为隐式约束,不同的理解方式会构成不同的状态空间树。

n 皇后是一个例子,可以把行和列的约束视为显式约束,构成排列树,斜线的约束视为隐式约束;也可以把行的约束视为显式约束,构成组合树,列和斜线的约束视为隐式约束。

本文我们来看一下 n 皇后问题。


51. N皇后 (返回所有可行解)

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

提示:

1
1 <= n <= 9

示例 1:

输入:n = 4
输出:[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1
输出:[[“Q”]]

算法1:回溯法-排列树

  • 显式约束:n 个皇后不同行。在不同行的前提下,n 个皇后的列位置是 n 个列的一个排列,状态空间树构成排列树。
  • 隐式约束:n 个列位置的排列必须满足 n 个皇后的位置不在一条斜线上。

排列树:1,2,3 三个元素的排列

代码 (C++)

代码整体是按照回溯法搜索排列树的代码模板来的。注意 check 函数中是隐式约束,其中 n 皇后不同行不同列是显式约束处理的,代码中 check 函数中检查同一行和同一列的部分可以注释掉。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// 朴素 DFS
// 无剪枝,无位运算优化
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
if(n <= 0)
return vector<vector<string>>();
if(n == 1)
return vector<vector<string>>(1, vector<string>(1,"Q"));

vector<vector<string> > result;
vector<string> board(n, string(n, '.'));
vector<int> cur_path(n); // 当前的排列
for(int i = 0; i < n; ++i)
cur_path[i] = i;
dfs(result, 0, board, cur_path, n);
return result;
}

private:
void dfs(vector<vector<string> >& result, int row, vector<string>& board, vector<int>& cur_path, const int n)
{
// row 是排列树的深度,也代表棋盘的行号
if(row == n)
{
result.push_back(board);
return;
}

for(int j = row; j < n; ++j)
{
if(board[row][cur_path[j]] == '.' && check(board, row, cur_path[j]))
{

// 第 row 行对应的列号取 cur_path[j]
board[row][cur_path[j]] = 'Q';
swap(cur_path[row], cur_path[j]);
dfs(result, row + 1, board, cur_path, n);
swap(cur_path[row], cur_path[j]);
board[row][cur_path[j]] = '.';
}
}
}

bool check(vector<string>& board, int x, int y)
{
int n = board.size();

// 检查同行
/* 皇后不同行且不同列是显式约束,因此这里隐式约束的部分可能省略同行和同列的检查
* for(int j = 0; j < n; ++j)
* {
* if(board[x][j] == 'Q')
* return false;
* }
*
* // 检查同列
* for(int i = 0; i < n; ++i)
* {
* if(board[i][y] == 'Q')
* return false;
* }
*/

// 检查同对角线
for(int i = x, j = y; i < n && j < n; ++i, ++j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = x, j = y; i >= 0 && j < n; --i, ++j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = x, j = y; i < n && j >= 0; ++i, --j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = x, j = y; i >= 0 && j >= 0; --i, --j)
{
if(board[i][j] == 'Q')
return false;
}
return true;
}
};

算法1:回溯法-满n叉树

  • 显式约束:n 个皇后不同行。在不同行的前提下,任一皇后的列位置都有 n 种选择。状态空间树构成满 n 叉树。
  • 隐式约束:n 个列位置的一个组合必须满足 n 个皇后的位置不在同一列或不在同一条斜线上的性质。

满 3 叉树:选 3 个元素,每次可以从 1,2,3 中选

代码 (C++)

代码整体是按照回溯法搜索满 n 叉树的代码模板来的。注意 check 函数中是隐式约束,其中 n 皇后不同行是显式约束处理的,代码中 check 函数中检查同一行的部分可以注释掉。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// 朴素 DFS
// 无剪枝,无位运算优化
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
if(n <= 0)
return vector<vector<string>>();
if(n == 1)
return vector<vector<string>>(1, vector<string>(1,"Q"));

vector<vector<string> > result;
vector<string> board(n, string(n, '.'));
dfs(result, 0, board, n);
return result;
}

private:
void dfs(vector<vector<string> >& result, int row, vector<string>& board, int n)
{
// row 是满 n 叉树的深度,也代表棋盘的行号
if(row == n)
{
result.push_back(board);
return;
}

for(int j = 0; j < n; ++j)
{
if(board[row][j] == '.' && check(board, row, j))
{
board[row][j] = 'Q';
dfs(result, row + 1, board, n);
board[row][j] = '.';
}
}
}

bool check(vector<string>& board, int x, int y)
{
int n = board.size();

// 检查同行
/* 皇后不同行是显式约束,因此这里隐式约束的部分可能省略同行的检查
* for(int j = 0; j < n; ++j)
* {
* if(board[x][j] == 'Q')
* return false;
* }
*/

// 检查同列
for(int i = 0; i < n; ++i)
{
if(board[i][y] == 'Q')
return false;
}

// 检查同对角线
for(int i = x, j = y; i < n && j < n; ++i, ++j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = x, j = y; i >= 0 && j < n; --i, ++j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = x, j = y; i < n && j >= 0; ++i, --j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = x, j = y; i >= 0 && j >= 0; --i, --j)
{
if(board[i][j] == 'Q')
return false;
}
return true;
}
};

52. N皇后 II (返回可行解个数)

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

给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。

提示:

1
1 <= n <= 9

示例 1:

输入:n = 4
输出:2
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1
输出:1

算法:回溯法

上一题解决的事返回所有的可行解,本题是只需要可行解个数。

直接用返回所有可行解的回溯法当然可以,这里以排列树的回溯方式为例。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
public:
int totalNQueens(int n) {
if(n <= 1)
return n;

int ans = 0;
vector<string> board(n, string(n, '.'));
vector<int> cur_path(n); // 当前的排列
for(int i = 0; i < n; ++i)
cur_path[i] = i;
dfs(ans, 0, board, cur_path, n);
return ans;
}

private:
void dfs(int& ans, int row, vector<string>& board, vector<int>& cur_path, const int n)
{
// row 是排列树的深度,也代表棋盘的行号
if(row == n)
{
++ans;
return;
}

for(int j = row; j < n; ++j)
{
if(board[row][cur_path[j]] == '.' && check(board, row, cur_path[j]))
{

// 第 row 行对应的列号取 cur_path[j]
board[row][cur_path[j]] = 'Q';
swap(cur_path[row], cur_path[j]);
dfs(ans, row + 1, board, cur_path, n);
swap(cur_path[row], cur_path[j]);
board[row][cur_path[j]] = '.';
}
}
}

bool check(vector<string>& board, int x, int y)
{
int n = board.size();

// 检查同行
/* 皇后不同行且不同列是显式约束,因此这里隐式约束的部分可能省略同行和同列的检查
* for(int j = 0; j < n; ++j)
* {
* if(board[x][j] == 'Q')
* return false;
* }
*
* // 检查同列
* for(int i = 0; i < n; ++i)
* {
* if(board[i][y] == 'Q')
* return false;
* }
*/

// 检查同对角线
for(int i = x, j = y; i < n && j < n; ++i, ++j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = x, j = y; i >= 0 && j < n; --i, ++j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = x, j = y; i < n && j >= 0; ++i, --j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = x, j = y; i >= 0 && j >= 0; --i, --j)
{
if(board[i][j] == 'Q')
return false;
}
return true;
}
};

额外剪枝:第一行只走一半

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
// 简单剪枝,第一行只走一半
class Solution {
public:
int totalNQueens(int n) {
if(n <= 0)
return 0;
if(n == 1)
return 1;

vector<string> board(n, string(n, '.'));
int ans = dfs(0, board, n);
return ans;
}

private:
int dfs(int row, vector<string>& board, int n)
{
if(row == n)
{
return 1;
}

int ans = 0;
if(row == 0)
{
for(int j = 0; j < n / 2; ++j)
{
if(board[row][j] == '.')
{
if(check(board, row, j))
{
board[row][j] = 'Q';
ans += dfs(row + 1, board, n);
board[row][j] = '.';
}
}
}
ans *= 2;
if(n % 2 == 1)
{
board[row][n / 2] = 'Q';
ans += dfs(row + 1, board, n);
board[row][n / 2] = '.';
}
}
else
{
for(int j = 0; j < n; ++j)
{
if(board[row][j] == '.')
{
if(check(board, row, j))
{
board[row][j] = 'Q';
ans += dfs(row + 1, board, n);
board[row][j] = '.';
}
}
}
}
return ans;
}

bool check(vector<string>& board, int x, int y)
{
int n = board.size();
for(int j = 0; j < n; ++j)
{
if(board[x][j] == 'Q')
return false;
}
for(int i = 0; i < n; ++i)
{
if(board[i][y] == 'Q')
return false;
}
for(int i = x, j = y; i < n && j < n; ++i, ++j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = x, j = y; i >= 0 && j < n; --i, ++j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = x, j = y; i < n && j >= 0; ++i, --j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = x, j = y; i >= 0 && j >= 0; --i, --j)
{
if(board[i][j] == 'Q')
return false;
}
return true;
}
};

优化:用位运算维护棋盘以及约束条件的判定

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
30
31
32
// 状态压缩
class Solution {
public:
int totalNQueens(int n) {
if(n <= 0)
return 0;
if(n == 1)
return 1;

int ans = 0;
dfs(0, 0, 0, 0, n, ans);
return ans;
}

private:
void dfs(int dep, int r, int s1, int s2, int n, int& cnt)
{
if(dep == n)
{
++cnt;
return;
}

for(int i = 0; i < n; ++i)
{
int j = 1 << i;
if((j & r) || (j & s1) || (j & s2))
continue;
dfs(dep + 1, (j | r), (j | s1) << 1, (j | s2) >> 1, n, cnt);
}
}
};

Share