算法搜索

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

字数统计: 2.8k字   |   阅读时长: 13分
,

摘要: 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