八皇后问题

luckin

#include<stdio.h>

int count = 0;

int notdanger(int row,int j,int (*chess2)[8])
{
        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)[8])
{
        int chess2[8][8];
        int i,j;
        for(i=0;i<8;i++)
                for(j=0;j<8;j++)
                        chess2[i][j]=chess[i][j];

                if(8==row)
                {
                        printf("第%d种方法为\n",count+1);
                        for(i=0;i<8;i++)
                        {
                                for(j=0;j<8;j++)
                                {
                                        printf("%d ",chess2[i][j]);
                                }
                                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[8][8]={0};
        EightQueen(0,8,chess);
        printf("*****all is %d ways!*****\n",count);
        return 0;
}

87行至90行 为什么添加这部分？不是初始化的时候所有元素已经是0了。
**********欢迎各位大神*********

santaclaus

                      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

santaclaus 发表于 2014-6-25 20:35

                               
登录/注册后可看大图

for(j=0;j

厉害！我调试的时候的row的值一直跳来跳去也是这个原因(回溯？)?

拈花小仙

santaclaus 发表于 2014-6-25 19:40
for(j=0;j

欢迎来交流http://bbs.fishc.com/group-264-1.html

繁空.星雨

顶一下