深度优先搜索之八皇后问题

八皇后问题是一个古老而又著名的问题，是学习回溯算法的一个经典案例。我们不探究她的历史，只说解决方案

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。

class NQueen():
    def __init__(self):
        self.n = 8; #定义几个皇后
        self.res = [] # 定义结果

    def run(self):
        self.bfs(resOfOne=[])
        print(f"共有{
            
     len(self.res)}种可能")
        print(self.res)

    def bfs(self,resOfOne):
        if len(resOfOne) == self.n:
            self.res.append(resOfOne[:])

        for i in range(self.n):
            # 确保不在同一行同一列
            if i not in resOfOne:
                # 确保不在同一斜线
                if self.notINBias(i,resOfOne):
                    resOfOne.append(i)
                    self.bfs(resOfOne)
                    resOfOne.pop(-1)
    
    def notINBias(self,i,resOfOne):
        length = len(resOfOne)
        for m,n in enumerate(resOfOne):
            if length-m == i-n or length+i == n+m:
                return False
        return True

nqueen = NQueen()
nqueen.run()

这其实就是回溯，我们把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行、第二行、第三行……第八行。在放置的过程中，我们不停地检查当前放法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种放法，继续尝试。

实际上我认为回溯算法最难的是对于递归的理解