【数据结构算法】递归：八皇后问题-蒲公英云

【数据结构算法】递归：八皇后问题

野性酷女 2022-05-21 03:18 314阅读 0赞

八皇后

八皇后问题就是说如下图所示的国际象棋的棋盘中，放入8个皇后，所谓皇后就是国际象棋中的一个角色，它的功能就是能够打掉与它同一行同一列同一斜排的棋子，并且打击距离是整个棋盘。我们的任务就是在棋盘中挑选8个位置放上皇后，使得这八个皇后能够在棋盘中和平共处，不会被对方打掉。

解题思路

利用递归的手段解决，我们的主要思路是以行为单位遍历整个棋盘，每次遍历到一个位置判断一次当前位置是否危险（其同一行同一列两个斜线上是否有棋子）。若不危险则继续遍历下一行，当行==8的时候输出当前情况（也就是递归的终止条件）。若行！=8的时候那么就遍历下一行，也就是行加一，所以八皇后问题可以用递归来解决。

代码

#include <stdio.h>
int count = 0;//全局变量
int notdanger(int row,int j,int (*chess)[8])
{
    int i, flag1 =0, flag2 =0;
    //判断列方向
    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<0 && k>=0;i++,k--)
    {
        if(*(*(chess+i)+k) != 0)
        {
            flag3 = 1;
            break;
        }
    }
    //判断右上方
    for(i = row,k=j;i>=0 && k<0;i--,k++)
    {
        if(*(*(chess+i)+k) != 0)
        {
            flag4 = 1;
            break;
        }
    }
    //判断右下方
    for(i = row,k=j;i<0 && k<0;i++,k++)
    {
        if(*(*(chess+i)+k) != 0)
        {
            flag5 = 1;
            break;
        }
    }
    if(flag1 || flag2 || flag3 || flag4 || flag5)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
//row表示起始行
//n表示列数
//（*chess）[8]:表示指向棋盘每一行的指针
void EightQueue(int row, int n, int (*chess)[8])
{
    int chess2[8][8], i, j;//用来存放递归过程中的棋盘
    //将棋盘赋值给中间矩阵
    for(i = 0;i<8;i++)
    {
        for(j = 0;j<8;j++)
        {
            chess2[i][j] = chess[i][j];
        }
    }
    if (8 == row)
    {
        //输出当前这个矩阵
        for(i=0;i<8;i++)
        {
            for(j=0;j<8;j++)
            {
                //*(*(chess2+i)+j)利用指针操纵二维数组的一种方式
                printf("%d ",*(*(chess2+i)+j));
            }
            //每个矩阵的行与行之间空出一格来
            printf("\n");
        }
        //每一个可行方案之间空出一格来
        printf("\n");
    }
    //如果递归过程中没有满足终止条件
    else
    {
        //对于每一行（当前行数为n）来说，一共有八个位置，我需要判断每个位置是否危险，一旦确定当前位置不危险，就要将当前行的这一列的这个值赋值为1，并且进入下一行，执行一样的操作（这就是递归的精髓）。
        for(j = 0;j<n;i++)
        {
            if(notdanger(row,j,chees))
            {
                //将当前row行，j列这个值赋值为1
                for(i = 0;i<8;i++)
                {
                    *((*chess+i)+j) = 0;
                }
                *((*chess+row)+j) = 1;
                EightQueen(row+1,n,chess);
            }
        }
    }
}
int main()
{
    int chess[8][8],i,j;
    for(i = 0;i<8;i++)
    {
        for(j = 0;j<8;j++)
        {
            chess[i][j] = 0;
        }
    }
    EightQueen(8,8,chess);
    printf("总共有%d种解决方法\n",count);
    return 0;
}