八皇后问题的两种解决方法

拼搏现实的明天。 2022-08-05 08:22 137阅读 0赞

最近看到递归，原本利用回溯思想解决的经典八皇后问题，其实也是可以用递归解决的~

八皇后的递归解决思路：

从第一行开始，依次判断0~8列的哪一列可以放置Queen，这样就确定了该行的Queen的位置，然后行数递增，继而递归实现下一行的判断，依次类推直到行数增加到8（行数从0开始的），此时为递归-----归的条件，即表示一种八皇后的解决方法完成，打印结果；之后进行下一种解决方法的寻找，大致思路个人理解是这样

noDanger(row,j,(\*chess)\[8\])函数是判断第row行第j列是否可以放置Queen

#include <stdio.h>
    
    int count=0;
    int noDanger(int row,int j,int (*chess)[8])
    {
        int flag1=0,flag2=0,flag3=0,flag4=0,flag5=0;
        int i,k;
        //判断列
        for(i=0;i<8;i++)
        {
            if(*(*(chess+i)+j)!=0)
            {
                flag1=1;
                break;
            }
        }
        //判断左上方
        for(i=row,k=j;i>=0&&k>=0;i--,k--)
        {
            if(*(*(chess+i)+k)!=0)
            {
                flag2=1;
                break;
            }
        }
        //判断右下方
        for(i=row,k=j;i<8&&k<8;i++,k++)
        {
            if(*(*(chess+i)+k)!=0)
            {
                flag3=1;
                break;
            }
        }
        //判断左下方
        for(i=row,k=j;i<8&&k>=0;k--,i++)
        {
            if(*(*(chess+i)+k)!=0)
            {
                flag4=1;
                break;
            }
        }
        //判断右上方
        for(i=row,k=j;i>=0&&k<8;k++,i--)
        {
            if(*(*(chess+i)+k)!=0)
            {
                flag5=1;
                break;
            }
        }
        if(flag1||flag2||flag3||flag4||flag5)
        {
            return 0;
        }else
        {
            return 1;
        }
    }
    //参数row表示起始行  参数n表示列数   参数(*chess)[8]表示指向每一行的指针
    void eightQueen(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(row==8)
        {
            printf("这是第 %d 种情况:\n",count+1);
            for(i=0;i<8;i++)
            {
                for(j=0;j<8;j++)
                {
                    printf("%d ",*(*(chess2+i)+j));
                }
                printf("\n");
            }
            printf("\n");
            count++;
        }else
        {
            //依次判断每一列
            for(j=0;j<n;j++)
            {
                if(noDanger(row,j,chess2))//判断该位置是否危险，也就是判断是否可以放置Queen
                {
                    for(i=0;i<8;i++)
                    {
                        *(*(chess2+row)+i)=0;//将第row行置为0
                    }
                    *(*(chess2+row)+j)=1;//可以放置皇后，则置1
                    eightQueen(row+1,n,chess2);
                }
            }
        }
    }
    int main()
    {
        int chess[8][8];
        int i,j;
        for(i=0;i<8;i++)
        {
            for(j=0;j<8;j++)
            {
                chess[i][j]=0;
            }
        }
        eightQueen(0,8,chess);
        printf("总共有 %d 种解决方法!\n\n",count);
        return 0;
    }