Python求解八皇后问题——回溯算法的一般形式

八皇后问题是经典回溯算法例题，用“暴力搜索”的方法求解。在Leetcode描述为：https://leetcode-cn.com/problems/eight-queens-lcci/设计一种算法，打印 8皇后在 8× 8棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线由八皇后问题可以推广至N皇后问题。咱们先以4皇

木盏

3445人浏览 · 2021-04-15 20:10:02

木盏 · 2021-04-15 20:10:02 发布

八皇后问题是经典回溯算法例题，用“暴力搜索”的方法求解。在Leetcode描述为：https://leetcode-cn.com/problems/eight-queens-lcci/

设计一种算法，打印 8皇后在 8 × 8 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线

由八皇后问题可以推广至N皇后问题。

咱们先以4皇后来进行思考：

-	-	Q	-
Q	-	-	-
-	-	-	Q
-	Q	-	-

以每个皇后Q为中心，“进行米”字威胁，要求皇后们两两不威胁。所以要求任意2个皇后Q，不同行不同列也不同对角线。

思考：咱们需要逐个位置地填“Q”来验证当前位置是否适合放“Q”。比如，在(0, 0)放Q，我们并不知道是否合理，需要继续放，直到某一行完全没有合适的位置，我们才知道前面有问题。

用回溯算法构思：

依次遍历第一排的4个位置，然后推测出第二排可能的位置，继续往下推测，直到无解或者找到答案就返回。

咱们用“递归”直接实现上面画的树状结构就可以完成题解了！

1. 每递归一次，就处理下一级节点；

2. 处理当级节点时，依次填位置([0, 1, 2, 3])并判断是否有效。如果有效，则进入下一级节点；若无效，则返回。

3. 判断停止：如果咱们处理到row3（也就是第4级节点），与棋盘的行数一致，并且有解，则代表已经得出一组解了。

# author: muzhan

C = 0

def run(num=8):
    result = [-1] * num
    row = 0
    backtrack(result, row)

def backtrack(result, row):
    n = len(result)
    if row == n:
        global C
        C += 1
        print(result)
        return
    for i in range(n):
        result[row] = i
        if isvalid(result, row):
            backtrack(result, row+1)

def isvalid(ans, pos):
    valid = True
    for i in range(pos):
        diag = pos - i
        if ans[pos] in [ans[i], ans[i] - diag, ans[i] + diag]:
                valid = False
                break
    return valid



if __name__ == '__main__':
    run(num=8)
    print('solution num:', C)

总结

对于回溯算法的一般解体方法：

1. 画出一个树状图，确定多级节点；

2. 写出有效性判断函数isvalid()；

3. 用递归backtrack(i+1)的形式向下追溯节点。

对于leetcode题的解法：https://leetcode-cn.com/problems/eight-queens-lcci/

class Solution:
    def __init__(self):
        self.ans_set = []

    def isvalid(self, ans, pos):
        valid = True
        for i in range(pos):
            diag = pos - i
            if ans[pos] in [ans[i], ans[i]-diag, ans[i]+diag]:
                valid = False
                break
        return valid
    
    def backtrack(self, ans, pos):
        n = len(ans)
        if n == pos:
            board = []
            for i in ans:
                row = ["."] * n
                row[i] = "Q"
                board.append(''.join(row))
            self.ans_set.append(board)
            return
        for i in range(n):
            ans[pos] = i
            if self.isvalid(ans, pos):
                self.backtrack(ans, pos+1)


    def solveNQueens(self, n: int) -> List[List[str]]:
        result = [-1] * n
        row = 0
        self.backtrack(result, row)
        return self.ans_set

击败了30%，待优化...