【基础算法】回溯法与八皇后问题

 
技术分享
 

  在国际象棋中,皇后是最强大的一枚棋子,可以吃掉与其在同一行、列和斜线的敌方棋子。比中国象棋里的车强几百倍,比她那没用的老公更是强的飞起(国王只能前后左右斜线走一格)。上图右边高大的棋子即为皇后。

   八皇后问题是这样一个问题:将八个皇后摆在一张8*8的国际象棋棋盘上,使每个皇后都无法吃掉别的皇后,一共有多少种摆法?此问题在1848年由棋手马克斯·贝瑟尔提出,岂止是有年头,简直就是有年头,82年的拉菲分分钟被秒的渣都不剩。

  八皇后问题是典型的回溯法解决的问题,我们以这个问题为例介绍回溯法。

  所谓回溯法,名字高大上,思想很朴素。设想把你放在一个迷宫里,想要走出迷宫,最直接的办法是什么呢?没错,试。先选一条路走起,走不通就往回退尝试别的路,走不通继续往回退,直到找到出口或所有路都试过走不出去为止。

是的你没说错,这就是暴力破解。对于BigMoyan这种简单粗暴不喜欢动脑子的人来说实在是太合适了,盲僧李青说得好:如果暴力不是为了解题,那就毫无意义了。

技术分享

 

  尽管回溯法也算是暴力方法,但也不是特别暴力,特别暴力的相关部门都不让播,能播的都是可以接受的暴力。怎么说?考虑八皇后问题,解决这个问题最暴力的办法是这样的:

  有关部门不让播的方法:

  从8*8=64个格子里选8个格子,放皇后,测试是否满足条件,若满足则计数加1,否则换8个格子继续试。

  很显然, 64中选8,并不是个小数字,十亿级别的尝试次数,够暴力。

  这还是8*8的格子,要是换围棋棋盘……这画面太美我都不敢算。

  稍加分析,我们可以得到一个不那么暴力的办法,显然,每行每列最多只能有一个皇后,如果基于这个事实进行暴力破解,那结果会好得多。安排皇后时,第一行有8种选法,一旦第一行选定,假设选为(1,i),第二行只能选(2,j),其中j!=i,所以有7种选法。以此类推,需要穷举的情况有8!=40320种。

  看起来这个结果已经不错了,但尝试的次数是随问题规模按阶乘水平提高的,BigMoyan仍然不满意——咋可能满意嘛!回溯法还没出,我要是满意了剩下的篇幅讲啥。

  8皇后太多,后宫太过丰富BigMoyan可hold不住,不如我们先裁一半分析试试,于是BigMoyan与4位皇后办了离婚手续,同时把家缩小了一半,那么现在问题变成了4皇后问题,4个皇后在4*4的格子里各自安排不打架,一共有多少种安排方法?

技术分享

 

  试着来穷举一下,真的需要4!=24次尝试吗?

  现在我们把第一个皇后放在第一个格子,被涂黑的地方是不能放皇后的。

技术分享

 

  第二行的皇后只能放在第三格或第四格,比方我们放第三格,则:

技术分享

  糟啦撸,前两位皇后沆瀣一气,已经把第三行全部锁死了,第三位皇后无论放哪里都难逃被吃掉的厄运。于是在第一个皇后位于1号,第二个皇后位于3号的情况下问题无解。我们只能返回上一步来,给2号皇后换个位置。

技术分享

  显然,第三个皇后只有一个位置可选。当第三个皇后占据第三行蓝色空位时,第四行皇后无路可走,于是发生错误,返回上层调用(3号皇后),而3号也别无可去,继续返回上层调用(2号),2号已然无路可去,继续返回上层(1号),于是1号皇后改变位置如下,继续搜索。

技术分享

  话说道这里,想必读者对“回溯法”已经有了基本概念。然而所谓知易行难,理解算法和将算法写出来完全是两回事。按照BigMoyan的风格,下面该进行算法分析了,下面的代码改写自刘汝佳《算法竞赛入门经典》,几乎是BigMoyan看到的实现8皇后问题最简洁的代码,改写后整个函数只有10行。

void queen(int row){
    if(row==n)
        total++;
    else
        for(int col=0;col!=n;col++){
            c[row]=col;
            if(is_ok(row))
                queen(row+1);
        }        
}

 

  算法是逐行安排皇后的,其参数row为现在正执行到第几行。n是皇后数,在八皇后问题里当然就是8啦。

  第2行好理解,如果程序当前能正常执行到第8行,那自然是找到了一种解法,于是八皇后问题解法数加1。

  如果当前还没排到第八行,则进入else语句。遍历所有列col,将当前col存储在数组c里,然后使用is_ok()检查row行col列能不能摆皇后,若能摆皇后,则递归调用queen去安排下一列摆皇后的问题。

  还不太清楚?再慢点来,刚开始的时候row=0,意思是要对第0行摆皇后了。

  If判断失败,进入else,进入for循环,col初始化为0

  显然,0行0列的位置一定可以摆皇后的,因为这是第一个皇后啊,后宫空荡她想怎么折腾就怎么折腾,于是is_ok(0)测试成功,递归调用queen(1)安排第1行的皇后问题。

  第1行时row=1,进来if依然测试失败,进入for循环,col初始化为0。1行0列显然是不能摆皇后的,因为0行0列已经有一个圣母皇太后在那搁着了,于是is_ok()测试失败,循环什么也不做空转一圈,col变为1。1行1列依然is_ok()测试失败,一直到1行2列,发现可以摆皇后,于是继续递归queen(2)去安排第二个皇后位置。

  如果在某种情况下问题无解呢?例如前面在4皇后问题中,0行0列摆皇后是无解的。假设前面递归到queen(2)时候,发现第2行没有地方可以摆皇后,那怎么办呢?要注意queen(2)的调用是在queen(1)的for循环框架内的,queen(2)若无解,则自然而然queen(1)的for循环col自加1,即将第1行的皇后从1行2列改为1行3列的位置,检查可否放皇后后继续安排下一行的皇后。如此递归,当queen(0)的col自加到7,说明第一列的皇后已经遍历了从0行1列到0行7列,此时for循环结束,程序退出。

  在主函数中调用queen(0),得到正确结果,8皇后问题一共有92种解法。

  全部程序如下:

 

 1 #include<iostream>
 2 #include<math.h>
 3 using namespace std;
 4 
 5 int n=8;
 6 int total=0;
 7 int *c=new int(n);
 8 
 9 bool is_ok(int row){
10     for(int j=0;j!=row;j++){
11         if(c[row]==c[j] || row-c[row]==j-c[j] || row+c[row]==j+c[j])
12             return false;
13     }
14     return true;
15 }
16 
17 void queen(int row){
18     if(row==n)
19         total++;
20     else
21         for(int col=0;col!=n;col++){
22             c[row]=col;
23             if(is_ok(row))
24                 queen(row+1);
25         }       
26 }
27 
28 int main(){
29     queen(0);
30     cout<<total;
31     return 1;
32 }
33  

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。