八皇后問題

?

八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。

該問題是十九世紀著名的數(shù)學家高斯1850年提出：在8x8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后

都不能處于同一行、同一列或同一斜線上，問有多少種擺法？

#include <iostream> #include <string.h> #include <stdio.h>using namespace std;int S[8]; int cnt; bool a[8],b[15],c[15];void Print() {cnt++;printf("%2d: ",cnt);for(int i=0;i<8;i++)cout<<S[i]<<" ";cout<<endl; }void DFS(int i) {for(int j=0;j<8;j++){if(a[j] == 0 && b[i+j] == 0 && c[i-j+7] == 0){S[i] = j;a[j] = b[i+j] = c[i-j+7] = 1;if(i < 7) DFS(i+1);else Print();a[j] = b[i+j] = c[i-j+7] = 0;}} }void Init() {cnt = 0;memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c)); }int main() {Init();DFS(0);return 0; }

?

問題：給兩個正整數(shù)n和m，輸出n個1 ~ m的數(shù)字的所有組合。

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int N = 25;int ans[N];void dfs(int dept,int n,int m) {if(dept == n){for(int i=0;i<n;i++)cout<<ans[i]<<" ";cout<<endl;return;}for(int i=1;i<=m;i++){ans[dept] = i;dfs(dept+1,n,m);} }int main() {int n,m;while(cin>>n>>m)dfs(0,n,m);return 0; }

?

問題：給定一個正整數(shù)n，輸出n的所有排列。

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int N = 25;int ans[N]; bool used[N]; int n;void dfs(int dept) {if(dept == n){for(int i=0;i<n;i++)cout<<ans[i]<<" ";cout<<endl;return;}for(int i=1;i<=n;i++){if(used[i]) continue;used[i] = true;ans[dept] = i;dfs(dept+1);used[i] = false;} }int main() {while(cin>>n){memset(used,0,sizeof(used));dfs(0);}return 0; }

?

總結

以上是生活随笔為你收集整理的经典的回溯问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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