当前课程知识点:程序设计基础 >  第五章 分治思想与递归 >  5.4 分书与八皇后 >  5.4.7 代码解说——八皇后问题

返回《程序设计基础》慕课在线视频课程列表

5.4.7 代码解说——八皇后问题在线视频

5.4.7 代码解说——八皇后问题

下一节:5.5.1 问题描述

返回《程序设计基础》慕课在线视频列表

5.4.7 代码解说——八皇后问题课程教案、知识点、字幕

好 下面我们在

看完分书这个代码之后

我们来看一看八皇后的求解的代码

我们还是采取跟刚才类似的方法

先看一下程序的整体的框架

然后再来看最核心的递归函数的实现

这样大家更容易集中到

最关键的算法实现上去

下面看到的是程序的整体的算法的实现

那么它仍然是分成几个部分

首先呢 顶上是它的

头文件的包含

这个我们不用再多说了

接着是若干个全局变量的定义

待会我们来解释

然后再往下就是核心的递归函数try

我们还是用try这个函数

来做这样一个函数命名

为了跟刚才那个有一点点区别

我们这次不是按照行来try它了

我们按照列来组合

就一列一列去摆这个皇后

摆第一列看到它放到哪一行

再摆第二列

看它放在第几行

最后摆到第八列

这样话 也能够用例子来表示

行跟列谁来去做这个

依次去做 都是

按行来做按列来做都是可以的

下面是main函数

这个main函数大家再次看到

它也是先做变量的初始化

然后调try这个函数

这个是一样的

只不过具体的内容上面稍有差别

但是它的性质是相通的

这就再次告诉我们

我们去做题目也好

思考问题也好

最关键的是把它算法的共性

能够理解能够掌握运用

而不是对某个具体的问题

说我今天会讲背会解八皇后了

分书的问题给你你就不会做了

反过来也是以一样

刚讲的分书 八皇后不会做了

这个就不太好

所以我们要抓到这些代码实现里头的

共性的部分

要去透过不同的代码

看到相同的地方

好首先来看

在这个八皇后里头

用到的全局变量

首先依然是有一个

变量要存储它的方案数

接着我们要有一个数组来存放

在8个皇后它摆到棋盘上之后

它到底占的行是哪一个

根据我们前面的解释

我们是一列一列去摆放这些皇后

每一列必然有皇后

所以呢 这些皇后

到底摆在哪一列上面

其实是不言而喻的

那肯定是零到七这些列啊

因此我们只需要去依次记录

每一列它到底摆到哪一行上去就行

所以用一个一维数组

就足以记录这八个皇后的位置

虽然这八个皇后位置每一个

都是二维的 有行有列啊

但是其实你只用一个

一维的数组就把它们全记下来了

因为我们利用到了这个

数组的下标

用它的下标代表了它的列

第零列就放到第零个元素里头

第一列就放到第一个元素里头

那第零个元素是什么那

存着是它的行号

接着 我们看到有三个bool数组

这三个bool数组就是我们前面讲到的

在这个解题的过程当中

大家在摆棋子的过程当中

那么每一个位置上的安全性的记录

就这个位置是不是安全的

能不能放棋子

我们前面分析说

我们一共需要三个数组来存放它

第一个 你现在尝试的这一行安全不安全

因为我们事先知道是按照列来的

一列上绝不可能摆放两个皇后

所以列上面这个问题你不用操心

对吧 因为我可以保证我是一列一列做的

做这一列做完了就做完了

我不可能在里头摆两个

所以这个列上的安全性不用去考虑

我们只用考虑行

所以呢 一个数组表示行上面的安全性

剩下的两个是表示对角线

在这个矩阵里头

这种45°和这样的135°

正反两个对角线

它的斜线的数量

不是一个 各有好多个

而每一个呢 它的信息

每一条这样的斜线

它的这个安全性我都要记录

所以我们用的两个数组

分别去记录这个方向

和这个方向的若干条线

这就是为什么这是一个数组的原因

那为什么我们用的是一个

17这样的元素呢

那是因为我们的正反两方向

这个斜线去记录它的状态的时候

经过我们前面的一个简单的

几何知识的运用

数学知识的运用

我们知道在一根斜线上面横纵坐标之间

它的和它的差是有特定关系的

一根线上的和或差它的值是一样的

那么基于这样的考虑呢

我们就用它的这个和或者差的值去做下标

但是呢 很不幸因为这个求和的时候

它当然都是正数

但是求差的时候 它有可能差出负数

我们知道负数是不可以做数字下标的

我们需要给它调整到

一个适当的范围里头去

因此呢 这个数组啊

我们就把它稍稍的变得大了一点点

然后到时候会增加一个常量值

让它调整到一个非负的范围里去

这就是大家在代码里第三行里看到的

