八皇后問題是一個古老而又著名的問題，是學習回溯算法的一個經典案例。我們不探究她的歷史，只說解決方案

在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 個棋子放到第一行、第二行、第三行……第八行。在放置的過程中，我們不停地檢查當前放法，是否滿足要求。如果滿足，則跳到下一行繼續放置棋子；如果不滿足，那就再換一種放法，繼續嘗試。

實際上我認為回溯算法最難的是對于遞歸的理解