关于蓝桥杯15届校赛第五题-八皇后问题

昨天比较忙，所以博客只能推迟到今天凌晨写了，无奈，主要是想总结一下自己做这道题后的一些见解和一些疑惑。

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。用c写出有多少种摆法。

看到这道题，我第一想法是用冒泡的方法，得到一串八个数据，让每两个数据之间符合一定的关系即可，但是仔细一想，如果这样子做，一效率太低，二条件过于繁琐，所以就放弃了，转而想到一个方法，就是利用二维数组。给每个格子初始定义为0，然后将放皇后的定义为1，将每一行每一列每一对角线都分别相加，结果均为1的方案提取出来使摆法加一，最后得出正确摆法数。然而这样子做在加的过程会极其复杂，所以再一次改进了自己的方针。最后的方针是在第二种想法的基础上加以改进，首先依然是定义一个二维数组，然后全赋予初始值0，即没有皇后，为假，然后定义一个递归函数，在递归函数内定义三个数组a［8］，b［15］，c［15］分别表示每一竖皇后剩余数，从↗️到↙️对角线皇后剩余数，从↖️到↘️对角线皇后剩余数，初始均为1,

固定以行为基础去递归，当符合a[col]&&b[n+col]&&c[n-col+7]，即各项均为1时，为真，则放好一个皇后Queen［n］［col］，与其相关的a［col］，b［n+col］，c［n－col＋7］都被赋值为0（col为行数），为后续的判定提供判断，当递归到第八行时，符合每次递归的条件的情况使摆法加一，如果不到第八行则持续递归，并在每一次循环结束后都要取消皇后位置，即恢复初始棋盘赋值，保证后面的循环的功能性。每次递归参数n加一，由此方案代码如下：

#include<stdio.h>
int Chess[8][8]={
  0};//定义二维数组代表8x8棋盘
int a[8],b[15],c[15];//定义a［8］代表一竖是八行，定义b［15］，c［15］代表从↗️到↙️对角线和从↖️到↘️对角线
int sum=0;//定义sum累计确定一共有多少种结果
void Queen(int n)//定义放置皇后的函数
{
    int col;//定义col控制皇后的位置
    for(col=0;col<8;col++)//从第一行开始确定皇后的位置，逐次递增，col表示皇后在该行的第几个位置
    {
        if(a[col]&&b[n+col]&&c[n-col+7])//判断该位置竖、对角线都还有1个皇后可以放，为真，即＝1
        {
            Chess[n][col]=1;//放置皇后
            a[col]=0;//放置皇后后，该位置的竖剩余可放皇后数变为0
            b[n+col]=0;//放置皇后后，该位置的由↗️到↙️对角线剩余可放皇后数变为0
            c[n-col+7]=0;//放置皇后后，该位置的由↖️到↘️对角线剩余可放皇后数变为0
            if(n==7)//判断是否到第八行，不到第八行则执行else
            {
                sum++;//循环到第八行，都符合题中条件，摆法加一
            }
            else//执行，递归
            {
                Queen(n+1);//调用函数Queen，参数逐次加一
            }
            Chess[n][col]=0;//取消皇后,恢复棋盘初始值
            b[n+col]=1;//恢复初始值，保证下一次循环的功能性
            c[n-col+7]=1;//恢复初始值，保证下一次循环的功能性
            a[col]=1;//恢复初始值，保证下一次循环的功能性
        }
    }
}
int main()//主函数
{
    int i;//定义计数变量i
    for(i=0;i<8;i++)//使a［i］＝1，使初始值都为1，即真
    {
        a[i]=1;
    }
    for(i=0;i<15;i++)//使b［i］＝1，c［i］＝1，使初始值都为1，即真
    {
        b[i]=1;
        c[i]=1;
    }
    Queen(0);//调用递归函数Queen，实现sum的累加
    printf("%d\n",sum);//输出sum的值
    return 0;//返回0
}

经验证，代码在Mac系统Xcode编译器下输出结果为92，正确，故基本代码无误。然而关于这段代码我依然存在一个小问题无法通晓，即在主函数中为何不能将其中的两个循环赋值函数改为在定义函数时直接赋值的方式，经过多次更改，均无法无误编译，故几番思索，却依然无法明了，希望这个问题可以趁早解决，得到我想要的答案，问题截图如下。

总结已毕，最后，想起从前看到的一个故事，感触很深。

每年，澳大利亚都会举行一场悉尼至墨尔本的耐力长跑，全程875公里，被认为是世界上赛程最长、最严酷的超级马拉松。这项漫长、严酷的赛跑耗时五天，参赛者通常都是受过特殊训练的世界级选手。这些选手大多不到三十岁，有“耐克”等知名运动品牌做后盾，全副武装着最昂贵的赞助训练装备和跑鞋。1983年，耐力长跑赛场上，出现了一个名叫克里夫·杨的家伙。起初，谁也没在意他，大家都以为他是去那儿看比赛的。毕竟，克里夫·杨已经61岁了，穿着条工装裤，跑鞋外面套了双橡胶靴。当克里夫·杨上前领取他的运动员号码时，人们这才明白原来他是来参赛的。他将跻身150名世界级选手的行列参加赛跑！这些选手压根儿没想到，还有一件令人称奇的事，克里夫惟一的教练竟是他81岁高龄的母亲耐威尔·冉。1983年他以61岁的高龄5天15时4分的成绩跑完了这场长达875公里的悉尼至墨尔本马拉松比赛，成功地击败了世界上最优秀的长跑运动员，捧走了冠军奖杯，以提前9小时的成绩打破了记录，成了国家英雄！1997年，76岁的克里夫·杨再露头角，力图成为年龄最大的环澳长跑选手，为无家可归的儿童募集资金。整个赛程16000公里，他跑完了6520公里，后来因母亲生病而被迫退出了比赛。他对长跑的热爱从未消减，2000年，他在一项1600公里比赛中跑完了921公里，一星期后在他盖里布兰德的家中病倒，从此再也没有力气跑了。轻度中风结束了他英雄般的长跑生涯。

其实，学习也如同一场马拉松，一场生命的马拉松，只要坚持，你就可以斡旋而归，生命不息，战斗不止！奋斗吧，逐梦者……

关于蓝桥杯15届校赛第五题-八皇后问题

全站热榜