那个常量变量的这种定义

Normalize 这个变量

让它等于九

就是为了去调整那个下标

使得正反两个方向

数组他们的下标

在同一个范围内变化

看上去会比较自然一点

这是关于这些状态变量它的含义

那有了这个解释之后

我们看主程序就比较清楚了

他们做了一些初始化的工作

Num等于零 没有方案

方案为零 他们的初始值为零

将来呢每找到一个方案

那么就会++

这是一个不能忘记的地方

接着 每一行

就是 如果是按列存么

这每一行它是安全的

所以呢 刚开始s[i]=true

每一行都安全 空的

各个斜线也是安全的

所以呢 这个L[i] R[i]都等于true

那就都把它赋值为true

表示这个棋盘空空的 什么都可以放

OK 万事具备开始尝试

所以从第一列开始 Try(1)

比如说我们编号是从一开始的

Try(1) 从第一列开始来放这个皇后

那么,这篇

就是try这个函数的实现

第几列开始做

那么根据前面讲过的

一个递归的函数最重要的是

把它的中止条件事先要想明白

很多递归的程序最后会出现

死循环、死机这样的现象

就是因为它的中止条件无法达到

永远也不可停止

那就一直转下去

最后直到转到你的程序崩溃为止

程序为什么会崩溃呢

这就牵扯到函数调用的时候

会有一个函数调用堆栈的一种内存需要

内存不是无止境的

终有一天会耗尽

最后程序就得退出了

这是关于为什么要强调中止条件

事先要把它想清楚的一个很重要的原因

因为它往往是程序出bug的地方

所以对于我们这个问题要看到

什么时候它能够中止呢

那当然是棋盘上八个皇后都摆上去了

八个皇后都摆上去了

那么这个时候

一定想去试图想摆第九个皇后

就意味着前面八个皇后摆好了

所以if(col)列它的的序号

是第九列的时候

表示前八列

记住我们这个题

是从1开始编号的

所以12345678搞定了

现在等于9了

就意味着摆完了

所以Num++

方案数加一

输出这些方案

我们前面说

每一个方案是把相应的

每一列的行号 所在的行记下来了

所以我们只需要

依次去打印这八列

它们到底放到哪一行

就OK了

所以cout

q这个数组

第k k就表示第几列

然后q、k存的是这一个列行

存的那个元素的行的位置

把它打出来

但是想想我们前面讲的

分书是不是也是这样

如果这个五本书都分出去了

打印方案数

然后cout 输出take

括号id 把它打出来

和这个地方是一致的

这就是它的中止条件

下面接着看下半部分

按照我们前面讲的算法的思路

是要依次去枚举每一行

在分书那边是依次去枚举每一列

我们这边稍稍倒一下

当然底下可以自己换掉

可以换成依次枚举每一列

现在是故意用成

依次去枚举每一行

这个行列都可以去枚举

那么怎么依次去枚举

for循环

row等于1到row等于8八行

一行一行去试

怎么试呢,看循环体

尝试尝试嘛,拿过来判断

所以上来就是一个if

if这一行安全吗

这一行怎么安全

s[row]是true它就是安全

那么这个斜线安全吗

两条斜线 所以

and一个东西又and一个

左斜线右斜线分别就是

r括号,注意我们前面通过

几何分析,数学图示的方法

我们知道斜线上面每一个点

它的横纵坐标和或者差是一样的

所以我们用那个一样的值

作为它的下标

[row+col]就表示

相应的所在的那个斜线

是谁所在的斜线呢

是现在正在try的这一列

和现在正在尝试的这一行

正好一个交叉点

那个点所在的两条斜线

只有两条

虽然整个棋盘上的斜线有好几条

这个斜线也好几条

但是对于特定的某个点来讲

这个斜线只有两条

所以这个元素这个这个元素

分别代表左斜线和右斜线

那么在这个斜线上面

由于有坐标的差

所以需要把它的位置调整一下

加了一个Normalize

那为什么加的是9呢

就是想让它们加完之后

两个数组的下标的起始值

都是从一个相同的地方开始

大家底下去思考一下

就知道为什么是9了

好了,如果行也安全

这样的斜线 这样的斜线都安全

那好,可以放棋子了

怎么放棋子呢

其实和我们前面说的分书是一个道理

怎么叫分呢

用变量把它记下来

就叫把书分出去了

用变量把棋盘的位置存起来

就叫做棋盘上放了这个棋子

所以我们用q[col]表示

在这一列上面放了一个棋

放棋放哪呢

放到一个行上去了

所以把这个行的值记下来

q[col]等于row

这就是把它记下来了

那么在现实生活当中

就代表棋子放在那一行上面去了

按照我们前面讲的

放上去会有后续的效应

会对后面有影响的

