八皇后问题
本帖最后由 luckin 于 2014-6-25 19:41 编辑#include<stdio.h>
int count = 0;
int notdanger(int row,int j,int (*chess2))
{
int i,k,flag=0,flag1=0,flag2=0,flag3=0,flag4=0;
//列方向
for(i=0;i<8;i++)
{
if(*(*(chess2+i)+j))
{
flag=1;
break;
}
}
//左上方向
for(i=row,k=j;i>=0&&k>=0;i--,k--)
{
if(*(*(chess2+i)+k))
{
flag1=1;
break;
}
}
//右下方向
for(i=row,k=j;i<8&&k<8;i++,k++)
{
if(*(*(chess2+i)+k))
{
flag2=1;
break;
}
}
//左下方向
for(i=row,k=j;i>=0&&k<8;i--,k++)
{
if(*(*(chess2+i)+k))
{
flag3=1;
break;
}
}
//右上方向
for(i=row,k=j;i<8&&k>=0;i++,k--)
{
if(*(*(chess2+i)+k))
{
flag4=1;
break;
}
}
if(flag||flag1||flag2||flag3||flag4)
return 0;
else
return 1;
}
//row表示起始行，n表示列数，最后一个参数表示指向棋盘每一行的指针。
void EightQueen(static int row,int n,int (*chess))
{
int chess2;
int i,j;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
chess2=chess;
if(8==row)
{
printf("第%d种方法为\n",count+1);
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
printf("%d ",chess2);
}
printf("\n");
}
count++;
printf("\n");
}
else
{
for(j=0;j<n;j++)
{
if(notdanger(row,j,chess2))
{
for( i=0; i < 8; i++ )
{
*(*(chess2+row)+i) = 0;
}
*(*(chess2+row)+j)=1;
EightQueen(row+1,n,chess2);
}
}
}
}
int main()
{
int chess={0};
EightQueen(0,8,chess);
printf("*****all is %d ways!*****\n",count);
return 0;
}87行至90行 为什么添加这部分？不是初始化的时候所有元素已经是0了。
**********欢迎各位大神*********
本帖最后由 santaclaus 于 2014-6-25 21:49 编辑
for(j=0;j<n;j++)
{
if(notdanger(row,j,chess2))
{
//八皇后放置问题并不是只考虑当前位置能不能放1，即便当前位置可放，还要考虑当下一行
//都不能放1时，该怎么办？为了解决这问题时，它采取一种“试放”的策略。即，先在当前位
//置“试放"一个1，一旦出现下一行都不能放置时，就必须立即取消当前位置的这个1。不然
//这个1会被保存下来。具体见以下分析：
//红色部分的代码是将当前行清零，保证该行最多只能放一个1。如果不清零操作的话，
// 由于蓝色那行代码是在当前行的第j列置1的。如果出现下一行无论怎么放都是冲突的，
//此时，当前位置的这个1就必须立即清理掉。不然，会随着j列从0到n的变化，该行1的
//数量会越放越多，从而形成不了八皇后。
//其实这问题还有更好的解决方法，见我的贴子《回溯法求解八皇后问题的C语言实现》
for( i=0; i < 8; i++ )
{
*(*(chess2+row)+i) = 0;
}
*(*(chess2+row)+j)=1;
EightQueen(row+1,n,chess2);
}
}
本帖最后由 luckin 于 2014-6-25 21:56 编辑
santaclaus 发表于 2014-6-25 20:35 static/image/common/back.gif
for(j=0;j
厉害！我调试的时候的row的值一直跳来跳去也是这个原因(回溯？)? santaclaus 发表于 2014-6-25 19:40
for(j=0;j
欢迎来交流http://bbs.fishc.com/group-264-1.html 顶一下
页:
[1]