从经典八皇后问题看回溯算法

题目描述

　　八皇后问题是一个经典的问题，这个问题最早是在1848年，由国际西洋棋棋手马克斯·贝瑟尔提出的，在两个世纪之后的今天，依然被人们津津乐道。这个问题的描述如下：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。

回溯思想

　　在解八皇后问题之前，我们先来看这样一个例子，如下图所示，是游戏的小地图：

　　现在你站在了路口A，前面有四个房间1、2、3、4。其中某一个房间有宝箱，而没有宝箱的房间也不会有陷阱和额外的敌人，如果是你，你会如何探索前面的区域？稍加思考便可以得到答案，既然不知道宝箱具体会在哪里，那么最好的方法就是地毯式搜索，去每个房间看一下，但这个过程要想节约跑路的时间，一般我们会这样规划路线：

　　（1）从路口A出发，经过路口C，先走向房间4

　　（2）若房间4没有，那么我们退回路口C，再去探索房间3

　　（3）若房间3没有，则退回路口A，经过路口B，探索房间2

　　（4）若房间2还是没有，则退回路口B，探索房间1

　　这样的规划能够确保我们走最少的重复路线，其实这就是回溯法的核心思想了，当前选择不是最优解或者无法达到目标时，就退回上一步重新选择，若上一步还不行就继续回溯上上步……，以此类推。

　　回溯法是一种搜索方法，通过回溯的方法，能避免一些无意义的重复计算，例如在上面的例子中，如果是按照2-3-1-4的顺序搜索，那么就会多走一段A到B和A到C的路程，但这段路程是可以用回溯思想的规划避开的。

八皇后问题的求解思路

　　现在让我们把目光重新放回到八皇后问题上，对于这个问题，如果不采用任何算法思想而直接暴力枚举的话，总的解空间为64选8，即C(64,8)=64!/8!*(64-8)!,可以简单写个程序来计算答案（因为计算过程会发生溢出，所以为了方便，这里就直接用Python偷懒了）

def fact(n):
    if n==1:
        return 1
    else:
        return fact(n-1)*n

print(fact(64)/(fact(8)*fact(56)))

　　得到的答案为：4426165368，也就是44亿种组合。很显然，这是无法接受的。

　　现在来分析一下这个问题，既然我们知道所有的皇后不能在同一行、同一列和同一斜线上，那么每行每列都只能有一个皇后。因此我们采用逐行扫描的方式，一行一行地安排皇后。其基本思路为：

　　1.从第一行开始安排皇后

　　2.安排皇后时，从该行的第一列开始检查，直到找到安全的位置为止。对于安全位置的具体检查方法为：

　　　　（1）该列没有其它皇后

　　　　（2）该列的左上角对角线上没有其它皇后

　　　　（3）该列的右上角对角线上没有其它皇后

　　3.若找到了安全位置，则在安全位置放置皇后，并开始安排下一层

　　4.若第八行已经安排好了，则说明找到了一组解，计数加一，然后重新尝试第八行其它位置是否可行。

　　5.若该行没找到安全位置，则回溯到上一行，移动上一行的皇后，重新开始安排，若上一行还是不行，则继续回溯到上上行。

　　6.若回溯到第一行时，第一行所有的位置都已经放过了，证明我们已经遍历完了所有的可能性，此时结束搜索，输出最终答案。

代码实施

　　一般来说，对于八皇后问题这种8x8的矩阵，会想到用二维数组来模拟，这肯定是可行的，但不是最优的。因为我们是逐行扫描的，所以其实我们需要的信息是”前面行的皇后放置在哪一列了“。因此，只需要一个长度为8的一维数组，分别存储第1到第8行皇后所在的列数。

　　按照之前的思路，要解决这个问题有两个难点，一是检查某行是否有安全位置，另一个就是回溯的设计。

安全位置的检查

　　我们刚说的用一维数组存储每一行皇后所在的列数，数组下标代表行数，该下标对应的元素为该行皇后所在的列数。当检查第n行的安全位置时，思路是这样的：

　　1，从第n行最左边的一列开始，逐个往右检查

　　2，检查某一列是否可行时，需要遍历从第一行到第n-1行的第1列到第8列，看看是否有会造成危险的皇后

　　定义一个函数row_check()检查某一行是否有安全位置，参数为行数，假设用来存储皇后位置的数组名为c，则c[row]表示当前尝试摆放的皇后列数。伪代码描述如下：

//遍历该行每一列
for(int col=0;col<8;col++){
    //尝试在第col列摆放皇后        
     c[row]=col;   
    if(row_check(row)){
        该列可以摆放皇后，第row行处理完毕，继续尝试row+1行
    }
    //若检查未通过，则进行下一次循环，尝试下一列        
}

　　那具体的row_check的函数实现为：

bool row_check(int row){
    //检查第1到第row-1行放置的皇后      
    for(int i=0;i){
        if(c[row]==c[i] ||abs(c[row]-c[i])==abs(row-i))
            return false;
    }
    return true;
}

　　其中需要说明几点，c[row]==c[i]，表示当前尝试的列数，在之前的第i行的同一列已经摆放过皇后了。而对角线的检查是这样的，把棋盘的行看作是x轴（i），列看作是y轴(c[i])，如果处于对角线则斜率为1或者-1，也就是y坐标之差的绝对值与x坐标之差的绝对值是相等的。即abs(c[row]-c[i])==abs(row-i)。

回溯的设计

　　回溯法的思想和递归契合度是比较高的，在递归出结果之前，可以一直往下递归尝试，如果不行，则返回上一层的递归调用。代码如下：

//函数queen表示安排第row行皇后的位置
void queen(int row){
    //当第8行安排完毕，证明找到了一组解，计数器加一
    if(row==8) {
        total++;
    }
    else
        //从第row行的第0列开始,逐个尝试
        for(int col=0;col<8;col++){
             //尝试在当前列安排皇后
            c[row]=col;
            //如果可行，则递归安排下一行，如果不可行，则不进行递归，继续循环尝试当前行的下一列。当循环结束仍然没有安全位置，则本行无解，此次调用结束。
            if(row_check(row))
                queen(row+1);
        }
}    

整体代码实现

#include
#include

using namespace std;

int total=0;
int c[8];

bool row_check(int row){
    for(int i=0;i){
        if(c[row]==c[i] ||abs(c[row]-c[i])==abs(row-i))
            return false;
    }
    return true;
}

void queen(int row){
    if(row==8) {
        total++;
    }
    else
        for(int col=0;col<8;col++){
            c[row]=col;
            if(row_check(row))
                queen(row+1);
        }
}

int main(){
    queen(0);
    cout<<total;
    return 0;
}