回溯算法+對稱剪枝——從八皇后問題到數獨問題（二）

引入：

本節我們進一步完善八皇后問題，學習剪枝、八皇后殘局問題進一步領會邏輯編程的概念，深入體會回溯算法，回顧上一節提到的啟發搜索策略。

回顧：

八皇后問題：我們需要在一個空棋盤上放置 n 個皇后，使得任意兩個皇后不能在同一行、同一列或同一對角線上。

我們使用回溯算法逐行嘗試放置皇后，并通過沖突檢測剪枝無效的分支實現。

def spin(row):  # 回溯算法def is_valid(row, col):  def prt():# 主程序入口
spin(0)  # 從第 0 行開始求解
print(f"總共有 {sol_num} 種解法。")

現在問題在于，當我們輸入n=10時，解已經輸出2680個了，?跑了大概十幾秒鐘才出來。這時我們發現，這其中很大一部分解之間是可以通過旋轉對稱得到的，如果能消除這些由旋轉對稱得到的解，是否能提高速度呢？

顯然是可以的，在應用“對稱剪枝”后，n=10的輸出幾乎是一瞬間的事。

那么，剪枝是什么呢？

剪枝

剪枝就是在搜索或計算過程中提前終止無效路徑，從而減少不必要的計算。?

我們在上一節似乎做過這件事！

# 嘗試在當前行的每一列放置皇后
for col in range(n):if is_valid(row, col):  # 如果當前位置有效board[row] = col  # 放置皇后spin(row + 1)  # 遞歸處理下一行board[row] = -1  # 回溯，撤銷放置

沒錯，上一節設定is_valid()函數的手段就是剪枝！

通過is_valid()函數判斷該節點是否有解，若無解返回 False，則直接跳過后續遞歸，因為從這個樹杈長出去的其他枝干都無解，就剪枝了。

剪枝的類型

可行性剪枝：

當前節點不滿足約束條件，則剪枝。

最優性剪枝：

求最優解時，若當前局部解已劣于已知最優解，則剪枝。

啟發式剪枝：

利用經驗規則（啟發式函數）優先剪掉低概率分支。

還有接下來的

對稱剪枝：

若兩個解（或部分解）可以通過旋轉、鏡像、置換等對稱操作相互轉換，則它們是對稱等價的。

對稱剪枝的實現

顯然，將棋盤沿對稱軸分兩半，從第一行看兩側的遍歷路徑總是一樣的，因此我們考慮只計算一半情況的解。

但棋盤并不總是偶數X偶數的，遇到奇數怎么辦？

很簡單，單獨計算中間這一行即可！

因此，當棋盤為偶數時，我們只計算第一行一半的解，如果是奇數，則加上中間一列產生的解：

 # 對稱性剪枝：限制第一行的皇后位置if n > 0:for col in range(n // 2):  # 只考慮第一行的一半列board[0] = colspin(1)  # 從第二行開始遞歸# 如果 n 是奇數，單獨處理中間列if n % 2 == 1:board[0] = n // 2spin(1)

靜態剪枝 VS 動態剪枝

你可能想問：為什么只對第一行剪枝，第二行第三行呢？是不是剪得越多算得越快呢？

實則不然，這就是對稱剪枝策略的核心——通常我們只對搜索樹的淺層（如第一行）進行靜態剪枝。

我們之所以能對第一行對稱剪枝是因為其對稱性未被破壞，

而一旦放置皇后后，后續的對稱性就會被破壞：例如第一行皇后放在列0，棋盤就會失去90°旋轉對稱性。

因此進行深層剪枝時，往往需要動態判斷是否有某種對稱性，其計算成本（包括分解和遞歸）和動態存儲空間都是階乘級的上漲。

結論：雖然動態剪枝減少了節點數，但增加的判斷時間反而導致總耗時上升。

因此我們只對已知初始狀態的第一行進行對稱剪枝！

完整代碼僅僅是在之前代碼上添加了對稱性剪枝這一部分：