影响体现在安全性发生了变化

就像大家在前面

看动画的时候看到的样子

每一个棋子放上去

都会产生所谓攻击范围

一旦有棋子在那里出现

就会被吃掉

所以现在这个棋子

放到row行col列上面去了

那么相应的行跟列的安全性

就发生了变化

行s[row]=false

这一行在后面的列里头不能再用了

斜线 也是把它定义成false

那大家可以看到

我们下一步 设好状态之后

就要进行递归调用

所以Try下一列

因为这一列完成了啊

我们完成下一列Try[col+1]

根据前面的讨论

类似的 所以后面就简单了

要回退到尝试这一列之前的状态

尝试这一列之前

没有做这些安全性的改变

所以要把这种改变再退回去

所以我们下面是相应的行相应的斜线

安全性又变成true

可以等同于理解为

这个棋子又被拿走了

对吧,一拿走不就安全了嘛

所以呢,这些值又被设成true

这个时候就表示

这一次行的尝试就完成了

可以进行下一行的尝试了

可以进行下一个for循环

这就是在递归的方法里头

有一个通过回溯去恢复到以前的某种状态

从而平等的去枚举下一种可能性

这是一个不可缺少的一个动作

少了它这个题目就做不对了

这样的话我们就依次枚举了八行

然后每次枚举的时候做了递归调用

然后在最前面设置了终止条件

这样一个try的函数的递归的实现

就说完了

这就是一个八皇后的问题的代码的实现

从这里头我们再次看到

通过代码这个层面

再次看到分书的问题和八皇后问题

它们的解题思路是完全一样的

虽然在细节代码上有差别

但是从思路层面上

是完全一致的

希望大家仔细体会

这个思路上的算法上的共同之处

从而掌握这一类问题

举一反三,我现在举了两个例子了

所以要把这一类问题

都掌握它的解题办法

程序设计基础课程列表:

第一章 编程初步

-1.1 基础知识

--1.1.1 什么是程序?什么是语言?

--1.1.2 什么是程序设计?

--1.1.3 计算机发展史

-1.2 买菜问题

--1.2.1 问题描述

--1.2.2 程序的基本结构

-1.3 数学运算

--1.3.1 数学运算符

--1.3.2 数学函数

-1.4 补充说明

--1.4.1 编程环境的下载与安装

--1.4.2 程序基本结构中的含义

--1.4.3 格式与风格

-1.5 总结

--1.5 总结

-程设论道

--程设论道

-师生问答

--师生问答一:怎样学好程序设计

--师生问答二:语言选择

--师生问答三:关于函数

-第一章 编程初步--语法自测

第二章 变量与代数思维

-2.1 关于超级计算器的几点思考

--2.1.1 关于超级计算器的几点思考

-2.2 电子秤模拟 — 背景介绍及需求分析

--2.2.1 电子秤模拟 — 背景介绍及需求分析

-2.3 电子秤模拟 — 代码实现

--2.3.1 电子秤模拟 — 代码实现

-2.4 变量定义与变量类型

--2.4.1 变量定义与变量类型

-2.5 猜数游戏与数据表示

--2.5.1 猜数游戏与数据表示

-2.6 关于变量的讨论

--2.6.1 变量的初始值

--2.6.2 变量类型

--2.6.3 变量内存单元地址

--2.6.4 存“变量地址”的变量——指针

--2.6.5 指针的 读/写 操作

--2.6.6 指针的 加/减 操作

--公告

-2.7 变量体现的计算思维

--2.7.1 变量体现的计算思维

-程设论道

--程设论道

-师生问答

--师生问答

-第二章 变量与代数思维--语法自测

第三章 逻辑推理与枚举解题

-3.1 谁做的好事——语义表示

--3.1.1 谁做的好事——语义表示

-3.2 谁做的好事——真假检查

--3.2.1 谁做的好事——真假检查

-3.3 谁做的好事——循环枚举

--3.3.1 谁做的好事——循环枚举

-3.4 谁是嫌疑犯——多重循环枚举

--3.4.1 谁是嫌疑犯——多重循环枚举

-3.5 谁是嫌疑犯——破案线索表示

--3.5.1 谁是嫌疑犯——破案线索表示

-3.6 谁是嫌疑犯——用二进制枚举

--3.6.1 谁是嫌疑犯——用二进制枚举

-程设论道

--程设论道一

--程设论道二

--程设论道三

-师生问答

--师生问答一:字符与ASCII码表

--师生问答二:其他循环语句、运算符优先级与变量作用域

-第三章 逻辑推理与枚举解题--语法自测

第四章 筛法与查找

-4.1 插花游戏

--4.1.1 问题提出(求素数)

--4.1.2 函数初探

--4.1.3 运行演示

-4.2 筛法

--4.2.1 筛法思路

