|
Scratch项目的负责人凯伦·布雷南曾说过：“我们的目的不是要创建电脑程序编写大军，而是帮助电脑使用者表达自己”。Scratch 作为适合青少年使用的图形化编程语言，含有丰富的数学处理指令，可以将复杂的公式通过程序代码表达出来，可以将抽象的问题转化为编程思维。 今天，我们将以Scratch图形化语言为平台，推出计算机与编程之基础系列文章，结合数学与算法的编程实践，来加强计算机基础素养，拓展编程思维，提升创新和解决问题的能力，为学习和构建复杂程序打好基础。 【编程与算法基础023】八皇后问题与回溯算法
今天我们来分享：回溯算法及依据回溯算法的八皇后问题。
一、回溯算法 回溯算法是一种系统性的搜索算法，属于暴力穷举法的改进版本，通过"试错"的思想来寻找问题的解。
其算法特点是"走不通就退回再走"，采用深度优先搜索策略遍历各个解，在搜索过程中遇到不满足约束条件的情况时，立即回溯，避免无效搜索。
回溯法有"通用解题法"的美称，特别适用于解决组合问题、约束满足问题以及优化问题等。
回溯算法的求解过程，实际上类似一个决策树的遍历过程，其框架包含三个关键要素： 路径：当前已经做出的选择； 选择列表：当前可以做出的选择（探索）； 结束条件：也就是到达决策树底层，无法再做选择的条件。
回溯和递归没有太多本质上的区别，只不过它采用一种试错的思想，尝试分步去解决一个问题。就是所谓的分治 + 试错 = 回溯。 八皇后问题就是回溯算法中最典型的应用场景。
二、八皇后问题
八皇后是个古老而著名的问题，由国际西洋棋棋手马克斯·贝瑟尔于1848年提出，详细问题是这样的：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？如下图，为八皇后问题的一个解。
八皇后问题，我们同样可以使用Scratch，使用递归的方法来求解，即定义一个大小为8的列表，列表的序号表示行，列表的内容表示列。具体的解决思路是： 1、定义列表，并初始化0； 2、从第一行开始，遍历每一列，尝试将皇后放在当前位置； 3、检查当前位置是否与已放置的皇后冲突，即检查与已放置的皇后在同一列、同一对角线上是否有冲突； 4、如果当前位置和已放置的皇后没有冲突，则将皇后放在当前位置，并标记该位置； 5、递归调用下一行，继续放置下一个皇后； 6、如果无法放置下一个皇后，则回溯到上一行，重新尝试在下一列放置皇后； 7、当所有皇后都放置在棋盘上时，得到一个解，将该解保存下来； 8、继续尝试在下一列放置皇后，重复步骤3-7，直到找到所有解。
然而，如何减少递归的次数？在八个皇后的问题中，不必要所有的格子都一一检查，例如若某列检查过，利用分支修剪法该列的其它格子就不用再检查了。 【小结】 八皇后问题是回溯算法最著名的应用，解题的原则是：有冲突解决冲突，没有冲突往前走，无路可走往回退，走到最后便是答案。 八皇后问题可推广为N皇后问题，适用于N×N棋盘。数学上已证明N皇后问题在N≥4时必有解，当N=8时解数为92，即：八皇后问题最终有92个不同放置方法。 注：若考虑棋盘的对称性（旋转和镜像），92种解可以归并为12组本质不同的独立解。具体包括： 基本解：12种 通过90°旋转：12×3=36种 通过镜像反射：12×4=48种
减去重复计算后总计92种 这意味着所有解都可以通过这12个基本解经过旋转或镜像变换得到。 |
