关于回溯法求解八皇后有关问题

关于回溯法求解八皇后问题
本人刚学习数据结构，遇到回溯法解决八皇后问题。自己想写代码演练下，可是怎么都得不出答案！不知道错在哪里？希望大家给看看，指出错误之处!

#include<stdio.h>
#include<math.h>
#define N 8
/* 采用回溯法解决八皇后问题 */

int Queen[N][N];
int count=0;  //记录方法个数

void init()
{//初始化Queen数组为0；
for(int i=0;i<N; ++i)
for(int j=0; j<N; ++j)
Queen[i][j]=0;
}

int is_conflict(int a,int b)
{
//判断在Queen[a][b]放第a+1个皇后和前a个皇后是否冲突
int flag=0;
for(int i=0; i<a; ++i)
{
if(Queen[i][b]==1)  //如果和Queen[a][b]同列 则判断冲突
{
flag=1;
return flag;
}
else
for(int j=0; j<N; ++j)
{
if((Queen[i][j]==1) && (abs(a-i)==abs(b-j)))   //如果在同一条对角线上则判断冲突
flag=1;
}
}
return flag;
}

void queen(int a)
{
if(a>N-1)  //如果超出N行则已经得出一个解，记录数加一并打印出方案
{
count++;
for(int i=0; i<N; ++i)
{
for(int j=0; j<N; ++j)
{
printf("%d",Queen[i][j]);
}
printf("\n");
}
return ;
}
for(int j=0; j<N; ++j)
{
if(a==0 || !is_conflict(a,j))  //如果不冲突则往下行递归
{
Queen[a][j]=1;
queen(a+1);
}
}
}

int main()
{
init();
queen(0);
printf("一共有%d种方法\n",count);
return 0;
}

数据结构 C? C++? 回溯算法 八皇后问题
[解决办法]
if(a==0 
[解决办法]
 !is_conflict(a,j))
{            
  Queen[a][j]=1;             
  queen(a+1);    
  Queen[a][j]=0;  // 加上这一行就好了
}     

查看更多 下一篇