這兩天在刷LeetCode37題解數獨時，被這個回溯法折騰的不要不要的，於是我疼定思疼發誓一定要找個能解決這類回溯法的套路出來，方便以後快速解決此類題目。於是我在網上找了兩個很經典的回溯法題目--八皇后問題和迷宮問題，認真總結了一番，發現其中還真的有一些共同之處，我會在下面好好講述。

首先，回溯法所用到的核心思想就是遞歸法，雖然其過程邏輯很清楚，而且執行效率很高。但缺點也是與之對應的，邏輯清楚，必然其抽象性很高，所以有時候就是這樣的情況：看它的解題過程很容易看懂，但要是讓你自己動手寫這個遞歸過程，發現很難下筆。當時我就是這樣的情況，於是我想在網上找找看看能不能有哪位大佬分享一些解題心得供我們這些演算法渣渣思考學習的，然而網上的一些csdn博客(這兒不是刻意貶低csdn的哈)寫的東西都是千篇一律，都是在把一些舊的不能再舊的東西炒來炒去，沒有一點營養！別人靠不住，那就只能靠自己唄！於是我自己找例子，自己琢磨，終於是有些小收穫，本著慈悲為懷的精神，故想拿出來供大家參考，避免大家少趟坑，保證不打馬虎眼，不炒現飯。當然了，若有不當之處，請各位筆友指出，面的誤人子弟。

1 八皇后問題

問題描述：

該問題是國際西洋棋棋手馬克斯·貝瑟爾於1848年提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處於同一行、同一列或同一斜線上，問有多少種擺法。

看完問題描述後，大家之前要是熟悉此題目的也可以先動手做做，看看還能不能解出來。再正式回答此題目之前我還是先把我寫的答案貼出來，讓大家對整個處理過程有個大致的印象。

八皇后問題代碼如下：

# 檢測皇后之間的位置關係
def conflict(queen_str, current_queen):
"""
:param queen_str: str-->指代當前皇后存放之前的所有皇后的集合
:param current_queen: int-->指代當前皇后想要存放的位置
:return:Flag: boolean-->指代當前位置的皇后是否與之前所有位置的皇后有衝突
"""
# 此處的queen_length既是之前保存的queen_list集合的長度，也可以理解為當前current_queen皇后的行下標
queen_length = len(queen_str)
# 定義是否有位置衝突的標籤
Flag = False
for index in range(queen_length):
# queen_length - index主要是控制相鄰兩行的皇后不能處於對角線上，其他的就沒要求
if abs(current_queen-int(queen_str[index])) in(0, queen_length-index):
Flag = True
break
return Flag

# 定義執行皇后問題的主函數
def queens(nums=8, queen_str=""):
"""
:param nums: int-->指代整個棋盤中想要存放皇后的個數
:param queen_str: str-->指代當前皇后存放之前的所有皇后的集合
:return:final_queens: List[int]-->指代最後符合要求的皇后的位置
"""
final_queens = []

# 定義遞歸函數，獲取所有八皇后的值
def back(queen_str):
# 出口條件
if len(queen_str) == nums:
final_queens.append(queen_str)
return
for index in range(nums):
Flag = conflict(queen_str, index)
# 如果當前位置的皇后是否與之前所有位置的皇后沒有衝突，則執行下述代碼
if Flag is False:
back(queen_str+str(index))

back(queen_str)
return final_queens

if __name__ == "__main__":
final_queens = queens()
print(final_queens)
print(len(final_queens))

寫的應該還是比較清楚的，大家也可以再看看官方給的回溯法的描述

描述：

回溯法（探索與回溯法）是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。

其實我總結起來就3點：

1 出口。一個遞歸演算法一定要有出口，否則就是一個死循環了。出口語句一般都挺好寫的，但 是出口語句該放在哪兒了，這個就是關鍵了，這兒容許我先賣個關子。

2 遞歸函數的參數。一般情況下，遞歸函數是要帶參數的，因為遞歸操作都是用來處理下一次的過程，如果沒有參數的話，那麼就很難從下一次的操作回溯到當前操作了。這麼說，可能會有點迷糊，別急，後面我會舉例子，這兒還是賣個關子。

3 遞歸函數的處理過程。這個自不必多說，重中之重，需要好好理解其過程

上面3點就是我總結的關於回溯法的關鍵點了，我覺得只要真正的把這3步喫透，一般的回溯法題目是ok的（這可不是我吹牛哈）下面我就這3點仔細講講，大家可要豎起耳朵通清楚了哈。

