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

野性酷女 2022-05-21 03:18 165阅读 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;
    }