八皇后问题是一个经典的问题,这个问题最早是在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<row;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<iostream> #include<cmath> using namespace std; int total=0; int c[8]; bool row_check(int row){ for(int i=0;i<row;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; }