1 出口

關於這個出口條件，就像我上面說的，它的關鍵是出口語句放置的位置，因為這個語句其實挺好寫的，一般也就2-3行代碼，大多數人都能想出來。但我覺得大多數人苦惱的就是不知道該把它放在哪兒，我剛開始也是這樣，後面總結了2-3題之後，我發現了一個萬能規律，就是把出口語句放在遞歸函數的第一行就行，大家可以看看八皇后問題的遞歸函數back()以及迷宮問題的遞歸函數back()，我這兒就直接貼出來。

八皇后問題的遞歸函數back()

# 定義遞歸函數，獲取所有八皇后的值
def back(queen_str):
# 出口條件
if len(queen_str) == nums:
final_queens.append(queen_str)
return
for index in range(nums):
Flag = conflict(queen_str, index)
# 如果當前位置的皇后是否與之前所有位置的皇后沒有衝突，則執行下述代碼
if Flag is False:
back(queen_str+str(index))


迷宮問題的遞歸函數back()

def back(position=start, pos_list=[start]):
# 該遞歸函數的出口
if position == final_position:
route.append(pos_list)
print("successful")
return
pos_x = position[0]
pos_y = position[1]
for direction in walk_route:
next_position = [pos_x+direction[0], pos_y+direction[1]]
if isValid(nums, next_position):
# 記住，這兒一定要用另一個list集合保存當前路線pos_list以及該路線下一個位置，方便回溯找到pos_list
# 如果直接對pos_list添加next_position，則不能回溯找到之前的pos_list
pos_list_copy = []
pos_list_copy.extend(pos_list)
pos_list_copy.append(next_position)
nums[pos_x, pos_y] = 0
back(next_position, pos_list_copy)
# 如果沒有找到出口，則將當前上一個位置0重置為1，回溯
nums[pos_x, pos_y] = 1


大家一對比就很清楚的看到，出口語句都是寫在最前面的，其實最主要的就是不能把出口語句放在for和while循環語句裡面，因為出口語句一定要方便整個函數退出，大家聽不懂的強行記住沒問題的，要是出了問題，也別來找我，啊哈哈哈哈哈。

2 遞歸函數的參數

這個遞歸函數的參數的設置也是有很大門道的，設置的好就很容易得到答案，否則弄大半天可能還是沒有一點反應。大家一定要記住一點：這個參數是隨著每一次的遞歸操作而發生改變的。而回溯法很關鍵的一點就是：如果當前操作行不通，如何回溯到上一步操作。大家繼續看上面貼的兩個遞歸函數的參數，會發現其參數都是要改變的，既然參數會發生改變，那麼我們要如何保存其上一步操作的值呢？大家可以再細細看看上述兩個函數的傳值操作。

八皇后問題的傳值操作

for index in range(nums):
Flag = conflict(queen_str, index)
# 如果當前位置的皇后是否與之前所有位置的皇后沒有衝突，則執行下述代碼
if Flag is False:
back(queen_str+str(index))


大家可以看到back(queen_str+str(index))這一步，其傳的參數就是queen_str+str(index) 其實想法就是不破壞當前參數的值，直接把當前值加上一個值(大家可以理解為定義了另一個非queen_str當前值的值給傳到下一次函數)，只要不破壞當前值，函數就能回溯。這一步很關鍵，大家可以好好品味。

for index in range(nums):
Flag = conflict(queen_str, index)
# 如果當前位置的皇后是否與之前所有位置的皇后沒有衝突，則執行下述代碼
if Flag is False:
queen_str = queen_str+str(index)
back(queen_str )


如果大家還有些疑惑的話，可以再把傳值操作改成這樣試試，你會發現結果會大相徑庭的，這裡就是破壞了當前值。

迷宮問題的傳值操作

if isValid(nums, next_position):
# 記住，這兒一定要用另一個list集合保存當前路線pos_list以及該路線下一個位置，方便回溯找到pos_list
# 如果直接對pos_list添加next_position，則不能回溯找到之前的pos_list
pos_list_copy = []
pos_list_copy.extend(pos_list)
pos_list_copy.append(next_position)
nums[pos_x, pos_y] = 0
back(next_position, pos_list_copy)
# 如果沒有找到出口，則將當前上一個位置0重置為1，回溯
nums[pos_x, pos_y] = 1


大家再可以參考迷宮操作的傳值操作理解。

