八皇后問題是一個(gè)古老而又著名的問題，是學(xué)習(xí)回溯算法的一個(gè)經(jīng)典案例。我們不探究她的歷史，只說解決方案

在8×8格的國際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問一共有多少種擺法。

眾所周知，計(jì)算機(jī)最擅長做的就是重復(fù)的事情，而我們最樸素的感情就是遍歷所有的可能，去掉不可能的不成立方案就是結(jié)果，由于不能再同一行，所以我們每個(gè)棋子都在八行中，由于不能再同一列，所以我們只考慮不能在同一行和同一列的話，我們需要計(jì)算多少種可能呢？
$$\mathrm{s}\mathrm{u}\mathrm{m}=A_8^8=40320$$
我們?cè)趶倪@些可能中去除有在同一斜線上的不就是答案了嘛。但是這樣的話我們需要生成所有的可能并且保存這些可能進(jìn)行驗(yàn)證，這樣很浪費(fèi)時(shí)間和空間，其實(shí)我們可以在生成可能的時(shí)候就計(jì)算這個(gè)棋子放置的時(shí)候符合不符合擺放的規(guī)則，不符合就下一個(gè)，符合就下一行。直到最后一行都符合的話我們就保存這個(gè)結(jié)果。

class NQueen():
    def __init__(self):
        self.n = 8; #定義幾個(gè)皇后
        self.res = [] # 定義結(jié)果

    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()

這其實(shí)就是回溯，我們把這個(gè)問題劃分成 8 個(gè)階段，依次將 8 個(gè)棋子放到第一行、第二行、第三行……第八行。在放置的過程中，我們不停地檢查當(dāng)前放法，是否滿足要求。如果滿足，則跳到下一行繼續(xù)放置棋子；如果不滿足，那就再換一種放法，繼續(xù)嘗試。

實(shí)際上我認(rèn)為回溯算法最難的是對(duì)于遞歸的理解