（一）八皇后問題
（1）回溯

#include <iostream> #include <string>#define MAXN 100using namespace std;int tot = 0, n = 8; int C[MAXN];void search(int cur) {if(cur == n) ++tot; //遞歸邊界，僅僅要走到了這里。全部皇后必定不沖突else for(int i = 0; i < n; ++i) {int ok = 1;C[cur] = i; //嘗試把第cur行的皇后放在第i列for(int j = 0; j < cur; ++j) { //檢查是否和前面的皇后沖突if(C[cur] == C[j] || cur-C[cur] == j-C[j] || cur+C[cur] == j+C[j]) {ok = 0;break;}}if(ok) search(cur+1); //假設合法，則繼續遞歸} }int main() {search(0);cout << tot << endl;return 0; }

（2）利用二維數組優化的回溯法

#include <iostream> #include <string>#define MAXN 100using namespace std;int tot = 0, n = 8; int vis[3][MAXN], C[MAXN]; void search(int cur) {if(cur == n) ++tot;else for(int i = 0; i < n; ++i) {if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n]) { //利用二維數組直接推斷C[cur] = i;vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1; //改動全局變量search(cur+1);vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0; //這里一定要改回來！}} }int main() {memset(vis, 0, sizeof(vis));search(0);cout << tot << endl;return 0; }

在上面的程序中，vis數組表示已經放置的皇后占領了哪些列、主對角線和副對角線。

一般的在回溯法中，假設改動了全局變量vis數組，那么遞歸調用結束后一定要改動回來！由于在解答樹中，假設下一層不滿足條件，那么就須要回溯。那么就要把改動過的vis給改回來，那樣，才干繼續進行下一次的推斷！！！

（二）素數環

題目：輸入正整數n，把整數1。2，3，...，n組成一個環。使得相鄰兩個整數之和均為素數。

輸出時從整數1開始逆時針排列。

同一個環應該恰好輸出一次。

典型的回溯法，代碼例如以下：

#include <iostream> #include <algorithm> using namespace std;const int MAXN = 1000; int isp[MAXN], vis[MAXN], A[MAXN], n;int is_prime(int x) { //推斷一個數是否為素數for(int i = 2; i*i <= x; ++i) {if(x % i == 0) return 0;}return 1; }void dfs(int cur) {if(cur == n && isp[A[0] + A[n-1]]) {for(int i = 0; i < n; ++i) cout << A[i] << " ";cout << endl;}else {for(int i = 2; i <= n; ++i) {if(!vis[i] && isp[i + A[cur-1]]) {A[cur] = i; //數字i滿足條件，所以第cur個位置能夠放數字ivis[i] = 1;dfs(cur+1);vis[i] = 0; //跟上題一樣。一定不能忘記把vis的值改回來，原因見上一題的代碼凝視}}} }int main() {memset(vis, 0, sizeof(vis)); //遞歸調用之前，一定要把vis函數清0cin >> n;for(int i = 2; i <= 2*n; ++i) isp[i] = is_prime(i); //推斷一個數不是質數。為了方便后推斷A[0] = 1; //從標題中的規定的第一個數字1開始dfs(1); //所以遞歸調用位置的1開始，而不是從位置0開始，因為數字第一位置已被確定是1return 0; }

總結

以上是生活随笔為你收集整理的ACM：回溯，八皇后问题，素数环的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。