C语言-数据结构-递归求解实例-8皇后问题

骑猪看日落 2022-07-19 02:27 33阅读 0赞

**1. 目标**

运用递归对8皇后问题进行求解（也可以推广到n皇后问题），输出每种棋子放置的位置和解的总数。

**2. 运行示例**

以4皇后问题为例。

![SouthEast][]

**3. 源代码**

<span style="font-size:14px;">#include<stdio.h>
    #define title "------------------------------Life is a fight!------------------------------------"
    #define n 4     //n 个皇后
    
    int count=0;
    
    //在当前chess 棋盘下，对 row, col 位置进行检查，是否可以放棋子
    int select(int row, int col, int(*chess)[n])
    {
        int flag1=0, flag2=0, flag3=0, flag4=0, flag5=0;
        int i=0;
    
        for(i=0;i<n;i++)    //column
        {
            if(1==*(*(chess+i)+col))
            {
                flag1=1;
                break;
            }
        }
        for(i=0;i<row;i++)  //left upper
        {
            if(col+i-row>=0&&1==*(*(chess+i)+(col+i-row)))
            {
                flag2=1;
                break;
            }
        }
        for(i=row;i<n;i++)  //right lower
        {
            if(col+i-row<n&&1==*(*(chess+i)+(col+i-row)))
            {
                flag3=1;
                break;
            }
        }
        for(i=0;i<row;i++)  //right upper
        {
            if(col+row-i<n&&1==*(*(chess+i)+(col+row-i)))
            {
                flag4=1;
                break;
            }
        }
        for(i=row;i<n;i++)  //left lower
        {
            if(col+row-i>=0&&1==*(*(chess+i)+(col+row-i)))
            {
                flag5=1;
                break;
            }
        }
        if(flag1||flag2||flag3||flag4||flag5)
            return 1;
        else
            return 0;
    }
    
    
    //在chess棋盘下，对第row行进行递归
    void queen(int row, int (*chess)[n])
    {
        int tchess[n][n];
        int i, j;
    
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                tchess[i][j]=chess[i][j];
        if(n==row)//如果已经放置了n个棋子，则递归结束，打印出棋盘
        {
            printf("%d:\n",count+1);
            for(i=0;i<n;i++)
            {
                for(j=0;j<n;j++)
                {
                    printf("%d ", tchess[i][j]);
                }
                printf("\n");
            }
            printf("\n");
            count++;
        }
        else
        {
            for(j=0;j<n;j++)
            {
                if(!select(row, j, chess))//如果该位置安全
                {
                    for(i=0;i<n;i++)//该步骤很重要，如果在传入的棋盘中检查，该位置是安全的，那么将该行棋子全部置零，这是为了消除之前在该行放置的棋子
                        tchess[row][i]=0;
                    tchess[row][j]=1;
                    queen(row+1, tchess);//recursion for next line
                }
            }
    
        }
    }
    
    int main(void)
    {
        int i=0, j=0;
        int chess[n][n];
    
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                chess[i][j]=0;
            }
        }
        printf("%s\n\n",title);
        printf("4 queens for 4x4 chess:\n\n");
        queen(0,chess);
        printf("\nTotal: %d\n", count);
        return 0;
    }</span>

[SouthEast]: /images/20220718/69872c53979d4576a7e0c1dd4643f32a.png