【算法】N皇后问题的回溯算法

问题

N皇后问题实际上是八皇后问题的拓展，需要在一个$n*n$大小的棋盘上放置$n$个皇后棋子，使这$n$个皇后不能互相攻击。即$n$个皇后不能处在同一条横线、竖线、45度斜线上。

Queen

现在要求输入一个整数n，输出n个皇后所有可能的排列方式。（棋盘大小也相应变成n*n）

思考

若我们之间采用暴力的方法解这道题，由于棋盘大小为$n*n$，则这种方法的时间复杂度为$O(n^n)$，为此我们必须采用别的算法。

这道题要用到两个编程概念，一个是约束，一个是回溯。

约束编程的解释是，每新放置一个皇后，就要增加后续放置的限制。比如放置了一个皇后之后，行、列和对角线上都不能再进行放置。

回溯算法，即DFS。假如我们进行筛选的时候，出现了不符合题设条件的情况，比如在一种方案中出现了不能继续放置皇后的情况。此时我们需要回退到上一步，这就是回溯。

下面的代码很好的解释了回溯。

#Python
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

回溯

我们要利用回溯的思路，逐行进行迭代，在每一行循环放置Queen来检查所有可能的组合。

每次放置完，就要添加限制，为此我们设置了col用来存放不能再放置Queen的列，以及diag1和diag2来存放不能放置Queen的主副对角线。如此一来每次放置完成，就向这些集合内增加数据，之后的放置就要利用col, diag1, diag2进行判定，若符合条件才继续进行迭代，否则就会回退。

Python代码如下：

#Python
def nQueens(self, n):
    result = []
    if n == 0: return res
    #row是当前行，col是不能使用的列集，diag1和diag2分别为不能使用的两侧对角线集
    def DFS(row, col, diag1, diag2, cur_result, n):
        #'-'代表空格，即没有存放皇后的地方
        if row == n:
        	result.append(['-' * cur + 'Q' + '-' * (n - cur - 1) for cur in cur_result])
        	return
    	for i in range(n):
            if (i not in col) and (i - row not in diag1) and (i + row not in diag2):
                DFS(row + 1, col|{i}, diag1|{i-row}, diag2|{i+row}, cur_result + [i], n)
                
    DFS(0, set(), set(), set(), [], n)
    return result

参考

【1】八皇后问题—百度百科