從八皇後問題到回溯算法

    大家好，今天我們來看一下回溯算法。

   在開始之前，我們先來回顧一下貪心算法。如果不熟悉的同學可以看這篇文章從哈夫曼編碼中我們學到了什麼？。

貪心算法隻能根據目前的狀态，選擇最優的走法，走向下一步，就和人的一生一樣，隻能在岔路口選擇一條目前條件下最優的路走，過去就過去了，不能回退，隻能一條路走到黑。而回溯算法，可以有重來的機會，比如選擇了一條路，發現這條路不适合自己，然後回退到岔路口，重新來選擇。這就是回溯的思想（類似于可以穿越一樣）。

   回溯算法本質上就是枚舉，我們枚舉所有的解，然後去找到滿足期望的解。為了有規律地枚舉所有可能的解，避免遺漏和重複，我們把問題求解的過程分為多個階段。每個階段，我們都會面對一個岔路口，我們先随意選一條路走，當發現這條路走不通的時候（不符合期望的解），就回退到上一個岔路口，另選一種走法繼續走。

   理論太過于抽象，我們來舉一個經典的例子-八皇後問題，來更深入的了解一下回溯的思想。首先我們來看一下題目:

   我們有一個 8x8 的棋盤，希望往裡放 8 個棋子（皇後），每個棋子所在的行、列、對角線都不能有另一個棋子。如下圖所示：圖中圓圈代表皇後，顯然下圖的放置方法是不滿足條件的。

八皇後問題就是期望找到所有滿足這種要求的放置棋子的方式。我們可以這麼考慮，我們把這個問題劃分成8個階段，然後将8個棋子分别放到第一行、第二行...直到最後一行。在放置的過程中，我們不停地檢查目前放法，是否滿足要求。如果滿足，則跳到下一行繼續放置棋子；如果不滿足，那就再換一種放置的方法，然後再繼續嘗試。    我們來看一下代碼是如何實作的。

class Cal8Queens:
     result=[0 for i in range(8)]
     count=0

     def findResult(self,row):
          if row==8:
               #放置ok,輸出結果
               self.printResult(self.result)
               return

          for col in range(8):
               #考察放置是否滿足
               if self.isResult(row,col):
                    self.result[row]=col
                    #繼續考察下一行
                    self.findResult(row+1)

     def isResult(self,row,col):
          #判斷row行column列放置是否合适
          leftup=col-1
          rightup=col+1
          for i in range(row-1,-1,-1):

               #考慮正上方是否有皇後
               if self.result[i]==col:
                    return False

               if leftup>=0:
                    #考慮左上角是否有皇後
                    if self.result[i]==leftup:
                         return False

               if rightup<8:
                    # 考慮右上角是否有皇後
                    if self.result[i]==rightup:
                         return False
               leftup=leftup-1
               rightup=rightup+1
          return True

     def printResult(self,result):
          self.count=self.count+1
          for row in range(8):
               for col in range(8):
                    if result[row]==col:
                         print("Q",end=" ")
                    else:
                         print("*",end=" ")
               print()
          print("===============")
          print()

cal=Cal8Queens()
cal.findResult(0)
print(cal.count)
複制代碼      

盡管回溯算法原理很好了解，當時卻可以解決很多問題。比如深度優先搜尋、0-1背包問題等，如果要想完全掌握，還是需要多多練習。

”。