当前位置: 代码迷 >> 综合 >> 回溯算法-8皇后
  详细解决方案

回溯算法-8皇后

热度:83   发布时间:2024-01-18 23:42:32.0

回溯算法的本质是深度优先搜索,回溯又叫试探法(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;
}


  相关解决方案