def solve_n_queens(n):def is_valid(board, row, col):"""檢查當前位置 (row, col) 是否有效"""for i in range(row):  if board[i] == col or abs(i - row) == abs(board[i] - col):return Falsereturn Truedef spin(row):"""回溯函數"""nonlocal sol_numif row == n:  # 如果所有行都放置了皇后sol_num += 1returnfor col in range(n):if is_valid(board, row, col):  # 剪枝：只有有效位置才繼續board[row] = col  # 放置皇后spin(row + 1)  # 遞歸處理下一行board[row] = -1  # 回溯，撤銷放置# 初始化board = [-1] * n  # board[i] 表示第 i 行中皇后所在的列號sol_num = 0# 對稱性剪枝：限制第一行的皇后位置if n > 0:for col in range(n // 2):  # 只考慮第一行的一半列board[0] = colspin(1)  # 從第二行開始遞歸# 如果 n 是奇數，單獨處理中間列if n % 2 == 1:board[0] = n // 2spin(1)return sol_numn = int(input("請輸入棋盤大小 n："))
sol_num = solve_n_queens(n)
print(f"總共有 {sol_num} 種解法。")

皇后殘局問題

在一個 n x n 的國際象棋棋盤上，已放置若干皇后且互不攻擊，需繼續放置剩余皇后至 n 個，滿足任意兩皇后不在同一行、列或對角線上。

輸入：

輸入一個n，代表棋盤的大小。
輸入一個二維 n x n 的棋盤狀態，其中部分格子已經有皇后（用‘Q’表示），其余格子為空（用?'.'?表示）。

4
.Q..
...Q
....
....

輸出：

如果存在解，則輸出所有可能的完整解（即棋盤上放置了?n?個互不攻擊的皇后）。
如果無解，則輸出“無解”。

解法 1:
.Q..
...Q
Q...
..Q.共找到 1 種解法。

實現思路

我們考慮相較于一般皇后問題，殘局問題做了哪些改變？我們應該如何應對？

(1)?初始棋盤狀態

棋盤已經部分皇后——遍歷棋盤，保留在board中。

(2)?約束條件

固定的皇后增加了約束條件：新皇后不僅要滿足自身約束規則，還須與已固定的皇后兼容——輸入時先對殘局檢查沖突，放入新皇后時直接跳過這些行。

(3)?解空間

固定的皇后減少了搜索空間——直接跳過。

若固定皇后間存在沖突，則直接無解。

因此，修改原思路：

① 初始化與解析：首先初始化容器并解析棋盤。

② 初始檢查：檢查初始棋盤自身是否沖突

③ 調用回溯函數：不沖突則調用回溯函數

④ 結束判斷：回溯函數先檢查當前是否滿足結束條件（所有行都有皇后）

⑤?遍歷每一列：若這一列有固定皇后則跳過

⑥ 約束條件：否則判斷是否滿足約束條件。若滿足，則保存當前狀態，同時為了下一次遍歷到這里時這一層是空的（有皇后就會被略過）要將這一層還原為空，接著處理下一行。

⑦ 如果不滿足約束條件則自動判斷當前是否是這一行的最后一個元素，如果是，證明這一行無論皇后放在哪都無解，因此自動返回上一行重新找解

⑧ 如果不是，就繼續遍歷下一列直到找到可以放皇后的位置。

代碼實現：

一、初始化與解析：

初始化列表參考上一節：

# 初始化
board = [-1] * n  # 當前棋盤狀態（-1 表示未放置皇后）
solutions = []  # 存儲所有解
sol_num = 0

首先考慮如何接收這個殘局，

在上一節中，我們用列表board[]保存每一行皇后的位置，
因此我們的任務是如何從nxn的輸入中讀取Q的位置存進board[]列表中。

由于輸入是 n x n 的，我們使用for_in_range(n)循環n次接收n行的輸入，并將其存入初始表格initial_board[]中。

initial_board = [input().strip() for _ in range(n)]  # 接收一維數組

其中 for _ in 僅表示循環 n 次，不關心當前迭代的索引，strip()去掉每一行輸入的換行符。

輸入后initial_board的內容是：

initial_board = ['.Q..', '...Q', '....', '....']

接著直接調用問題解決函數：

if __name__ == "__main__":n = int(input("請輸入棋盤大小 n："))print("請輸入初始棋盤狀態（'Q' 表示皇后，'.' 表示空位）：")initial_board = [input().strip() for _ in range(n)]  # 接收一維數組solve_n_queens_with_given_board(n, initial_board)

