回溯算法從空解開始，并逐步擴(kuò)展該解。搜索遞歸地通過各種不同的構(gòu)造解決方案的路徑。

例如，考慮計算n皇后問題：在n*n的棋盤上放置彼此不受攻擊的n個皇后。

（皇后可以攻擊在同一行、同一列、同一斜線上的棋子）

按以上規(guī)則：同一行或同一列或同一斜線上只能有一個皇后，同一行或同一列上必須有一個皇后。

n皇后問題的解空間是一棵n叉樹，樹的深度為n。

當(dāng)n為4時，有兩種可能的解決方案：

八皇后問題對于每一行是否可以放置皇后，可用一個規(guī)模為8的循環(huán)去判斷。每一行的判斷操作相同，如果操作完成了8行（放置了8個皇后），便求出了一個解。所以該問題可以用遞歸去做。如果某一行全部位置無法放置皇后時，沒必要繼續(xù)深入，可以回溯到上一步，也就是使用回溯法。對于非尾遞歸，遞歸函數(shù)回退時，遞歸點后面的代碼就是遞歸函數(shù)回退后執(zhí)行的部分。對于八皇后問題，上述的循環(huán)可以判斷某行下一列是否可以放置皇后，而上一列放置皇后的操作進(jìn)行逆操作后便完成了回溯（遞歸有天然的回退階段）。

八皇后問題的暴力枚舉搜索或遞歸解法會形成一個棵8叉完全樹，回溯解法可以通過約束條件避免一些搜索繼續(xù)深入，形成一棵8叉不完全樹。

為簡便起見，我們可以用四皇后問題去理解，然后泛化到一般的情況。

在底層，前三種配置是非法的，因為皇后們互相攻擊。然而，第四種配置是有效的，可以通過在棋盤上再放置兩個皇后來擴(kuò)展到完整的解決方案。只有一種方法可以放置剩下的兩個皇后。

如下面左圖所示：

從y=0,x=0開始，search(0)遞歸調(diào)用search(1)（x=2,y=1），遞歸調(diào)用search(2)

當(dāng)y=2，x=3時，遞歸函數(shù)search(2)執(zhí)行完畢，回退到search(1)，x=0，逆操作，循環(huán)到x=3……

code demo:

#include #define n 4int column[n*2] = {0};int diag1[n*2] = {0};int diag2[n*2] = {0};int count = 0;void search(int y) { if (y == n) { count++; return; } for (int x = 0; x < n; x++) { if (column[x] || diag1[x+y] || diag2[x-y+n-1]) continue; column[x] = diag1[x+y] = diag2[x-y+n-1] = 1; search(y+1); column[x] = diag1[x+y] = diag2[x-y+n-1] = 0; // 回退時的逆操作，下一輪循環(huán)x++ } return;}main(){ search(0); printf("%d",count); getchar();}/*n=4, 2n=8, 92n=16, 14772512*/

搜索從調(diào)用search(0)開始。棋盤的大小為n*n，代碼計算要計數(shù)的解決方案數(shù)。

代碼假設(shè)棋盤的行和列編號從0到n-1。當(dāng)使用參數(shù)y調(diào)用函數(shù)搜索時，它會在行y上放置皇后，然后使用參數(shù)y-1調(diào)用自身。然后，如果y=n，則已找到解決方案，變量count增加1。

數(shù)組column跟蹤包含皇后的列，數(shù)組diag1和diag2跟蹤對角線。不允許在已包含皇后的列或?qū)蔷€中添加其他皇后。例如，4*4棋盤編號如下，當(dāng)x、y取不同的值時，對應(yīng)列方向column[x]、”/”方向上diag1[x+y]、””方向上diag2[x-y+4-1]的取值為0時表示無皇后：

y 2，x=3

回溯。

y 1，x=3

……

count=1。

回溯到下面綠色點：

繼續(xù)逐步回溯：

……

count=2。

繼續(xù)逐步回溯，最后count=2。

可視化操作的網(wǎng)頁地址：

https://pythontutor.com/render.html#mode=display

-End-