N 皇后问题的演进（附代码）

Posted on

N-皇后问题的演进（附代码)

[TOC]

一、该类问题的通用回溯解法

N 皇后问题的解法是典型的回溯算法，回溯算法本质上就是穷举决策树。暴力有效。

回溯问题的解法框架：

1
2
3
4
5
6
7
8
9
res = []
def backtrack(path, choices):
	if 满足终止条件:
		res.append(path[:])
		return
	for choice in choices:
		做选择
		backtrack(path, choices)
		撤销选择

关于这类回溯问题如何解，推荐这篇文章回溯算法解题套路框架

二、N 皇后问题两个核心问题

N 皇后问题 有两个需要关键处理的：

  1. 回溯，可以直接套模版
  2. 合法的放置皇后，判断位置的是否合法

如何判断位置是否合法

该部分主要参考 力扣上的这篇帖子:Accepted 4ms c++ solution use backtracking and bitmask, easy understand.

如何算合法放置？

image-20200318120331036

N个皇后，要求放置时不同行，不同列，不同对角线,如果算法是遍历每行（当然也可以遍历每列，并确保每行只有一个皇后，那么只需考虑，不同列，和不同对角线）

关于对角线部分，其实只需考虑 45度方向（即左上方）135度方向（即右上方），因为递归遍历每行时，当到达某行时，未遍历的行数皆没有放置皇后。

故可以得出代码（直接放原博主的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
30
31
32
33
34
35
36
37
class Solution {
public:
    std::vector<std::vector<std::string> > solveNQueens(int n) {
        std::vector<std::vector<std::string> > res;
        std::vector<std::string> nQueens(n, std::string(n, '.'));
        solveNQueens(res, nQueens, 0, n);
        return res;
    }
private:
    void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, int row, int &n) {
        if (row == n) {
            res.push_back(nQueens);
            return;
        }
        for (int col = 0; col != n; ++col)
            if (isValid(nQueens, row, col, n)) {
                nQueens[row][col] = 'Q';
                solveNQueens(res, nQueens, row + 1, n);
                nQueens[row][col] = '.';
            }
    }
    bool isValid(std::vector<std::string> &nQueens, int row, int col, int &n) {
        //check if the column had a queen before.
        for (int i = 0; i != row; ++i)
            if (nQueens[i][col] == 'Q')
                return false;
        //check if the 45° diagonal had a queen before.
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
            if (nQueens[i][j] == 'Q')
                return false;
        //check if the 135° diagonal had a queen before.
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
            if (nQueens[i][j] == 'Q')
                return false;
        return true;
    }
};

这样在判断皇后位置是否合法时，其实有很多冗余计算，不妨以空间换时间，通过数组存下位置的状态（是否可以放置皇后），原博主天才的想法：

对于 n皇后，总共有n列，45° 对角线数目：2*n-1, 对角线135°的数目也为2 * n-1。当到达[row，col]时，列号为col，则 45°对角线编号为row + col，而135°对角线编号为n-1 + col- row。 我们可以使用三个数组来指示列或对角线之前是否有王后，如果没有，我们可以将王后放在这个位置并继续。

示意图：

image-20200318121504700

代码实现（原博主的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
30
31
32
33
34
/**    | | |                / / /             \ \ \
  *    O O O               O O O               O O O
  *    | | |              / / / /             \ \ \ \
  *    O O O               O O O               O O O
  *    | | |              / / / /             \ \ \ \ 
  *    O O O               O O O               O O O
  *    | | |              / / /                 \ \ \
  *   3 columns        5 45° diagonals     5 135° diagonals    (when n is 3)
  */
class Solution {
public:
    std::vector<std::vector<std::string> > solveNQueens(int n) {
        std::vector<std::vector<std::string> > res;
        std::vector<std::string> nQueens(n, std::string(n, '.'));
        std::vector<int> flag_col(n, 1), flag_45(2 * n - 1, 1), flag_135(2 * n - 1, 1);
        solveNQueens(res, nQueens, flag_col, flag_45, flag_135, 0, n);
        return res;
    }
private:
    void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, std::vector<int> &flag_col, std::vector<int> &flag_45, std::vector<int> &flag_135, int row, int &n) {
        if (row == n) {
            res.push_back(nQueens);
            return;
        }
        for (int col = 0; col != n; ++col)
            if (flag_col[col] && flag_45[row + col] && flag_135[n - 1 + col - row]) {
                flag_col[col] = flag_45[row + col] = flag_135[n - 1 + col - row] = 0;
                nQueens[row][col] = 'Q';
                solveNQueens(res, nQueens, flag_col, flag_45, flag_135, row + 1, n);
                nQueens[row][col] = '.';
                flag_col[col] = flag_45[row + col] = flag_135[n - 1 + col - row] = 1;
            }
    }
};

其实完全没有必要开辟三个数组，一个flag数组就够。现在，当到达[row，col]时，列的下标为col，对角线45°的下标为n + row + col，对角线135°的下标为n + 2 * n-1 + n-1 + col -行。flag 数组的大小为 n+2n-1+2n-1=5n-2

代码实现（python3）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def solveNQ(n, row, res, flag):
            if row==n:
                res.append([str for str in nq])
                return
            for col in range(n):
                if flag[col] and flag[n+row+col] and flag[4*n-2+col-row]:
                    flag[col]=flag[n+row+col]=flag[4*n-2+col-row]=0
                    nq[row] = nq[row][:col]+'Q'+nq[row][col+1:]
                    solveNQ(n, row+1, res, flag)
                    flag[col]=flag[n+row+col]=flag[4*n-2+col-row]=1
                    nq[row] = nq[row][:col]+'.'+nq[row][col+1:]
        nq = ['.'*n for _ in range(n)]
        res =[]
        flag = [1 for _ in range(5*n-2)]
        solveNQ(n, 0, res, flag)
        return res

但是python中修改字符串其实挺浪费时间的，完全可以存一个列号，等求出所有的排列后，再构造出棋盘分布。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def solveNQ(n, row, res, flag, nqCol):
            if row==n:
                res.append(nqCol[:])
                return
            for col in range(n):
                if flag[col] and flag[n+row+col] and flag[4*n-2+col-row]:
                    flag[col]=flag[n+row+col]=flag[4*n-2+col-row]=0
                    nqCol[row] = col
                    solveNQ(n, row+1, res, flag, nqCol)
                    flag[col]=flag[n+row+col]=flag[4*n-2+col-row]=1
                    nqCol[row] = -1
        res =[]
        flag = [1 for _ in range(5*n-2)]
        solveNQ(n, 0, res, flag, [-1 for _ in range(n)])    
        for i, npCol in enumerate(res):
            board =[]
            for col in npCol:
                board.append('.'*col+'Q'+'.'*(n-1-col))
            res[i] = board   
        return res

17-21行代码是构造棋盘分布的

总结

  1. 回溯问题要学会套模板，
  2. python 代码最好尽可能解耦合，模块化，降低模块的耦合性。