大家好，今天我们来看一下回溯算法。
在开始之前，我们先来回顾一下贪心算法。如果不熟悉的同学可以看这篇文章。
贪心算法只能根据当前的状态，选择最优的走法，走向下一步，就和人的一生一样，只能在岔路口选择一条当前条件下最优的路走，过去就过去了，不能回退，只能一条路走到黑。而回溯算法，可以有重来的机会，比如选择了一条路，发现这条路不适合自己，然后回退到岔路口，重新来选择。这就是回溯的思想（类似于可以穿越一样）。
回溯算法本质上就是枚举，我们枚举所有的解，然后去找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。
理论太过于抽象，我们来举一个经典的例子-八皇后问题，来更深入的理解一下回溯的思想。首先我们来看一下题目:
我们有一个 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背包问题等，如果要想完全掌握，还是需要多多练习。
今天的分享就到这里，更多硬核知识，请关注公众号“程序员学长”。