Scratch 编程解《迷人的数学》中谜题164——八皇后问题

一、八皇后问题——1848年

与棋类游戏中棋子摆放相关的问题，几百年来一直让谜题专家乐此不疲。

你能在棋盘上摆放八个“皇后”棋子，使得任何一个“皇后”棋子都不会被另一个“皇后”棋子“吃掉”吗？记住，“皇后”棋子可以按横线、竖线线或对角线方向移动到棋盘上的任何空位。

这个问题是马克斯·贝策尔（Max Bezzel）首先提出来的，这个问题曾被视为消遣数学中的一颗“珍珠”。

这个问题有十二种解答方法。你能想到多少种方法呢？当n取5到7时，你至少能找到一种解答这个问题的方法吗？

二、结论：一般来说，这个问题涉及另一个问题：已知一个n阶的正方形棋 盘，你可以在上面放置多少个“皇后”棋子，才能让每一个棋子都无法 去“攻击”另一个棋子呢？类似的问题还有：要在游戏盘上放置多少个棋子，才能让两个棋子不处在同一排、同一列或同一对角线上呢？对于全部尺寸的棋盘来说，只有12种基本的方法（不将镜像或旋转视为不同的解答方法）。这个问题也可以作为两个选手间的竞赛游戏。

《迷人的数学》书中的结果示意图

三、Scratch编程解八皇后问题

（一）算法分析:1.由于八皇后问题所有可能的排法共8^8=16777216种，数目庞大，如果用穷举法，将显得力不从心了。故使用一种叫做“回溯”的算法策略。就是不断试错，遇到不合规，就回退到上一步重新选择。这样就可以及早丢弃很多种无用的排法。这个丢弃的过程也叫剪枝。

2.逐行检测可以用递归的策略，因此也用到像递归画分形几何图时，保存位置和恢复位置那样的压栈保护和弹出的操作，只不过本例中只需保护列号即可。

3.由于皇后的造型一样，可以使用画笔的图章或者角色克隆，由于要显示几组结果，使用克隆更好。

4.两个位置在同一斜线的判别，用行坐标差绝对值=列坐标差绝对值来实现，如下示意图：

（二）编程实现

1.画8×8方格棋盘的程序，尽可能把屏幕高度用完，可用一个单独的角色完成：

2.合规检测的程序，也可以用一个单独的角色完成：

检测第i行的位置是否合规：

递归逐行检测的子程序：

检测主程序，先初始化基本结构，包括建立两个列表，6个变量，再从第二行开始，检测是否合规：

3.根据检测结果，设置合规的八皇后的程序，也可以用一个单独的角色克隆完成：

（三）符合条件的八皇后：

前面共48个不同排列后两个是前46个中某个的对称排列。把对称的算作不同的话，共有92种八皇后排列，把各个方向上的对称或旋转的算作同一种基本类型，则共有12种基本解。

四、拓展：你能编程解决九皇后、十皇后谜题吗？

九皇后谜题结果之一的截图