1. 從“N車(chē)”問(wèn)題看藍(lán)橋杯算法訓(xùn)練的核心邏輯最近在整理藍(lán)橋杯的歷年真題和訓(xùn)練題發(fā)現(xiàn)很多同學(xué)對(duì)“ALGO-969 N車(chē)”這類(lèi)題目感到困惑。題目名字聽(tīng)起來(lái)有點(diǎn)抽象其實(shí)就是經(jīng)典的“N皇后”問(wèn)題的一個(gè)變種或者更準(zhǔn)確地說(shuō)是“車(chē)”Rook在棋盤(pán)上的擺放問(wèn)題。這屬于回溯算法的經(jīng)典應(yīng)用場(chǎng)景也是藍(lán)橋杯從基礎(chǔ)到提高階段必考的題型之一。很多人在初次接觸時(shí)會(huì)試圖去死記硬背“八皇后”的代碼模板但一旦題目條件稍有變化比如從“皇后”換成“車(chē)”或者棋盤(pán)形狀、約束條件改變就立刻不會(huì)做了。這背后的根本原因是沒(méi)有理解回溯算法解決這類(lèi)“棋盤(pán)放置”問(wèn)題的通用框架和核心思想?！癗車(chē)”問(wèn)題可以這樣描述在一個(gè)N×N的棋盤(pán)上放置N個(gè)車(chē)使得它們彼此之間不能相互攻擊。我們知道車(chē)的攻擊規(guī)則是直線(xiàn)即同一行或同一列不能有兩個(gè)車(chē)。這聽(tīng)起來(lái)比“皇后”還能斜線(xiàn)攻擊簡(jiǎn)單但它訓(xùn)練的是同樣的解題肌肉——如何系統(tǒng)性地、不重不漏地枚舉所有可能解并在過(guò)程中利用約束條件進(jìn)行“剪枝”避免無(wú)效搜索。這道題是理解回溯算法“狀態(tài)空間樹(shù)”和“剪枝優(yōu)化”的絕佳入門(mén)。通過(guò)它我們可以把看似復(fù)雜的搜索問(wèn)題拆解成清晰的遞歸步驟和條件判斷這個(gè)思維模式能應(yīng)用到無(wú)數(shù)其他場(chǎng)景比如數(shù)獨(dú)、全排列、組合選擇等等。接下來(lái)我就以“ALGO-969 N車(chē)”為引子帶你徹底吃透這類(lèi)問(wèn)題的解法并分享一些在藍(lán)橋杯賽場(chǎng)上的實(shí)戰(zhàn)編碼技巧和避坑經(jīng)驗(yàn)。2. N車(chē)問(wèn)題的數(shù)學(xué)模型與回溯算法框架2.1 問(wèn)題定義與狀態(tài)表示首先我們把問(wèn)題從自然語(yǔ)言轉(zhuǎn)化為精確的數(shù)學(xué)模型。在一個(gè)N×N的棋盤(pán)通常用二維數(shù)組表示上放置N個(gè)車(chē)。每個(gè)車(chē)占據(jù)一個(gè)格子。約束條件是任何兩個(gè)車(chē)不能位于同一行也不能位于同一列。這里有一個(gè)非常重要的隱含條件也是簡(jiǎn)化問(wèn)題的關(guān)鍵因?yàn)樾枰胖肗個(gè)車(chē)而棋盤(pán)只有N行所以最終解必然滿(mǎn)足每行有且僅有一個(gè)車(chē)。同理每列也有且僅有一個(gè)車(chē)。這個(gè)洞察直接決定了我們的搜索策略我們不需要像最樸素的搜索那樣去枚舉棋盤(pán)上N×N個(gè)格子中選N個(gè)的所有組合那將是C(N^2, N)復(fù)雜度爆炸。我們可以按行來(lái)放置。因此我們的搜索狀態(tài)可以這樣定義遞歸深度代表我們正在放置第幾行的車(chē)從第0行到第N-1行。狀態(tài)記錄我們需要一個(gè)數(shù)組或集合來(lái)記錄哪些列已經(jīng)被占用了。因?yàn)槲覀兪前葱蟹胖玫闹灰ＷC每一行放置時(shí)選擇的列沒(méi)有被之前的車(chē)占用即可。這樣我們的搜索空間就從“在棋盤(pán)上選點(diǎn)”變成了“為每一行選擇一個(gè)未被占用的列”。這本質(zhì)上是一個(gè)全排列問(wèn)題求數(shù)字0到N-1的一個(gè)排列P其中P[i]表示第i行的車(chē)放置在第P[i]列。所有滿(mǎn)足條件的放置方案就是0到N-1的所有排列?？偡桨笖?shù)是N!。2.2 回溯算法模板解析基于上述分析我們可以套用回溯算法的標(biāo)準(zhǔn)框架?；厮莘ū举|(zhì)上是深度優(yōu)先搜索DFS在解空間樹(shù)上的應(yīng)用其核心結(jié)構(gòu)是一個(gè)遞歸函數(shù)。對(duì)于N車(chē)問(wèn)題模板如下def backtrack(row, n, used_cols, path, result): :param row: 當(dāng)前正在放置的行號(hào) :param n: 棋盤(pán)大小 :param used_cols: 記錄列占用狀態(tài)的列表used_cols[col]為T(mén)rue表示第col列已被占用 :param path: 記錄當(dāng)前放置方案的列表path[i] col 表示第i行放在了第col列 :param result: 保存所有合法方案的列表 # 1. 遞歸終止條件所有行都已放置完畢 if row n: # 找到一組解將當(dāng)前路徑的副本存入結(jié)果 result.append(path[:]) # 注意這里要用副本而不是引用 return # 2. 遍歷當(dāng)前行的所有選擇即所有列 for col in range(n): # 3. 剪枝判斷當(dāng)前列是否可用 if not used_cols[col]: # 4. 做出選擇放置車(chē)并更新?tīng)顟B(tài) used_cols[col] True path.append(col) # 或 path[row] col取決于path的初始化方式 # 5. 遞歸進(jìn)入下一層下一行 backtrack(row 1, n, used_cols, path, result) # 6. 撤銷(xiāo)選擇回溯恢復(fù)狀態(tài)以進(jìn)行同一層的下一個(gè)嘗試 used_cols[col] False path.pop() # 或 path[row] -1這個(gè)模板是解決所有排列型、組合型回溯問(wèn)題的基石。每一部分都有其明確的作用終止條件意味著我們成功構(gòu)建了一個(gè)完整的解。遍歷選擇在當(dāng)前狀態(tài)下第row行所有可能的列都是候選。剪枝判斷if not used_cols[col]就是根據(jù)“車(chē)”的規(guī)則進(jìn)行的剪枝直接跳過(guò)非法分支極大減少搜索量。做出選擇與撤銷(xiāo)選擇這是回溯法的精髓狀態(tài)在遞歸調(diào)用前后必須保持一致這樣才能保證搜索的正確性。注意result.append(path[:])這里的[:]是必須的。因?yàn)閜ath是一個(gè)列表對(duì)象在Python中直接append(path)加入的是該列表的引用。后續(xù)的回溯操作會(huì)修改path的內(nèi)容導(dǎo)致之前存入result的結(jié)果也被意外修改。使用path[:]創(chuàng)建了一個(gè)新的列表副本從而保存了當(dāng)前時(shí)刻的快照。2.3 初始化與調(diào)用在主函數(shù)中我們這樣初始化并調(diào)用回溯函數(shù)def solveNQueens(n): result [] # 存儲(chǔ)所有解 used_cols [False] * n # 列占用狀態(tài)初始都為False path [] # 當(dāng)前路徑也可以初始化為[-1]*n然后用索引賦值 backtrack(0, n, used_cols, path, result) return result # 例如求解4車(chē)問(wèn)題 solutions solveNQueens(4) print(f總共有 {len(solutions)} 種放置方案) for sol in solutions: print(sol) # 輸出如 [1, 3, 0, 2]表示第0行放1列第1行放3列...這個(gè)基礎(chǔ)版本已經(jīng)可以正確求出N車(chē)問(wèn)題的所有解了。對(duì)于藍(lán)橋杯的“ALGO-969”題目通常要求輸出方案數(shù)或者具體的擺放。理解這個(gè)框架是第一步。3. 算法優(yōu)化與空間復(fù)雜度分析雖然基礎(chǔ)回溯法已經(jīng)可以工作但在藍(lán)橋杯這種對(duì)時(shí)間和空間有嚴(yán)格限制的競(jìng)賽中我們還需要考慮優(yōu)化。對(duì)于N車(chē)問(wèn)題最主要的優(yōu)化點(diǎn)在于狀態(tài)記錄的數(shù)據(jù)結(jié)構(gòu)。3.1 狀態(tài)記錄的位運(yùn)算優(yōu)化在上面的代碼中我們使用了一個(gè)布爾列表used_cols來(lái)記錄列占用情況。每次檢查if not used_cols[col]是O(1)操作這已經(jīng)很快了。但是當(dāng)N較大時(shí)比如N15遞歸深度和狀態(tài)拷貝可能會(huì)成為瓶頸。我們可以使用**位圖Bitmask**來(lái)優(yōu)化。用一個(gè)整型變量cols_mask的二進(jìn)制位來(lái)表示列的占用情況。假設(shè)N8那么cols_mask是一個(gè)8位的二進(jìn)制數(shù)實(shí)際上用int的32位足夠。第i位為1表示第i列已被占用為0表示空閑。def backtrack_bitmask(row, n, cols_mask, path, result): if row n: result.append(path[:]) return # 計(jì)算當(dāng)前所有可用的列cols_mask中為0的位 # 首先cols_mask中為1的位是已占用的列我們想要可用的列為0的位。 # 一個(gè)技巧是available_cols (~cols_mask) ((1 n) - 1) # (1 n) - 1 產(chǎn)生一個(gè)低n位全是1的掩碼用來(lái)確保只考慮前n位。 available_cols (~cols_mask) ((1 n) - 1) # 當(dāng)available_cols不為0時(shí)循環(huán)取出最低位的1代表一個(gè)可用的列 while available_cols: # 取出最低位的1所代表的列號(hào): col available_cols -available_cols # 但我們需要的是列索引而不是這個(gè)二進(jìn)制數(shù)。所以常用 lowbit available_cols -available_cols # 然后 col (lowbit.bit_length() - 1) lowbit available_cols -available_cols col (lowbit.bit_length() - 1) # 做出選擇設(shè)置該列為占用 new_cols_mask cols_mask | lowbit path.append(col) backtrack_bitmask(row 1, n, new_cols_mask, path, result) # 撤銷(xiāo)選擇 path.pop() # 注意cols_mask本身作為參數(shù)傳入在遞歸調(diào)用中使用了new_cols_mask所以本層cols_mask未變無(wú)需顯式恢復(fù) # 將最低位的1從available_cols中移除嘗試下一個(gè)可用列 available_cols (available_cols - 1)位運(yùn)算優(yōu)化的優(yōu)勢(shì)極快的狀態(tài)檢查與更新位運(yùn)算與、或、非、移位是CPU最基本的指令速度遠(yuǎn)快于列表的索引和賦值。狀態(tài)壓縮用一個(gè)整數(shù)就代替了一個(gè)長(zhǎng)度為N的列表節(jié)省了大量?jī)?nèi)存尤其是在遞歸深度很深時(shí)。遍歷可用列的效率while available_cols循環(huán)直接遍歷所有為1的位即可用列避免了for col in range(n)中無(wú)效的循環(huán)檢查。對(duì)于N15的問(wèn)題基礎(chǔ)版本完全夠用。但如果你在訓(xùn)練中遇到N更大比如20左右的變種題或者需要極致性能時(shí)位運(yùn)算技巧就非常關(guān)鍵。這也是藍(lán)橋杯提高組甚至國(guó)賽階段可能考察的點(diǎn)。3.2 路徑記錄的空間優(yōu)化在上面的代碼中我們使用path列表記錄當(dāng)前解。另一種常見(jiàn)寫(xiě)法是初始化一個(gè)固定長(zhǎng)度的列表path [-1] * n然后在遞歸中通過(guò)索引賦值path[row] col。這樣做的好處是path在整個(gè)遞歸過(guò)程中只有一份通過(guò)索引修改其元素在回溯時(shí)也通過(guò)索引重置path[row] -1。這避免了append和pop操作也避免了在保存結(jié)果時(shí)頻繁創(chuàng)建列表副本雖然path[:]還是需要。對(duì)于純粹求方案數(shù)而不需要記錄具體解的情況甚至可以省略path只維護(hù)used_cols或cols_mask。3.3 時(shí)間復(fù)雜度與可行性N車(chē)問(wèn)題的時(shí)間復(fù)雜度就是搜索樹(shù)中節(jié)點(diǎn)的數(shù)量。由于每層遞歸的選擇都在減少這是一個(gè)典型的排列樹(shù)。時(shí)間復(fù)雜度是O(N!)。這意味著當(dāng)N10時(shí)10! 3,628,800還在可接受范圍。當(dāng)N12時(shí)12! ≈ 4.79億在普通計(jì)算機(jī)上遞歸回溯就可能需要數(shù)秒甚至更長(zhǎng)時(shí)間。當(dāng)N15時(shí)15!是一個(gè)天文數(shù)字完全不可行。所以純粹的、無(wú)剪枝的回溯法求解N車(chē)問(wèn)題的所有解其N(xiāo)的實(shí)用上限大約在10-12。這也是為什么藍(lán)橋杯的基礎(chǔ)練習(xí)中N通常不會(huì)太大。題目可能會(huì)要求輸出方案數(shù)而不是所有具體方案這樣我們可以用深度優(yōu)先搜索配合記憶化或者動(dòng)態(tài)規(guī)劃來(lái)計(jì)數(shù)這又是另一個(gè)優(yōu)化方向了。4. 從N車(chē)到N皇后理解攻擊規(guī)則的擴(kuò)展理解了N車(chē)再去看經(jīng)典的N皇后問(wèn)題就豁然開(kāi)朗了。N皇后的約束更強(qiáng)不能同行、同列、同斜線(xiàn)。斜線(xiàn)攻擊規(guī)則是主要的難點(diǎn)。4.1 斜線(xiàn)規(guī)則的數(shù)學(xué)表達(dá)棋盤(pán)上的斜線(xiàn)分為兩種主對(duì)角線(xiàn)左上到右下和副對(duì)角線(xiàn)右上到左下。在同一條主對(duì)角線(xiàn)上的格子其行號(hào)減去列號(hào)的值是相等的。即row - col constant。在同一條副對(duì)角線(xiàn)上的格子其行號(hào)加上列號(hào)的值是相等的。即row col constant。因此我們可以用兩個(gè)額外的數(shù)組或集合來(lái)記錄兩條斜線(xiàn)方向的占用情況。diag1_used記錄row - col值是否被占用。由于row - col的范圍是[-(n-1), n-1]共2n-1個(gè)值我們可以將其偏移n-1映射到數(shù)組索引[0, 2n-2]。diag2_used記錄row col值是否被占用。其范圍是[0, 2n-2]共2n-1個(gè)值直接作為索引即可。4.2 N皇后回溯代碼實(shí)現(xiàn)在N車(chē)代碼的基礎(chǔ)上增加兩個(gè)用于記錄斜線(xiàn)狀態(tài)的數(shù)組即可。def backtrack_queen(row, n, used_cols, used_diag1, used_diag2, path, result): if row n: result.append(path[:]) return for col in range(n): d1 row - col n - 1 # 偏移保證索引非負(fù) d2 row col if not used_cols[col] and not used_diag1[d1] and not used_diag2[d2]: # 做出選擇 used_cols[col] True used_diag1[d1] True used_diag2[d2] True path.append(col) backtrack_queen(row 1, n, used_cols, used_diag1, used_diag2, path, result) # 撤銷(xiāo)選擇 used_cols[col] False used_diag1[d1] False used_diag2[d2] False path.pop()同樣斜線(xiàn)狀態(tài)也可以用位運(yùn)算優(yōu)化但邏輯會(huì)更復(fù)雜一些因?yàn)樾枰獌蓚€(gè)長(zhǎng)度為2n-1的位圖。對(duì)于初學(xué)者先用數(shù)組理解清楚原理更重要。4.3 一個(gè)常見(jiàn)的誤解與糾正很多初學(xué)者在寫(xiě)N皇后時(shí)會(huì)嘗試在遞歸函數(shù)里用一個(gè)循環(huán)去檢查當(dāng)前放置位置(row, col)是否與之前放置的所有皇后沖突。例如for prev_row in range(row): prev_col path[prev_row] if prev_col col or abs(row - prev_row) abs(col - prev_col): conflict True break這種方法在邏輯上是正確的但它的時(shí)間復(fù)雜度是O(N) per placement。而使用used_cols,used_diag1,used_diag2數(shù)組的方法檢查沖突是O(1)的。當(dāng)N較大時(shí)前者的效率會(huì)低很多。在算法競(jìng)賽中能用O(1)時(shí)間完成的狀態(tài)檢查和更新絕不要用O(N)的方法。這是一個(gè)非常重要的優(yōu)化思想。5. 藍(lán)橋杯真題實(shí)戰(zhàn)與解題策略“ALGO-969 N車(chē)”這類(lèi)題目在藍(lán)橋杯系統(tǒng)中通常屬于“算法訓(xùn)練”或“基礎(chǔ)練習(xí)”模塊。它的目的不是考倒你而是確保你掌握了回溯法的基本思想和編碼實(shí)現(xiàn)。在實(shí)戰(zhàn)中你可能會(huì)遇到以下幾種變體5.1 變體一求方案數(shù)而非具體方案這是最常見(jiàn)的考法。題目可能只要求輸出有多少種不同的放置方法。這時(shí)候我們不需要維護(hù)path和result列表來(lái)存儲(chǔ)每一個(gè)解只需要一個(gè)全局計(jì)數(shù)器count在遞歸到達(dá)葉子節(jié)點(diǎn)row n時(shí)遞增即可。這可以節(jié)省大量存儲(chǔ)具體方案的內(nèi)存。count 0 def backtrack_count(row, n, used_cols): global count if row n: count 1 return for col in range(n): if not used_cols[col]: used_cols[col] True backtrack_count(row 1, n, used_cols) used_cols[col] False # 調(diào)用 n 8 used [False] * n backtrack_count(0, n, used) print(count)5.2 變體二棋盤(pán)存在障礙物題目可能給出一個(gè)N×N的棋盤(pán)其中某些格子是障礙物用‘X’表示不能放置車(chē)。求最多能放置多少個(gè)車(chē)使得它們互不攻擊。或者求在放置N個(gè)車(chē)的前提下有多少種方案障礙物格不能放。解題策略狀態(tài)表示除了used_cols我們還需要一個(gè)棋盤(pán)信息board。剪枝調(diào)整在遍歷第row行的列時(shí)除了檢查列是否被占用還要檢查board[row][col]是否是障礙物。求最大放置數(shù)這就不是簡(jiǎn)單的排列問(wèn)題了變成了一個(gè)搜索優(yōu)化問(wèn)題。我們可以用回溯法嘗試所有可能的放置組合小于等于N個(gè)車(chē)并記錄最大車(chē)數(shù)。這需要更精巧的剪枝比如按行或列的空閑格子數(shù)排序優(yōu)先搜索可能性少的分支。5.3 變體三廣義的“車(chē)”與二分圖匹配如果我們把問(wèn)題抽象棋盤(pán)的行和列可以看作二分圖的兩部分頂點(diǎn)。如果一個(gè)格子可以放車(chē)就在對(duì)應(yīng)的行頂點(diǎn)和列頂點(diǎn)之間連一條邊。那么“放置互不攻擊的車(chē)”就等價(jià)于在這個(gè)二分圖上找一個(gè)匹配并且如果要求放N個(gè)車(chē)就是找一個(gè)最大匹配且匹配數(shù)等于N。對(duì)于標(biāo)準(zhǔn)的、沒(méi)有障礙的N車(chē)問(wèn)題它是一個(gè)完美匹配問(wèn)題方案數(shù)是N!。對(duì)于有障礙的棋盤(pán)問(wèn)題轉(zhuǎn)化為求二分圖的最大匹配數(shù)或所有最大匹配的方案數(shù)。這時(shí)可以用匈牙利算法Hungarian Algorithm來(lái)高效求解最大匹配但求所有方案數(shù)仍然需要回溯或更高級(jí)的算法如利用行列式。在藍(lán)橋杯的提高組題目中可能會(huì)引入二分圖匹配的概念。如果你掌握了回溯法再學(xué)習(xí)匈牙利算法就能解決更廣泛的一類(lèi)問(wèn)題。5.4 輸入輸出格式與注意事項(xiàng)藍(lán)橋杯的OJ系統(tǒng)對(duì)輸入輸出格式要求嚴(yán)格。對(duì)于“ALGO-969”你需要仔細(xì)閱讀題目描述確認(rèn)是求方案數(shù)還是輸出具體方案。如果是具體方案輸出格式是什么例如每行一個(gè)數(shù)字表示列號(hào)還是輸出一個(gè)棋盤(pán)矩陣。處理輸入通常就是一個(gè)整數(shù)N。用int(input().strip())讀取。設(shè)計(jì)輸出嚴(yán)格按照題目要求。如果輸出數(shù)字注意是否要換行。如果輸出多種方案注意方案之間的分隔符。性能考慮如果N可能達(dá)到10或以上使用位運(yùn)算優(yōu)化版本。Python的遞歸深度默認(rèn)有限約1000層對(duì)于N10沒(méi)問(wèn)題但如果N很大或遞歸樹(shù)很深可能需要設(shè)置sys.setrecursionlimit(1000000)。6. 調(diào)試技巧與常見(jiàn)錯(cuò)誤排查在編寫(xiě)和調(diào)試回溯代碼時(shí)以下幾個(gè)坑我?guī)缀趺看味家?jiàn)同學(xué)們踩6.1 錯(cuò)誤一狀態(tài)恢復(fù)失敗這是回溯法最經(jīng)典的錯(cuò)誤。在遞歸調(diào)用返回后忘記恢復(fù)used_cols[col]、path.pop()等操作。導(dǎo)致?tīng)顟B(tài)污染后續(xù)搜索出錯(cuò)。務(wù)必牢記“做出選擇”和“撤銷(xiāo)選擇”必須成對(duì)出現(xiàn)像括號(hào)一樣對(duì)稱(chēng)。# 錯(cuò)誤示例 used_cols[col] True path.append(col) backtrack(...) # 忘記了 used_cols[col] False 和 path.pop()6.2 錯(cuò)誤二結(jié)果列表保存了引用而非副本如前所述result.append(path)會(huì)導(dǎo)致災(zāi)難性的后果。所有存入result的path實(shí)際上都是同一個(gè)列表對(duì)象最終result里的所有解都是一樣的最后回溯完成時(shí)的空列表或最終狀態(tài)。必須使用result.append(path[:])或result.append(path.copy())。6.3 錯(cuò)誤三遞歸終止條件錯(cuò)誤終止條件應(yīng)該是row n表示所有行都成功放置了車(chē)。有人會(huì)寫(xiě)成row n-1然后在row n-1的那一層遞歸里放置最后一個(gè)車(chē)并加入結(jié)果。這雖然也能工作但代碼邏輯不清晰容易在path的記錄上出錯(cuò)。統(tǒng)一使用row n作為終止條件更安全。6.4 錯(cuò)誤四剪枝條件遺漏或錯(cuò)誤對(duì)于N皇后忘記檢查斜線(xiàn)條件。或者檢查斜線(xiàn)時(shí)索引計(jì)算錯(cuò)誤比如row-col沒(méi)有加偏移導(dǎo)致負(fù)數(shù)索引。建議在寫(xiě)完后用一個(gè)小例子如N4手動(dòng)模擬或打印中間狀態(tài)驗(yàn)證剪枝邏輯是否正確。6.5 調(diào)試方法打印調(diào)試法在遞歸函數(shù)的開(kāi)頭打印當(dāng)前row,col,used_cols,path等信息。觀(guān)察搜索過(guò)程是否符合預(yù)期。小數(shù)據(jù)測(cè)試永遠(yuǎn)先用N1, 2, 3這樣的小數(shù)據(jù)測(cè)試。N1有1種解N2有2種解車(chē)放在(0,0)(1,1)和(0,1)(1,0)N3有6種解3!。用手算驗(yàn)證輸出。與已知結(jié)果對(duì)比N皇后的解的數(shù)量是已知的序列OEIS A000170。例如N1-1, N2-0, N3-0, N4-2, N5-10, N6-4, N7-40, N8-92。如果你的程序結(jié)果不對(duì)可以對(duì)照檢查。7. 舉一反三回溯算法的應(yīng)用擴(kuò)展掌握了N車(chē)/N皇后的回溯框架你就擁有了一把解決許多組合搜索問(wèn)題的鑰匙。以下是一些可以直接套用或稍加修改就能解決的藍(lán)橋杯常見(jiàn)題型全排列問(wèn)題給定一個(gè)不含重復(fù)數(shù)字的數(shù)組返回其所有可能的全排列。這幾乎就是N車(chē)問(wèn)題的翻版——N個(gè)數(shù)字放到N個(gè)位置上每個(gè)數(shù)字只能用一次。狀態(tài)記錄從“占用列”變成“占用數(shù)字”。組合總和問(wèn)題給定一個(gè)候選數(shù)組和一個(gè)目標(biāo)數(shù)找出所有和為目標(biāo)的組合數(shù)字可重復(fù)使用。這時(shí)搜索樹(shù)不再是排列樹(shù)而是組合樹(shù)。遞歸函數(shù)需要多一個(gè)參數(shù)current_sum并且為了去重需要控制搜索起點(diǎn)通常傳入一個(gè)start_index。子集問(wèn)題求一個(gè)集合的所有子集。每個(gè)元素有“選”或“不選”兩種狀態(tài)構(gòu)成一棵二叉樹(shù)。遞歸函數(shù)需要處理當(dāng)前元素選或不選兩種分支。數(shù)獨(dú)求解9x9的棋盤(pán)約束條件更復(fù)雜行、列、3x3宮格。但核心回溯框架不變遍歷每個(gè)空位嘗試填入1-9檢查是否符合三條規(guī)則遞歸回溯。檢查規(guī)則可以用類(lèi)似used_rows[9][10],used_cols[9][10],used_boxes[3][3][10]的數(shù)組來(lái)O(1)完成。圖的m著色問(wèn)題給定一個(gè)無(wú)向圖和m種顏色判斷是否可以用這些顏色給圖的頂點(diǎn)著色使得相鄰頂點(diǎn)顏色不同。從第一個(gè)頂點(diǎn)開(kāi)始嘗試每種顏色檢查與已著色鄰居是否沖突遞歸處理下一個(gè)頂點(diǎn)。核心思想都是一致的定義遞歸函數(shù)參數(shù)包含“當(dāng)前處理到哪個(gè)狀態(tài)”如第幾行、第幾個(gè)數(shù)字、第幾個(gè)頂點(diǎn)。在每一層枚舉所有可能的選擇。對(duì)于每個(gè)選擇先判斷是否滿(mǎn)足約束剪枝如果滿(mǎn)足則“做出選擇”更新?tīng)顟B(tài)遞歸進(jìn)入下一層然后“撤銷(xiāo)選擇”恢復(fù)狀態(tài)。通過(guò)“ALGO-969 N車(chē)”這道題我希望你收獲的不僅僅是一個(gè)問(wèn)題的答案而是這套分析和解決回溯類(lèi)問(wèn)題的通用方法論。從理解問(wèn)題、建立模型、設(shè)計(jì)狀態(tài)、編寫(xiě)遞歸框架到優(yōu)化剪枝、調(diào)試驗(yàn)證最后舉一反三。這才是算法訓(xùn)練的真正目的。在藍(lán)橋杯乃至更廣闊的編程世界里這種將復(fù)雜問(wèn)題分解并系統(tǒng)化解決的能力遠(yuǎn)比記憶幾個(gè)算法模板要重要得多。下次再遇到“ALGO-xxx”的題目不妨先靜下心來(lái)畫(huà)一畫(huà)搜索樹(shù)想一想狀態(tài)如何表示剪枝條件是什么你會(huì)發(fā)現(xiàn)很多難題都似曾相識(shí)。