八皇后问题

1.问题描述

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

2.解法一

2.1解题思路

首先我们分析一下问题的解,我们每取出一个皇后,放入一行,共有八种不同的放法,然后再放第二个皇后,同样如果不考虑规则,还是有八种放法。于是我们可以用一个八叉树来描述这个过程。从根节点开始,树每增加一层,便是多放一个皇后,直到第8层(根节点为0层),最后得到一个完全八叉树。

紧接着我们开始用深度优先遍历这个八叉树,在遍历的过程中,进行相应的条件的判断。以便去掉不合规则的子树。

那么具体用什么条件来进行子树的裁剪呢?

我们先对问题解的结构做一个约定。用X[i]来表示,在第i行,皇后放在了X[i]这个位置。

于是我们考虑第一个条件,不能再同一行,同一列于是我们得到x[i]不能相同。剩下一个条件是不能位于对角线上,这个条件不是很明显,我们经过分析得到,设两个不同的皇后分别在j,k行上,x[j],x[k]分别表示在j,k行的那一列上。那么不在同一对角线的条件可以写为abs((j-k))!=abs(x[j]-x[k]),其中abs为求绝对值的函数。

于是下面我们便可以利用一个递归的调用来深度遍历八叉树。

2.2具体实现

我们首先定义一个访问某节点所有子节点的函数。

void backtrack(int t)
{
    if(t>num) //num为皇后的数目
    {
        sum++;//sum为所有的可行的解
        for(int m = 1;m<num;m++){
            cout<<x[m];//这一行用输出当递归到叶节点的时候,一个可行解
        }
        cout<<endl;
    }
    else
        for(int i = 1;i<=num;i++){
            x[t] = i;
            if(place(t)) backtrack(t+1);//此处的place函数用来进行我们上面所说的条件的判断,如果成立,进入下一级递归
        }
}

下面我们定义了条件判断函数:

bool place(int k)
{
    for(int j = 1;j<k;j++)
        if(abs(x[k] - x[j]) == abs(k-j)||x[j] == x[k])
            return false;
        return true;
}

上面的函数便是按照我们上面说介绍的条件进行判断。最后就是主程序的调用了。

static int num;
static int *x;
static int sum;
void main()
{
    num = 8;
    sum = 0;
    x = new int[num+1];
    for(int i= 0;i<=num;i++)
        x[i] = 0;
    backtrack(1);
    cout<<"方案共有"<<sum;
}

3.解法二

3.1解题思路

剑指offer的思路是利用了全排列法的方法。由于八个皇后的任意两个不能处在同一行,那么这肯定是每一个皇后占据一行。于是我们可以定义一个数组ColumnIndex[8],数组中第i个数字表示位于第i行的皇后的列号。先把ColumnIndex的八个数字分别用0-7初始化,接下来我们要做的事情就是对数组ColumnIndex做全排列。由于我们是用不同的数字初始化数组中的数字,因此任意两个皇后肯定不同列。我们只需要判断得到的每一个排列对应的八个皇后是不是在同一对角斜线上,也就是数组的两个下标i和j,是不是i-j==ColumnIndex[i]-Column[j]或者j-i==ColumnIndex[i]-ColumnIndex[j]。

3.2具体实现

int g_number = 0;

//对八个皇后的位置进行正确性判断
bool check(int ColumnIndex[], int length)
{
    for(int i = 0; i < length; ++ i)
    {
        for(int j = i + 1; j < length; ++ j)
        {
            if((i - j == ColumnIndex[i] - ColumnIndex[j])
                || (j - i == ColumnIndex[i] - ColumnIndex[j]))
            return false;
        }
    }
    return true;
}

void printQueen(int ColumnIndex[], int length)
{
    printf("solution %d\n", g_number);
    for(int i = 0; i < length; ++i)
        printf("%d\t", ColumnIndex[i]);
    printf("\n");
}

//对数组进行排列的核心函数
//
void permutation(int ColumnIndex[], int length, int index)
{
    //当最后一个子问题已经解决
    if(index == length){
        if(check(ColumnIndex, length)){
            ++g_number;
            printQueen(ColumnIndex,length);
        }
    }
    else{
        //分别与后面的元素交换
        for(int i = index; i < length; ++ i){
            int temp = ColumnIndex[i];
            ColumnIndex[i] = ColumnIndex[index];
            ColumnIndex[index] = temp;

            //后面的数组形成子问题,递归求解
            permutation(ColumnIndex, length, index + 1);

            //回溯到上一个状态,准备与下一个元素交换
            temp = ColumnIndex[index];
            ColumnIndex[index] = ColumnIndex[i];
            ColumnIndex[i] = temp;
        }
    }
}

void eightQueen()
{
    const int queens = 8;
    int ColumnIndex[queens];
    for(int i = 0; i < queens; ++ i)
        ColumnIndex[i] = i;
    permutation(ColumnIndex, queens, 0);
}

参考文献

[1]http://www.cnblogs.com/gaoteng/archive/2012/04/11/2442692.html. [2]http://zhedahht.blog.163.com/blog/static/2541117420114331616329/.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏绿巨人专栏

读书笔记: 范畴论

一个范畴是一个带标签的有向图,其节点为对象(object),带有标签的有向边为箭头(arrow or morphism)。

24820
来自专栏Android机器圈

排序算法

上面结果可以说明,虽然也是比较了和冒泡一样多的次数,但是交换缺少了很多。所以时间为N²/2

21050
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(11-15打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

12810
来自专栏Jacklin攻城狮

简谈常用算法

9820
来自专栏大数据学习笔记

Java程序设计(Java9版):第3章 流程控制

第3章 流程控制 学习要点 掌握三种流程控制 掌握简单的输入输出 了解三种循环设计方法 掌握数组、字符串和枚举类型 3.1 面向过程介绍...

38770
来自专栏数据结构与算法

后缀自动机经典操作

20540
来自专栏数据结构与算法

字符串hash入门

简单介绍一下字符串hash 相信大家对于hash都不陌生 hash算法广泛应用于计算机的各类领域,像什么md5,文件效验,磁力链接 等等都会用到hash算法 在...

72750
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

21220
来自专栏窗户

Scheme来实现八皇后问题(1)

  皇后是国际象棋里杀力最强的子,它可以吃掉同一条横线、竖线上其他棋子,也可以吃掉所在的两条斜线上的其他棋子(当然在角上只有一条斜线)。

21340
来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

33250

扫码关注云+社区

领取腾讯云代金券