图像思维解释八皇后算法及其拓展问题

叶均隆　叶均明　余伟红

摘 要：从多年教学中，笔者发现计算机专业的学生大多数在学习中运用的是数学逻辑思维，尤其在竞赛中有获奖的同学，如：蓝桥杯获奖的。这些优秀同学利用逻辑推理思维去理解某些困难算法，如：八皇后、回溯、广搜、深搜等算法，表现得非常困难，耗费很多时间仍然不得要领。如果通过图像思维帮助其理解困难的算法问题，往往事半功倍。因此，文章研究了图像思维解释八皇后算法及其拓展问题。

关键词：图像思维；视觉化思维；蓝桥杯；八皇后；教学设计；算法

运用图像思维解释八皇后算法问题是笔者立项以来第一个运用案例。文章适合有一定的C语言基础的，想了解图像思维的或递归算法能力薄弱但想加深理解的读者。软件技术和计算机应用技术专业是笔者所在院系人数最多的两个专业，但在近年来每次参加蓝桥杯省赛获一等奖人数徘徊在1～2人。蓝桥杯竞赛的难题的解决主要是能否灵活运用适合的算法。通常题目越难，程序算法越复杂。从参赛的情况看，学生在软件技术中的算法把握得还不够。机器学习应用、自然语言处理、智能无人机、计算机视觉与图像、人工智能、大数据、操作系统开发、智能导航等是国家重点发展核心领域，而这些领域的基础都是靠好的算法。算法是软件的灵魂，得益于好的算法会给软件带来的往往都是质的变化，性能都是呈指数倍提高的。如何培养学生程序算法设计能力，笔者提出新思路—尝试运用视觉图像思维。

1 视觉图像思维介绍

视觉图像思维自从人类诞生就产生了，在没有发明文字前，人们用石器在石头、木头等物体上刻画图案用来表达事件、物体、动作等，人们几乎不需要怎样学习都能理解其意义。随着社会的发展，原来的图案慢慢变成规则的符号，失去形象的效果，思维方式也慢慢改变。视觉图像思维是通过摄影般逼真的具体图像来思考，视觉化思考的具体程度因人而异。一般的视觉思考者只能想象静止的图像。这些图像的范围包括，从具体地点的图像，到更模糊的概念图像。运用图像思维的好处有：丰富的信息量、具体且形象、准确、推理方便、协助记忆、协助整理思路等。

2 以经典算法八皇后问题为例

棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法[1]。运用计算机求解8个皇后问题，笔者将问题简单化，由于运算原理相同，先求解四皇后问题，那么八皇后问题就迎刃而解。四皇后问题可再分两部分处理，第一部分是：编写解决同一行、同一列或同一斜线上判断函数（函数返回“1”代表可此位置可放置棋子）。第二部分是：編写递归函数检测所有摆放情况，并算出其中符合要求摆放情况。笔者多年培训蓝桥杯的参赛者发现，第一部分的函数编写问题不大，在第二部分的算法里，学生能完全理解原理较少。通过笔者多年的教学经验运用图像分析，学生的学习效果较好，如图1所示，程序按先根遍历执行，每个棋盘旁边的数字为计算机执行的顺序。

如果读者是第一次接触这个四皇后问题，运用图像思维入手，读者只需观察图1所示的所有信息变化规律入手，不需阅读其他文字说明，就很容易找出编写递归函数实现的思路。序号2，19，32，42就是表格逐列循环（四皇后循环4次，八皇后循环8次如此类推）。在序号2下一层又同样执行逐列循环（序号3，4，5，10）。序号3，4因为不符合条件停止搜索，不会放置皇后，而在第二层的序号5（即检测到放置在此位置是安全的，放置第二个皇后）下一层又同样执行逐列循环（序号6，7，8，9）。每个序号的下层都会进行同样的检索，直至4个皇后放置完毕，同时所处的位置安全即是所求的解，具体算法如图2所示。这里还需注意一点，每次放置棋子后往后执行需要回溯，例如：细心的读者会发现，序号5完成一次递归函数调用会先清掉当前位置的棋子再到序号10位置运行，具体实现如图2第11行所示。

3 八皇后算法问题拓展

如果棋盘大小及皇后的个数可任意设置，程序怎么求解有多少种摆法。这个问题可以转化为特定问题的解，如：在3×4的棋盘放2个皇后，有多少种摆法。通过上面规则（4个皇后在4×4的棋盘）作进一步图形转换（2个皇后在3×4的棋盘），如图3所示。转换成对应的状态后，观察棋盘状态执行顺序，如图4所示，在当前函数结束时再次递归调用往下逐列循环探索，其他棋盘状态同理不一一绘制（下同）。因此，从图4的图形变化推理，笔者找到函数递归调用的位置和要求—放置在函数体的最后，函数参数传递变化还是像原来那样对行号的值加一处理（算法在图2的伪代码基础修改），但是程序不能无限往下探索，从图4的棋盘状态可得行号最大是3，也就是需要增加递归结束条件：行号累加后不能超过3。继续观察图4的变化可知，还需增加检测放置皇后的数量的变量：count= count﹢1，达到要求的数量输出并返回，放完后为了不影响后面的探索，需对这变量回溯：count= count-1。

4 结语

笔者最初编写八皇后算法时，运用常用的数学逻辑编程思维，尚且能解决，但到了任意皇后及其拓展问题，感觉程序执行的方向性难以把握，各变量的数值变化难以推理。通过转变思路，使用作图、图形转换、辅助线、图形推理时恍然大悟，使复杂的事情变得简单化了；感觉能看到程序运行全过程，并能捕捉到某一时刻的变量的变化，有点像在做建筑设计或机械设计。笔者抛砖引玉，引起大家去摸索图像思维在教研中的作用，促进技能人才的培养和就业，同时提出解决问题的另一种思路。

[参考文献]

[1]严蔚敏，吴伟民.数据结构C语言版[M].北京：清华大学出版社，2007.