關於參數，我還有一點就是強調：就是結果一定是要有一個全局參數來保存，這個全局參數不會隨著每一次的遞歸操作而隨時改變，它只是用來保存每一次遞歸操作成功時的結果，其它的不關它的事。你仔細看看這兩個程序也會發現：它們在一開始就定義了一個List空列表。大家也可以照搬的，凡是結果需要保存的題目90%以上就是要預先定義一個List空列表（不要問我這個90%數據是怎麼得來的哈，問了我也不知道，哈哈哈哈哈）

八皇后問題的List空列表

# 定義執行皇后問題的主函數
def queens(nums=8, queen_str=""):
"""
:param nums: int-->指代整個棋盤中想要存放皇后的個數
:param queen_str: str-->指代當前皇后存放之前的所有皇后的集合
:return:final_queens: List[int]-->指代最後符合要求的皇后的位置
"""
# 定義一個保存結果的List列表
final_queens = []


迷宮問題的List空列表

"""
迷宮問題，使用回溯法
"""
def maze(nums, start):
"""
:param nums: List[List[int]]-->指代所給的迷宮
:param start: List[int X, Y]-->指代起始點位置
:return: route: List[]
"""
# 定義最終路線的集合
route = []


3 遞歸函數的處理過程

這個過程是最關鍵的了，但是也很少有人能把它說清楚，當然也包括我。我想來想去，總結起來一句話就是：如果當前遞歸過程的處理參數符合要求，則執行相關賦值或其它操作，然後轉入下一次遞歸，如果下一次遞歸不能找到出口，則把之前相關賦值或其它操作重置為初始狀態。說的有些抽象，但我目前確實是說的這麼樣了，還需要自己好好看幾個題目，好好做幾道題目才能理解這層意思。大家也可以好好看看下述迷宮問題的處理過程。

迷宮問題的處理過程

nums[pos_x, pos_y] = 0
back(next_position, pos_list_copy)
# 如果沒有找到出口，則將當前上一個位置0重置為1，回溯
nums[pos_x, pos_y] = 1


2 迷宮問題

問題描述：

定義一個二維數組：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一個迷宮，其中的1表示牆壁，0表示可以走的路，只能橫著走或豎著走，不能斜著走，要求編程序找出從左上角到右下角的最短路線。

解題思路：

本題我才用的方法也是很常規的廣度優先搜索（BFS）也就是定義四個方向，即上下左右，對迷宮內每個可以通過的點執行該四個方向的操作。具體的操作我這兒就不說了，直接貼代碼吧！

迷宮問題代碼如下：

mport numpy as np

# 檢查當前位置是否有效
# 如果當前位置為0，則表示不能通過；
# 如果當前位置表示為1，則表示可以繼續通過
def isValid(nums, current_position):

:param nums: List[List[int]]-->指代所給的迷宮
:param current_position: List[int X, Y]-->指代當前坐標點位置
:return: boolean-->指代當前位置是否有效

pos_x = current_position[0]
pos_y = current_position[1]
if pos_x in range(len(nums)) and pos_y in range(len(nums)) and nums[pos_x, pos_y] == 1:
return True
else:
return False

"""
迷宮問題，使用回溯法
"""
def maze(nums, start):
"""
:param nums: List[List[int]]-->指代所給的迷宮
:param start: List[int X, Y]-->指代起始點位置
:return: route: List[]
"""
# 定義最終路線的集合
route = []
# 定義當前點上下左右移動方向的集合
walk_route = [[-1, 0], [0, -1], [1, 0], [0, 1]]
# 獲取迷宮的終點
nums_length = len(nums)
final_position = [nums_length-1, nums_length-1]

def back(position=start, pos_list=[start]):
# 該遞歸函數的出口
if position == final_position:
route.append(pos_list)
print("successful")
return
pos_x = position[0]
pos_y = position[1]
for direction in walk_route:
next_position = [pos_x+direction[0], pos_y+direction[1]]
if isValid(nums, next_position):
# 記住，這兒一定要用另一個list集合保存當前路線pos_list以及該路線下一個位置，方便回溯找到pos_list
# 如果直接對pos_list添加next_position，則不能回溯找到之前的pos_list
pos_list_copy = []
pos_list_copy.extend(pos_list)
pos_list_copy.append(next_position)
nums[pos_x, pos_y] = 0
back(next_position, pos_list_copy)
# 如果沒有找到出口，則將當前上一個位置0重置為1，回溯
nums[pos_x, pos_y] = 1

back()
return route

