您现在的位置:首页 > >

回溯法-八皇后问题

发布时间:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define M 8
int col[M+1]; //col[m]=n表示第m列,第n行放置皇后
int a[M+1]; //a[k]=1表示第k行没有皇后
int b[2*M+1]; //b[k]=1表示第k条主对角线上没有皇后
int c[2*M+1]; //c[k]=1表示第k条次对角线上没有皇后
int queen(int N)
{ //初始化N+1个元素,第一个元素不使用
int solution = 0; //解的组数
int j,m=1,good=1;
char awn;
for(j=0;j<=N;j++)
{a[j]=1;}
for(j=0;j<=2*N;j++)
{b[j]=c[j]=1;}
col[1]=1;col[0]=0;
do
{
if(good)
{
if(m==N) //已经找到一个解
{
solution++;
// printf("列\t\t行\n");
cout<<"第 "<<solution<<" 组解的坐标:\n";
for(j=1;j<=N;j++)
{
//printf("%d\t\t%d\n",j,col[j]);
cout<<"("<<j<<" , "<<col[j]<<")"<<" ";
}
cout<<endl;
//printf("Enter a character(Q/q for exit)!\n");
// scanf("%c",&awn);
// if(awn=='Q'||awn=='q')
// exit(0);
while(col[m]==N) //如果本列试探完毕,则回溯
{
m--; //回溯
a[col[m]]=b[m+col[m]]=c[N+m-col[m]]=1;//标记m列col[m]行处没有皇后(所在行,对角线,次对角线上都没有皇后)
}
col[m]++; //继续试探本列其他行
}
else //当前放置的皇后满足要求,但还没找到解,继续考察下一列
{
a[col[m]]=b[m+col[m]]=c[N+m-col[m]]=0; //标志当前位置已经放置皇后
col[++m]=1; //转到下一列第一行
}
}
else
{
while(col[m]==N) //已经到了列底,所以回溯到上一列
{
m--;
a[col[m]]=b[m+col[m]]=c[N+m-col[m]]=1;
}
col[m]++; //试探其它行
}
good=a[col[m]]&&b[m+col[m]]&&c[N+m-col[m]]; //检查是否满足要求
}while(m!=0);
return solution;
}
int main()
{
printf("solution: %d\n",queen(8));
return 0;

}


热文推荐
猜你喜欢
友情链接: 医学资料大全 农林牧渔 幼儿教育心得 小学教育 中学 高中 职业教育 成人教育 大学资料 求职职场 职场文档 总结汇报