c语言二维数组回溯法疑问
八皇后问题 我是想设置一个a[8[8]数组，在第一列第一行中先填入数字1，然后再从第二列第一行中开始填数字一，若冲突则从第二行填写 …… 直到回溯并填写完毕 则输出每次填写好的数组
#include <stdio.h >
int iCount = 0;//记录解的序号的全局变量
int Queens[8][8]={0};//记录皇后在各列上的放置位置的全局数组
int tot=0;
void Queen(int n)//在第n列放置皇后
{
int i,j,ok,k;
if (n ==8)//若8个皇后已放置完成
{++tot;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{printf("%2d",Queens[i][j]);
if(j==7)
printf("\n");}}
else
for (i =0; i < 8; i++)//在第n列的各个行上依次试探
{ ok=1;
Queens[i][n] = 1;//在n列的第i行上放置皇后。
for(j=0;j<n;j++) //查找前n-1列
for(k=0;k<8;k++) //查找前n-1列中所有单元格是否放皇后
if (Queens[i][k]==1||abs(i-k)==abs(j-n)&&Queens[j][k]==1)//两个皇后在同一对角线上和在同一 行上
{Queens[i][n] = 0;
break;}
if (Queens[i][n])//没有冲突，就开始下一列的试探
Queen(n + 1); //递归调用进行下一步
}
}
int main()
{
printf("八皇后排列方案:\n");
Queen(0);//从第0列开始递归试探
getch();
return 0;
}
我知道 for(j=0;j<n;j++) //查找前n-1列
for(k=0;k<8;k++) //查找前n-1列中所有单元格是否放皇后
if (Queens[i][k]==1||abs(i-k)==abs(j-n)&&Queens[j][k]==1)//两个皇后在同一对角线上和在同一 行上
{Queens[i][n] = 0;
break;}
这一段有问题 但不知道如何修改了
[解决办法]
你这几段有几个问题，1：for(j=0;j<n;j++) 这里并非只是检查前n-1列， 要检查该行所有列。2：没有回溯条件，不能求出所有解，更何况你这无解。
[解决办法]
我给你看一下我的，和你思路一样的。
#include<stdio.h>
#define Queen 8
int Sign(int p[][Queen],int a,int b)
{
for(int i=0;i<Queen;i++)
{
if(p[a][i]||p[i][b])
return 0;
if((i+b-a<Queen)&&(i+b-a>=0))
if(p[i][i-a+b])
return 0;
if((a+b-i<Queen)&&(a+b-i>=0))
if(p[i][a+b-i])
return 0;
}
return 1;
}
void Print(int p[][Queen],int *pathcount)
{
printf("第%d种方案\n",++(*pathcount));
for(int i=0;i<Queen;i++)
{
for(int j=0;j<Queen;j++)
p[i][j]?printf("■"):printf("□");
printf("\n");
}
}
void Back(int p[][Queen],int i,int j,int *count)
{
p[i][j]=0;
(*count)--;
}
void SetQueen(int p[][Queen],int i,int *count,int *pathcount)
{
for(int j=0;j<Queen;j++)
{
if(Sign(p,i,j))
{
p[i][j]=1;
(*count)++;
if(*count==Queen)
{
Print(p,pathcount);
}
else
{
SetQueen(p,i+1,count,pathcount);
}
Back(p,i,j,count); //求出一组解或遇到障碍时回溯
}
}
}
void main()
{
int p[Queen][Queen]={0};
int count=0,k=0,pathcount=0;
SetQueen(p,k,&count,&pathcount);
}