if __name__ == "__main__":
nums = [[1, 0, 0, 1, 0, 1], [1, 1, 1, 0, 1, 0], [0, 0, 1, 0, 1, 0], [0, 1, 1, 1, 0, 0], [0, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 1, 1]]
nums = np.array(nums)
print(nums)
current_position = [0, 0]
print(maze(nums, current_position))

該講的我在八皇后問題那兒都講到了，本題大家就用作檢驗方法和思考作用吧。

3 解數獨

問題描述

編寫一個程序，通過已填充的空格來解決數獨問題。

一個數獨的解法需遵循如下規則：

1. 數字 1-9 在每一行只能出現一次。
2. 數字 1-9 在每一列只能出現一次。
3. 數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。

空白格用 . 表示。

一個數獨。

答案被標成紅色。

Note:

• 給定的數獨序列只包含數字 1-9 和字元 . 。
• 你可以假設給定的數獨只有唯一解。
• 給定數獨永遠是 9x9 形式的。

思路：

這一題是LeetCode上面的第37題，確實是挺噁心的，當時做了兩三天。但如果你把它解答出來了，我覺得你對應回溯法的理解應該是差不多了。下面我還是直接貼代碼了，相關註解我都在代碼裏寫的很清楚了，大家應該很容易看得懂！

代碼如下：

import numpy as np

class Solution(object):
# 本題採用回溯法解決
# 當時在area3x3檢查時栽了跟頭
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
# board = np.array(board)

def back(board, position=[0, 0]):
# 如果當前數獨中沒有空白元素.，則說明查找成功了
if position == [-1, -1]:
print("successful")
return True
# 獲取當前位置的橫縱坐標
pos_x = position[0]
pos_y = position[1]
# 獲取當前位置的值
pos_value = board[pos_x][pos_y]
if pos_value == .:
for index in range(1, 10):
value = str(index)
if self.isValid(board, position, value) is True:
board[pos_x][pos_y] = value
next_position = self.getNextPosition(board, position)
if back(board, next_position) is True:
return True
else:
board[pos_x][pos_y] = .
else:
next_pos = self.getNextPosition(board, position)
back(board, next_pos)
return False

back(board)
return board

# 獲取下一個有效點的坐標位置
def getNextPosition(self, board, position):
next_x = position[0]
next_y = position[1]
while board[next_x][next_y] != .:
next_y += 1
if next_y >= len(board):
next_x += 1
next_y = 0
if next_x not in range(len(board)) or next_y not in range(len(board)):
return [-1, -1]
return [next_x, next_y]

# 判斷當前位置是否有效
def isValid(self, board, position, value):
"""
:param board: array[[]]-->指代所給的數獨列表
:param position: List[int x, y]-->指代所給的當前位置
:param value: str-->指代當前位置的值
:return: boolean-->若返回為True，則表示當前位置有效；反之，則無效
"""
board = np.array(board)
# 獲取當前位置的橫縱坐標
pos_x = position[0]
pos_y = position[1]
# 獲取當前位置橫縱坐標所對應的每一行每一列元素
pos_row = board[pos_x]
pos_col = board[:, pos_y]
# 如果當前位置的值value與其所在的每一行或者每一列的值重複，則表示當前值無效，返回False
if value in pos_row or value in pos_col:
return False
# 獲取當前位置點所在的3x3區域的位置
area3x3_x = pos_x//3*3
area3x3_y = pos_y//3*3
area3x3_batch = board[area3x3_x:area3x3_x+3, area3x3_y:area3x3_y+3]
# 如果當前位置的值value與其所在的3x3區域的值重複，則表示當前值無效，返回False
if value in area3x3_batch:
return False
return True

if __name__ == "__main__":
board = [[5, 3, ., ., 7, ., ., ., .],
[6, ., ., 1, 9, 5, ., ., .],
[., 9, 8, ., ., ., ., 6, .],
[8, ., ., ., 6, ., ., ., 3],
[4, ., ., 8, ., 3, ., ., 1],
[7, ., ., ., 2, ., ., ., 6],
[., 6, ., ., ., ., 2, 8, .],
[., ., ., 4, 1, 9, ., ., 5],
[., ., ., ., 8, ., ., 7, 9]]
result = Solution().solveSudoku(board)
print(np.array(result))

暫時就補充這麼多了，如果有更好的想法，我也會及時補充的，當然了，各位讀者如果有更nice的解題套路也希望大家積極分享！！！

推薦閱讀：

相關文章