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

例如，考慮計(jì)算n皇后問(wèn)題：在n*n的棋盤(pán)上放置彼此不受攻擊的n個(gè)皇后。

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

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

n皇后問(wèn)題的解空間是一棵n叉樹(shù)，樹(shù)的深度為n。

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

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

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

為簡(jiǎn)便起見(jiàn)，我們可以用四皇后問(wèn)題去理解，然后泛化到一般的情況。

在底層，前三種配置是非法的，因?yàn)榛屎髠兓ハ喙簟Ｈ欢?，第四種配置是有效的，可以通過(guò)在棋盤(pán)上再放置兩個(gè)皇后來(lái)擴(kuò)展到完整的解決方案。只有一種方法可以放置剩下的兩個(gè)皇后。

如下面左圖所示：

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

當(dāng)y=2，x=3時(shí)，遞歸函數(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; // 回退時(shí)的逆操作，下一輪循環(huán)x++ } return;}main(){ search(0); printf("%d",count); getchar();}/*n=4, 2n=8, 92n=16, 14772512*/

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

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

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

y 2，x=3

回溯。

y 1，x=3

……

count=1。

回溯到下面綠色點(diǎn)：

繼續(xù)逐步回溯：

……

count=2。

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

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

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

-End-