Hello 演算法 n 皇后問題深度解析回溯、剪枝與多語言實現【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo導讀本文以《Hello 演算法》繁體中文版 n 皇后問題 章節為主體完整講解經典回溯問題「n 皇后」的問題定義、三大約束條件、逐行放置策略、列與對角線剪枝技巧以及時間/空間複雜度分析。文中將結合本倉庫 Python、Java、C、Go、TypeScript、C 等多語言源碼展示同一套回溯框架在不同程式語言中的落地實現讀者讀完後既能掌握 n 皇后的標準解法也能理解回溯演算法「嘗試—剪枝—回退」的通用思維。問題定義在 n×n 棋盤上放置 n 個皇后根據國際象棋規則皇后可以攻擊與其同處一行、一列或一條斜線上的棋子。n 皇后問題要求給定 $n$ 個皇后與一個 $n \times n$ 大小的棋盤找出所有讓皇后之間無法相互攻擊的擺放方案。如下圖所示當 $n 4$ 時總共可以找到兩個解。從回溯演算法的角度審視這個問題$n \times n$ 大小的棋盤共有 $n^2$ 個格子這些格子構成了所有的選擇choices在逐個放置皇后的過程中棋盤狀態不斷變化每個時刻的棋盤就是狀態state每一次放置皇后都伴隨「嘗試、遞迴、回退」三個步驟這是回溯演算法的標準流程與 backtracking_algorithm.md 中描述的框架一脈相承。三大約束條件行、列與對角線本題的解必須同時滿足三個約束條件多個皇后不能在同一行、同一列、同一條對角線上。需要特別注意的是對角線分為兩種主對角線\從左上到右下方向次對角線/從右上到左下方向。此外由於矩陣的起點位於左上角行索引從上到下遞增、列索引從左到右遞增這決定了後續對角線索引計算的方式。逐行放置策略將行約束化為搜索結構皇后的數量與棋盤行數同為 $n$因此可以推導出一個關鍵結論棋盤每行都允許且只允許放置一個皇后。基於此我們可以採取逐行放置策略從第一行開始在每行放置一個皇后直到最後一行結束。下圖展示了 4 皇后問題的逐行放置過程受限於畫幅圖中僅展開了第一行的一個搜索分支並對不滿足列約束與對角線約束的方案進行了剪枝從本質上看逐行放置策略本身就起到了剪枝的作用——它直接避免了「同一行出現多個皇后」的所有搜索分支使搜索樹的規模從「在 $n^2$ 個格子中選 $n$ 個」縮小為「每行選一列」這是 n 皇后問題得以高效求解的結構性基礎。列與對角線剪枝用三個布林陣列記錄衝突列約束陣列cols為了滿足列約束可以使用一個長度為 $n$ 的布林陣列cols記錄每一列是否已有皇后。每次決定放置前透過cols將已有皇后的列剪枝並在回溯過程中動態更新cols的狀態。主對角線約束陣列diags1設棋盤中某格子的行列索引為 $(row, col)$選定某一條主對角線會發現該對角線上所有格子的 $row - col$ 為恆定值。也就是說如果兩個格子滿足 $row_1 - col_1 row_2 - col_2$則它們一定位於同一條主對角線上。利用此規律可以借助陣列diags1記錄每一條主對角線上是否已有皇后。次對角線約束陣列diags2同理次對角線上所有格子的 $row col$ 是恆定值因此可以用陣列diags2處理次對角線約束。索引範圍與陣列長度$n$ 維方陣中$row - col$ 的範圍是 $[-n 1, n - 1]$共 $2n - 1$ 個取值$row col$ 的範圍是 $[0, 2n - 2]$共 $2n - 1$ 個取值。因此主對角線與次對角線的數量都為 $2n - 1$即陣列diags1和diags2的長度都為 $2n - 1$。在實際程式碼中為了讓row - col的負值也能作為合法的陣列索引需要加上偏移量 $n - 1$即diag1 row - col n - 1。程式碼實現回溯框架的多語言落地本倉庫在 14 種語言中實現了完全同構的 n 皇后解法。以下先以 Python 版 為例講解核心邏輯再給出其他語言的對應位置。Python 實現骨架def backtrack(row, n, state, res, cols, diags1, diags2): 回溯演算法n 皇后 # 當放置完所有行時記錄解 if row n: res.append([list(r) for r in state]) return # 遍歷所有列 for col in range(n): # 計算該格子對應的主對角線和次對角線索引 diag1 row - col n - 1 diag2 row col # 剪枝不允許該格子所在列、主對角線、次對角線上存在皇后 if not cols[col] and not diags1[diag1] and not diags2[diag2]: # 嘗試將皇后放置在該格子 state[row][col] Q cols[col] diags1[diag1] diags2[diag2] True # 遞迴放置下一行 backtrack(row 1, n, state, res, cols, diags1, diags2) # 回退將該格子恢復為空位 state[row][col] # cols[col] diags1[diag1] diags2[diag2] False對應的入口函式n_queens(n)負責初始化 $n \times n$ 的棋盤state其中Q代表皇后、#代表空位建立長度為 $n$ 的cols與長度為 $2n - 1$ 的diags1、diags2從第 0 行開始呼叫backtrack最終返回所有解組成的res。多語言對照同一套邏輯在倉庫各語言目錄下均有完整可執行的實作語言檔案路徑實現特點Pythonn_queens.py以巢狀 list 表示棋盤解以深拷貝方式存入resJavan_queens.java使用ListListString記錄解時逐行new ArrayList(sRow)拷貝Cn_queens.cpp使用vectorvectorstring記錄解時直接push_back(state)Gon_queens.go以指標傳遞state、res與三個布林陣列記錄解時手動copyTypeScriptn_queens.ts記錄解時以state.map(row row.slice())複製二維陣列Cn_queens.c以char state[MAX_SIZE][MAX_SIZE]與三級指標char***儲存結果需手動malloc/free以 Java 版 為例核心backtrack方法與 Python 版結構完全一致抵達row n時建立copyState快照加入res否則遍歷每一列計算diag1 row - col n - 1與diag2 row col在三者皆為false時執行「放置皇后 → 遞迴 → 回退復原」的標準三步驟。這種「記錄解時深拷貝」的做法保證了回溯過程中的狀態回退不會污染已保存的解。複雜度分析時間複雜度$O(n! \cdot n^2)$逐行放置 $n$ 次僅考慮列約束時從第一行到最後一行分別有 $n$、$n-1$、$\dots$、$2$、$1$ 個選擇即 $O(n!)$ 時間每當記錄一個解時需要複製矩陣state並加入res複製操作耗費 $O(n^2)$ 時間。因此總體時間複雜度為 $O(n! \cdot n^2)$。實際上對角線約束的剪枝能大幅縮小搜索空間真實搜尋效率往往優於該上界。空間複雜度$O(n^2)$陣列state佔用 $O(n^2)$ 空間陣列cols、diags1、diags2各佔用 $O(n)$ 空間最大遞迴深度為 $n$堆疊幀空間為 $O(n)$。因此空間複雜度為 $O(n^2)$主要由棋盤狀態state主導。執行與驗證各語言源碼均附帶 Driver Code默認以 $n 4$ 為例執行並輸出結果。以 Python 版 為例執行後會輸出輸入棋盤長寬為 4 皇后放置方案共有 2 種 -------------------- [#, Q, #, #] [#, #, #, Q] [Q, #, #, #] [#, #, Q, #] -------------------- [#, #, Q, #] [Q, #, #, #] [#, #, #, Q] [#, Q, #, #]輸出結果與文首給出的 4 皇后兩個解完全對應可直接用於驗證演算法正確性。讀者也可以將n改為 88 皇后共有 92 個解或更大的值觀察剪枝效率與搜索規模的關係——這正是回溯演算法從理論到實戰的最佳練習。總結n 皇后問題是回溯演算法的經典範例其核心思想可以濃縮為三點逐行放置策略把「每行只能放一個皇后」內建為搜索結構從根源上消除同行衝突三個布林陣列cols、diags1、diags2以 $O(1)$ 時間完成列與兩類對角線的衝突檢測配合 $row - col$ 與 $row col$ 的恆定值規律實現高效剪枝「嘗試—遞迴—回退」的標準回溯流程在 Hello 演算法 的 Python、Java、C、Go、TypeScript、C 等 14 種語言實現中保持一致是跨語言遷移回溯演算法思維的最佳教材。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考