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

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

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

众所周知，计算机最擅长做的就是重复的事情，而我们最朴素的感情就是遍历所有的可能，去掉不可能的不成立方案就是结果，由于不能再同一行，所以我们每个棋子都在八行中，由于不能再同一列，所以我们只考虑不能在同一行和同一列的话，我们需要计算多少种可能呢？
$$\mathrm{s}\mathrm{u}\mathrm{m}=A_8^8=40320$$
我们在从这些可能中去除有在同一斜线上的不就是答案了嘛。但是这样的话我们需要生成所有的可能并且保存这些可能进行验证，这样很浪费时间和空间，其实我们可以在生成可能的时候就计算这个棋子放置的时候符合不符合摆放的规则，不符合就下一个，符合就下一行。直到最后一行都符合的话我们就保存这个结果。

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 个棋子放到第一行、第二行、第三行……第八行。在放置的过程中，我们不停地检查当前放法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种放法，继续尝试。

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