目录
题目：
n皇后解题代码：
代码思维：
题目：
N 皇后问题源自国际象棋，所有棋子中权力最大的称为皇后，它可以直着走、横着走、斜着走（沿 45 度角），可以攻击移动途中遇到的任何棋子。N 皇后问题的具体内容是：如何将 N 个皇后摆放在 N*N 的棋盘中，使它们无法相互攻击。
举个简单的例子，将 4 个皇后摆放在 4*4 的棋盘中，下图给出了一种摆放方式，各个皇后无论是直着走、横着走还是斜着走，都无法相互攻击。
该问题用回溯法解决
n皇后解题代码：
#include <iostream>
#include <cmath>
using namespace std;
int N,res=0;
int queen(int *arr,int r){
if(r==N)
res++;
else{
for(int c=0;c<N;c++){
arr[r]=c;
bool can=true;//用于标记是否可以放皇后
for(int c1=0;c1<r;c1++){ //不在同一行
if(arr[r]==arr[c1]|| //同一列的情况
abs(r-c1)==abs(arr[r]-arr[c1])){ //同一对角线的情况
can=false;
break;
}
}
if(can)
queen(arr,r+1);
}
}
return res;
}
int main(){
cin>>N;
int arr[N];
cout<<queen(arr,0);
return 0;
}代码思维：
这种问题和全排列问题代码对比后可以发现回溯算法的中心思维为：
对于某个问题的求解，先将当前的选择作为解的一部分，基于当前的解法继续求解，当试探到某一步时，发现原先的选择并不能达到目标，则退回去修改原来的选择。
全排列代码：
#include <iostream>
using namespace std;
int n;
int num[20];
bool chosen[20];
void calc(int k){
if(k==n+1){
//达到条件输出
for(int i=1;i<=n;i++){
cout<<num[i]<<" ";
}
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
//做选择
if(chosen[i]==1){
continue;
}
num[k]=i;
chosen[i]=1;
calc(k+1);
chosen[i]=0;
num[k]=0;
}
}
int main()
{
cin>>n;
calc(1);
return 0;
}
发布者：admin，转转请注明出处：http://www.yc00.com/web/1754941061a5218151.html
评论列表（0条）