回溯算法的本质是深度优先搜索,回溯又叫试探法(backtracking),深度优先遇到障碍再返回来。
回溯法要先定义一个解空间,用便于搜索的方式整理解空间,然后深度优先搜索。
八皇后问题:
解空间?
八个皇后在棋盘上面的排列位置可以用一个8元数组表示,
X1,X2,X3,X4,X5,X6,X7,X8代表第i行皇后所在的列
约束条件是
x[i]!=x[j]&&x[i]-x[j]!=i-j这样就只有8!个解空间了
回溯算法解决的N皇后
#include <iostream>
using namespace std;
const int maxn=10005;
int place[maxn];
int cnt;
int N;
int abs(int a){if(a<0) return -a;return a;
}
bool check(int placex,int curi){for(int i=1;i<curi;i++){if(place[i]==placex || abs(curi-i)==abs(place[i]-placex)){return false;}}return true;
}
//curi 代表当前x的下标
void dfs(int curi){for(int i=1;i<=N;i++){if(check(i,curi)){//i能不能填到place[curi]里面去if(curi==N) cnt++;else{place[curi]=i;dfs(curi+1);}}}
}int main(int argc, char const *argv[])
{cin>>N;dfs(1);cout<<cnt<<endl;/* code */return 0;
}打印八皇后
</pre><pre name="code" class="cpp">void print(){for(int i=1;i<=N;i++){for(int j=1;j<place[i];j++)cout<<"0 ";cout<<1<<" ";for(int j=place[i]+1;j<=N;j++) cout<<"0 ";cout<<endl;}cout<<endl;
}