接著是如何解析initial_board[]中皇后的位置，我們考慮遍歷每一個元素“字符串”，在這個字符串中尋找是否有'Q'字符，如果有就在board對應位置保存，沒有就跳過。

 # 解析初始棋盤
for r in range(n):if initial_board第r元素有'Q'：c = 'Q'的位置board[第r元素] = 'Q'的位置else:pass

那么如何從字符串中找指定字符呢？

我們想到index()函數，他會返回對象中與要找字符匹配的第一個元素的下標。

X = '1919810'
print(X.index('9'))
#輸出1

代碼也就很容易想到了：

 # 解析初始棋盤for r in range(n):try:c = initial_board[r].index('Q')  # 找到 'Q' 的列索引board[r] = c  # 固定該位置except ValueError:pass  # 如果該行沒有 'Q'，跳過

二、初始檢查：檢查初始棋盤自身是否沖突

由于上一節的約束條件在這里不變，因此保留is_valid()判斷函數。

那么接下來的任務就是檢查初始棋盤是否沖突了

剛剛我們將initial_board的內容放到了board中，因此我們對board每一元素遍歷，如果其值不為-1證明這一行有固定皇后，觸發沖突判斷

is_valid()的參數列表是

def is_valid(board, row, col):

因此我們還要把當前位置傳給他，假設遍歷到第r行，且有'Q'元素，則其位置為board[r]，即縱坐標為board[r]：

def is_valid(board, r, board[r]):

完整代碼：?

    # 檢查初始棋盤是否有沖突for r in range(n):if board[r] != -1:  # 如果當前行有固定皇后if not is_valid(board, r, board[r]):print("無解")return

三、回溯算法：?

由于固定皇后的存在，解空間減小了，因此遍歷行時，會有兩種情況：

①該行已有固定皇后，則檢測是否沖突。

②該行為空，則和普通皇后問題一樣進行列遍歷找地方放皇后。

當然，在執行遍歷行前，還要優先進行終點判定：

如果當前行是最后一行則將棋盤狀態保存在result中，[:]代表選擇全部。同時解數量加一。

if row == n:  # 如果所有行都放置了皇后result.append(board[:])sol_num += 1return

?對于情況①，如果固定皇后存在，則進行沖突判斷。

由于我們在解析initial_board[]的時候已經記錄過固定皇后的位置了，其實if下面那一行是多余的，但為了與情況②保存代碼對稱，我們依然保留。

if initial_board[row] != -1:  # 如果當前行已經有固定的皇后if is_valid(board, row, initial_board[row]):  # 檢查是否沖突board[row] = initial_board[row]spin(row + 1)board[row] = -1else:  # 如果沖突，則無解return

對于情況② ，如果該行為空，則正常進行列遍歷，找合適位置放入皇后。

else:  # 如果當前行沒有固定的皇后for col in range(n):if is_valid(board, row, col):  # 剪枝：只有有效位置才繼續board[row] = col  # 放置皇后spin(row + 1)  # 遞歸處理下一行board[row] = -1  # 回溯，撤銷放置

?四、輸出函數

你可能已經注意到了，我們找到解后并沒有立馬輸出，而是保存在result[]中。

因此輸出函數就是要從result[]中迭代輸出解（用上一節的prt()也是可以的，星馬想稍稍講講enumerate的用法）

首先先判斷有沒有解，直接看sol_num是否為零即可。

如果有解，就考慮如何從result中輸出解。

在使用enumerate前，最重要的事就是確定迭代對象的結構是什么樣的，即result是如何存儲解的狀態的？

還記得result是如何來的嗎？我們直接將board的全部狀態裝載進去了。

result.append(board[:])

其結構就是由board[]構成的解空間。?

result = [[1, 3, 0, 2],  # 解法 1[2, 0, 3, 1]   # 解法 2
]

?接下來，我們的輸出要求也是“解法X：解的結構”。

而result的存儲格式正好是“解法：解的結構”的鍵值對結構！

enumerate迭代器用于在遍歷容器時同時獲取元素的索引和值，也就是說他能同時返回我們想要的東西。

