Java教程

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

本文主要是介绍从经典八皇后问题看回溯算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

  八皇后问题是一个经典的问题,这个问题最早是在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;
}

 

这篇关于从经典八皇后问题看回溯算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!