递归典例之八皇后问题

问题描述：

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

分析：先将棋盘的危险和安全数字化，1为危险，0为安全，皇后被放置前棋盘所有位置均为0。我们从第一列至第八列依次考虑，先考虑第一列，第一列我们有八种选择，但要注意，循环选择第一列元素时，要记得重置棋盘！选择一个位置我们用chose函数来表示。chose的作用是先判断此次选择的位置是不是最后一列，若不是，则将此次放置位置的同行同列及同对角线全置为1，并且将此次放置位置还原成0，将皇后与棋盘中未放置皇后的位置分离开来。然后列数加一，在该列安全的位置依次放置皇后，（即对该列元素为1的位置再次调用chose），同样要记住，此次调用结束到下次调用前，要将棋盘还原成未被本次循环调用前的模样。直到调用chose时，调用列即是最后一列，那么检测各列棋盘中放置皇后的行数（即数值为0的行数），输出行数的加一即可。

代码如下：

//声明: 棋盘中1为危险，0为安全
#include <stdio.h>
int solutionsum = 1;
//void print(int chessboard[][8],int m,int n);测试使用
void chose(int chessboard[][8],int row,int column);
void reset(int chessboard[][8]);
int main(void)
{
    int chessboard[8][8] = {0},i;
    for(i = 0; i < 8; i++)
    {
        chose(chessboard,i,0);  //按第一列依次选择元素
        reset(chessboard);      //将棋盘各元素重置为0
    }
    //chose(chessboard,7,0);测试使用
    //print(chessboard,8,8);测试使用
}
void print(int chessboard[][8],int m,int n)
{
    int i,j;
    for(i = 0; i < 8; i++)
    {
        for(j = 0; j < 8; j++)
        {
            printf("%d ",*(*(chessboard+i)+j));
        }
        printf("\n");
    }
}
void chose(int chessboard[][8],int row,int column)
{
    int i,j,k,l;
    int recordchessboard[8][8];     //记录棋盘状态
    if(column < 7)                  //若此时列非最后一列
    {
        for(i = 0; i < 8; i++)
        {
            for(j = 0; j < 8; j++)
            {
                if(i == row || j == column || (i - row) == (j - column) || (i - row) == (column - j))
                {
                    chessboard[i][j] = 1;
                }
            }
        }                           //函数本次选择元素的同列同行同对角线的元素全置1
        chessboard[row][column] = 0;//函数本次选择元素在上述置1过程中也被置1，为了与其他元素分辨，此处将其重置为0

        for(i = 0; i < 8; i++)
        {
            for(j = 0; j < 8; j++)
            {
                recordchessboard[i][j] = chessboard[i][j];
            }
        }                            //记录棋盘

        for(i = 0; i < 8; i++)
        {
                if(chessboard[i][column+1] == 0)
                {
                    chose(chessboard,i,column+1);//调用一次后棋盘变化，应将其还原至未被调用前的状态
                    for(k = 0; k < 8; k++)
                    {
                        for(l = 0; l < 8; l++)
                        {
                            chessboard[k][l] = recordchessboard[k][l];  //还原棋盘
                        }
                    }      
                }
        }
    }
    else
    {
        printf("[%2d]: ",solutionsum++);
        for(j = 0; j < 8; j++)
        {
            for(i = 0; i < 8; i++)
            {
                if(chessboard[i][j] == 0)
                {
                    printf("%d ",i+1);
                }
                
            }
        }
        printf("\n");
    } 
}
void reset(int chessboard[][8])
{
    int i,j;
    for(i = 0; i < 8; i++)
    {
        for(j = 0; j < 8; j++)
        {
            chessboard[i][j] = 0;
        }
    }
}

希望本篇文章对各位友友们有所帮助~