当前课程知识点:程序设计基础 > 第五章 分治思想与递归 > 5.4 分书与八皇后 > 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.2 买菜问题
-1.3 数学运算
-1.4 补充说明
-1.5 总结
--1.5 总结
-程设论道
--程设论道
-师生问答
-第一章 编程初步--语法自测
-2.1 关于超级计算器的几点思考
-2.2 电子秤模拟 — 背景介绍及需求分析
-2.3 电子秤模拟 — 代码实现
-2.4 变量定义与变量类型
-2.5 猜数游戏与数据表示
-2.6 关于变量的讨论
--公告
-2.7 变量体现的计算思维
-程设论道
--程设论道
-师生问答
--师生问答
-第二章 变量与代数思维--语法自测
-3.1 谁做的好事——语义表示
-3.2 谁做的好事——真假检查
-3.3 谁做的好事——循环枚举
-3.4 谁是嫌疑犯——多重循环枚举
-3.5 谁是嫌疑犯——破案线索表示
-3.6 谁是嫌疑犯——用二进制枚举
-程设论道
--程设论道一
--程设论道二
--程设论道三
-师生问答
-第三章 逻辑推理与枚举解题--语法自测
-4.1 插花游戏
-4.2 筛法
-4.3 线性查找
-4.4 折半查找
--4.4.1 提问
-4.5 排序问题
-4.6 总结
--4.6.1 总结
-程设论道
--程设论道二:筛法
-师生问答
-第四章 筛法与查找--语法自测
-5.1 阶乘
-5.2 排序
-5.3 矩阵填充
-5.4 分书与八皇后
-5.5 青蛙过河
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答一
--师生问答二
-第五章 分治思想与递归--语法自测
-6.1 兔子数列问题
-6.2 分鱼问题
-6.3 橱窗的插花问题
-6.4 最长公共子序列问题
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第六章 递推与动态规划--语法自测
-7.1 统计记录总数
-7.2 统计活跃用户数
-7.3 统计在线时长
--7.3.2 结构
-7.4 总结
--7.4.1 总结
-程设论道
--程设论道
-师生问答
--师生问答
-第七章 文本数据处理--语法自测
-8.1 将数据组织成链表
-8.2 提高链表访问效率 —— 哈希链表
-8.3 以二进制文件存储链表
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第八章 非文本数据处理--语法自测
-9.1 自动售卖程序
-9.2 配制水果信息
-9.3 指定界面语言
-程设论道
--程设论道
-师生问答
--师生问答
-第九章 可配置的程序设计--语法自测