--4.2.2 数组的定义

--4.2.3 代码翻译

--4.2.4 运行演示

--4.2.5 小朋友数人数

--4.2.6 运行演示

--4.2.7 韩信点兵

-4.3 线性查找

--4.3.1 扑克查找问题

--4.3.2 扑克查找问题代码翻译

--4.3.3 最小值问题

--4.3.4 最小值问题代码翻译

-4.4 折半查找

--4.4.1 提问

--4.4.2 折半查找思路

--4.4.3 折半查找代码翻译

--4.4.4 折半查找运行演示

-4.5 排序问题

--4.5.1 插入排序

--4.5.2 选择排序

--4.5.3 函数写法

--4.5.4 运行演示

-4.6 总结

--4.6.1 总结

-程设论道

--程设论道一:数组与编码思维

--程设论道二:筛法

-师生问答

--师生问答一:函数与面向过程编程

--师生问答二:数组的下标越界

-第四章 筛法与查找--语法自测

第五章 分治思想与递归

-5.1 阶乘

--5.1.1 阶乘问题

--5.1.2 递归解法

--5.1.3 递归小结

-5.2 排序

--5.2.1 归并排序——总体思路

--5.2.2 归并排序——思路分解

--5.2.3 归并排序——代码解说

--5.2.4 快速排序——总体思路

--5.2.5 快速排序——代码解说

--5.2.6 排序总结

-5.3 矩阵填充

--5.3.1 矩阵填充问题

--5.3.2 代码解说

-5.4 分书与八皇后

--5.4.1 问题描述

--5.4.2 问题分析——共性

--5.4.3 问题分析——区别

--5.4.4 解题准备——二维数组

--5.4.5 解题准备——递归设计

--5.4.6 代码解说——分书问题

--5.4.7 代码解说——八皇后问题

-5.5 青蛙过河

--5.5.1 问题描述

--5.5.2 问题分析——简单情况

--5.5.3 问题分析——复杂情况

--5.5.4 问题分析——一般情况

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答一

--师生问答二

-第五章 分治思想与递归--语法自测

第六章 递推与动态规划

-6.1 兔子数列问题

--6.1.1 问题描述

--6.1.2 按大小兔子分别递推

--6.1.3 按总数递推

--6.1.4 不用数组递推

-6.2 分鱼问题

--6.2.1 问题描述

--6.2.2 从A到E递推

--6.2.3 从E到A递推

-6.3 橱窗的插花问题

--6.3.1 问题描述

--6.3.2 题意理解与分析

--6.3.3 用枚举思想解题

--6.3.4 采用递推的优化算法

--6.3.5.1 采用动态规划算法—优化分析

--6.3.5.2 采用动态规划算法—递推代码

--6.3.5.3 采用动态规划算法—计算过程

--6.3.5.4 采用动态规划算法—输出方案

--6.3.6 动态规划总结

-6.4 最长公共子序列问题

--6.4.1 问题描述与理解

--6.4.2 问题分析

--6.4.3.1 动态规划解题(1)

--6.4.3.2 动态规划解题(2)

--6.4.3.3 动态规划代码

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第六章 递推与动态规划--语法自测

第七章 文本数据处理

-7.1 统计记录总数

--7.1.1 问题分析

--7.1.2 读文件操作

-7.2 统计活跃用户数

--7.2.1 问题分析

--7.2.2 字符串

--7.2.3 程序翻译与演示

-7.3 统计在线时长

--7.3.1 问题分析

--7.3.2 结构

--7.3.3 程序翻译与演示

--7.3.4 写文件操作

-7.4 总结

--7.4.1 总结

-程设论道

--程设论道

-师生问答

--师生问答

-第七章 文本数据处理--语法自测

第八章 非文本数据处理

-8.1 将数据组织成链表

--8.1.1 链表的基本概念

--8.1.2 代码讲解

--8.1.3 链表遍历与释放

-8.2 提高链表访问效率 —— 哈希链表

--8.2.1 简单的哈希算法

--8.2.2 算法实现

-8.3 以二进制文件存储链表

--8.3.1 二进制文件的操作方法

--8.3.2 代码讲解

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第八章 非文本数据处理--语法自测

第九章 可配置的程序设计

-9.1 自动售卖程序

--9.1.1 提出问题与初步设计

--9.1.2 细化实现订单处理

--9.1.3 使程序更健壮

-9.2 配制水果信息

--9.2.1 提出问题与设计文件格式

--9.2.2 实现订单处理功能

-9.3 指定界面语言

--9.3.1 提出问题与命令行参数

--9.3.2 实现程序功能

-程设论道

--程设论道

-师生问答

--师生问答

-第九章 可配置的程序设计--语法自测

5.4.7 代码解说——八皇后问题笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。