語法為：

for index, value in enumerate(iterable, start=0):

index是索引鍵，value是對應值，我們分別取idx和sol。

后面的邏輯和皇后問題一樣，先初始化輸出行為“...........”，從對應解取對應存放Q的位置，更改為'Q'

for idx, sol in enumerate(result):print(f"解法 {idx + 1}:")for r in range(n):line = ['.'] * nline[sol[r]] = 'Q'print(' '.join(line))print()

完整代碼：?

# 輸出結果
if sol_num == 0:print("無解")
else:for idx, sol in enumerate(result):print(f"解法 {idx + 1}:")for r in range(n):line = ['.'] * nline[sol[r]] = 'Q'print(' '.join(line))print()print(f"共找到 {sol_num} 種解法。")

至此，所有核心代碼結束，接下來的任務就是裝在一起就好啦~

我們將回溯函數、約束條件函數和執行邏輯全部封裝在solve_n_queens_with_given_board這個函數中，由于我們要獲取輸入n和殘局情況initial_board，因此要作為參數傳入。

def solve_n_queens_with_given_board(n, initial_board):def is_valid(board, row, col):#約束條件判斷def spin(row):#回溯函數#################################################################
調用solve_n_queens_with_given_board()后從這里開始執行，前面是函數聲明# 初始化board = [-1] * n  # 初始化當前棋盤狀態（-1 表示未放置皇后）result = []  # 存儲所有解sol_num = 0# 解析初始棋盤for r in range(n):# 檢查初始棋盤是否有沖突for r in range(n):# 開始回溯spin(0)# 輸出結果if sol_num == 0:無解else:輸出解# 示例調用
if __name__ == "__main__":n = int(input("請輸入棋盤大小 n："))print("請輸入初始棋盤狀態（'Q' 表示皇后，'.' 表示空位）：")initial_board = [input().strip() for _ in range(n)]  # 接收一維數組solve_n_queens_with_given_board(n, initial_board)

完整代碼：

def solve_n_queens_with_given_board(n, initial_board):def is_valid(board, row, col):"""檢查當前位置 (row, col) 是否有效"""for i in range(row):  # 檢查當前行之前的行if board[i] == col or abs(i - row) == abs(board[i] - col):return Falsereturn Truedef spin(row):"""回溯函數"""nonlocal sol_numif row == n:  # 如果所有行都放置了皇后result.append(board[:])sol_num += 1returnif initial_board[row] != -1:  # 如果當前行已經有固定的皇后if is_valid(board, row, initial_board[row]):  # 檢查是否沖突board[row] = initial_board[row]spin(row + 1)board[row] = -1else:  # 如果沖突，則無解returnelse:  # 如果當前行沒有固定的皇后for col in range(n):if is_valid(board, row, col):  # 剪枝：只有有效位置才繼續board[row] = col  # 放置皇后spin(row + 1)  # 遞歸處理下一行board[row] = -1  # 回溯，撤銷放置# 初始化board = [-1] * n  # 當前棋盤狀態（-1 表示未放置皇后）result = []  # 存儲所有解sol_num = 0# 解析初始棋盤for r in range(n):try:c = initial_board[r].index('Q')  # 找到 'Q' 的列索引board[r] = c  # 固定該位置except ValueError:pass  # 如果該行沒有 'Q'，跳過# 檢查初始棋盤是否有沖突for r in range(n):if board[r] != -1:  # 如果當前行有固定皇后if not is_valid(board, r, board[r]):print("無解")return# 開始回溯spin(0)# 輸出結果if sol_num == 0:print("無解")else:for idx, sol in enumerate(result):print(f"解法 {idx + 1}:")for r in range(n):line = ['.'] * nline[sol[r]] = 'Q'print(' '.join(line))print()print(f"共找到 {sol_num} 種解法。")# 示例調用
if __name__ == "__main__":n = int(input("請輸入棋盤大小 n："))print("請輸入初始棋盤狀態（'Q' 表示皇后，'.' 表示空位）：")initial_board = [input().strip() for _ in range(n)]  # 接收一維數組solve_n_queens_with_given_board(n, initial_board)