计算机程序设计实现重排九宫格问题

【摘 要】本文通过解决计算机程序设计，从而实现重排九宫格问题，使我们青少年达到掌握更多的计算机知识，锻炼编程能力。

【关键词】计算机；九宫格；程序

重排九宫格顾名思义就是重新排列九宫图的意思，其玩法是在3×3方格盘上，放有1-8八个数，剩下一格为空，每一空格其周围的数字可移至空格。先设定初始排列数字，然后开始思考如何以最少的移动次数来达到目的。这类小游戏可以锻炼人的逆向思维能力，是青少年非常喜爱的课余活动。

目前，人们已经迈入了网络时代，计算机和互联网已经与我们的日常工作、学习和生活息息相关，我们青少年更加应该掌握更多的计算机知识，尤其学习程序设计语言可以培养我们运用算法来解决实际问题的能力，这种解决问题的方式是计算机所独有的，也只有通过对计算机程序设计语言和程序设计方法的学习才有可能获得这种解决问题的能力。使用计算机程序设计的方式解决实际问题有诸多的好处主要表现在：

（1）程序设计的目标是用某种计算机高级算法语言编写程序实现特定的算法的功能。程序设计要具有强烈的創造意识，为实现预想的功能要不断地设想多种方案，同时又需要具有十分严谨的逻辑推理。因此程序设计是获得创造性修养与获得正确思维方法的极好的科目；

（2）计算机程序设计与数学是紧密相互联系而相辅相成的，它对数学的学习有着极大的促进作用。许多数学问题必须要用计算机才能最终解决问题，反之计算机的编程常常要借助数学的思想与方法才能出色完成任务；

（3）程序设计是学习其他学科的基础，不论是文科还是理科，特别是学习理科学科，计算机是一种必不可少的工具。由于在计算机方面的兴趣，新泰一中的高三学生霍达通过计算机程序设计了一个有效的算法，实现关于九宫格的重排问题。

为了实现重排九宫格的问题，系统在算法设计上使用广度优先搜索算法。广度优先搜索算法是一种图形搜索算法。简单的说，广度优先搜索算法从根节点开始，广度优先搜索算法沿着树的宽度遍历树的节点。

如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表（在搜索算法过程中其邻居节点尚未被检验过的节点会被放置在一个被称为open的容器中，而被检验过的节点则被放置在被称为closed的容器中，简称open-closed表）。

对于九宫格重排的问题，系统使用广度优先搜索算法队列的形式来实现，具体实现的算法步骤如下：

步骤1：把初始的状态节点放入一个队列；

步骤2：如果队列为空，则问题无解，退出。否则，检查队尾的状态是否是目标状态，如果是目标状态，转至步骤5；

步骤3：如果不是目标状态，扩展当前节点，并为每个子节点配置指向父节点的指针，把不是当前节点的先辈的子节点加入到队头；

步骤4：队尾指针指向下一个节点，转至步骤2；

步骤5：当前节点通过其父指针回溯到初始状态，并为每个节点设置其移动的方向，以记录找到的这条路径；

步骤6：根据找到的路径移动九宫格到达目标状态；

系统使用目前最流行的Windows平台应用程序开发环境Visual Studio实现，程序在找到有效路径后，一步一步地移动到目标状态过程中，其中最难处理的部分是如何展示移动的过程。系统使用了一个巧妙的方法，系统在运行过程中记录下每次移动的状态矩阵，这样就不必移动格子，只要修改格子里的数字就可以了。

程序的初始界面如下图1所示，程序分为开始状态和目标状态，开始状态显示的是九宫格初始状态，目标状态显示的是九宫格从开始状态最终要移动到的状态。程序开始运行前，先调整开始状态和目标状态到任意位置，如图2所示。然后点击开始，系统自动从设定的开始状态一步一步移动的设定的目标状态，如图3所示。

在计算机程序实现九宫格重排的过程中，不难发现利用巧妙的算法，计算机能方便快捷得解决人脑看来复杂或耗时的问题。而设计程序的过程不仅充满趣味与挑战，更能一劳永逸得解决一些需要不断重复思考的问题。因此，处于人生充电期的青少年，应该勇敢进入计算机的广阔世界，锻炼编程能力，让计算机成为自己未来求学和工作道路上的良师益友。