手把手教你怎么实现java九宫格自动拼图

手把手教你怎么实现九宫格自动拼图

在上一篇推文中我们带大家基本了解了近几年随着深度学习的发展，人工智能可以干很多的事：人脸识别，自动驾驶，风格迁移等等。那么有一个问题出现了，人工智能的发展，一开始就过渡到那么深奥的“机器学习”，“神经网络”吗？

肯定不是的。

现在大热的人工智能实现方法，我们称之为模拟法，它不仅要看效果，还要求实现方法也和人类或生物机体所用的方法相同或相类似。大名鼎鼎的遗传算法和人工神经网络就是这个类型。

而在机器学 习概念还没提出之前，人工智能是采用传统的编程技术，使系统呈现智能的效果，而不考虑所用方法是否与人或动物机体所用的方法相同。这种方法叫工程学方法。它已在一些领域内作出了成果，如文字识别、电脑下棋等。今天要教大家实现的，就是用传统的办法，用java编程和数据结构，来实现打乱的九宫格自动还原功能。

本推文不需要阅读者拥有Java编程基础，讲解的是实现的思路（当然在文末，会提供源码给想亲自编译的小伙伴玩一玩~）

构思游戏框架

界面

界面是拼图游戏的雏形实现，九个按钮，按钮上的图片显示出完整的图片。前八个是完整的图形，最后一个为空白图。再在上边添加控制按钮。大概就长这样：

板块怎么实现移动

移动版块，我们更换按钮上的图片。按钮类上我们设置有两个属性,a[]表示按钮的位置，b[]表示按钮上图片的编号， 空白快图片编号为8标记，点击按钮之后，点击事件得到点击的块数在哪（1-9）,if -else判断相邻是否为标记的空白快。虽然代码长但是方法简单。

判断胜利

在上一段中我们提到有两个按钮属性 a,b来记录信息,在未打乱之前，ab对应，值相等。那么我们在每一次的鼠标点击拼图按钮之后进行一次判断，是否每一个a[i]都对应着自身b[i]值，如果是的话就给出胜利信号。

打乱拼图

在完成了上面的设计之后，我们已经可以开始玩耍了，但是这是游戏，得有打乱的功能。怎么实现呢。若随机置入图片，会存在图片移动次数的奇偶性问题，有一半的几率是没有解法的。采用此法，我不得不再写一个判断随机打乱之后是否有解的算法。这样会非常麻烦，并且与我之前写的版块内容不兼容。由于我们写好了移动算法，所以我们随机移动可移动的版块若干次，次数足够多的情况下便可以做到打乱拼图的效果，并且保证此法必然有解。

重头戏：实现自动还原

广度搜索算法

广度优先算法（Breadth-First Search）简称BFS，是一种图形搜索演算法，在程序员必学的经典--《数据结构》中占有很重要的位置。那它到底是什么呢？

有一个有向图如图a：

我们的目标是从v1开始，先下寻到，直到找到v8这个目标点的最短路径。人眼很容易看出来，但是机器怎么知道呢？于是就引出了广度搜索算法。

1、访问顶点vi ；

2、访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ；

3、依次从这些邻接点（在步骤②中访问的顶点）出发，访问它们的所有未被访问的邻接点; 依此类推，直到找到v8.；

这样的算法优点在于它的完全性。无论图形的种类如何，只要目标存在，则BFS一定会找到。然而缺点也在于此，若目标不存在，且图为无限大，则BFS将不会结束，若图形太过庞大，将花费巨大的时间。

拼图怎么引入广度搜索算法

现在我们将来初始打乱状态，目标状态抽象表示如下：

运用广度搜索的思想，我们可以让白块模拟走一走，判断是不是已经赢了，不是的话，我们就回去，再模拟同一层次的走法。根据白块的位置不同，可以走2，3，4中情况。比如在中间可以模拟走上下左右。同层走完之后都没有找到目标点，记录下我走了一步了，再走下一层。如此循环，最终找到目标状态。显示出走了多少步，这就是最佳最短的还原路径了。

引入广度搜索之后提示出下棋步骤

算出步数之后，我们再找到白块，模拟有效移动一次，再判断这次的局面，相比较之前最短步数是否减1。若是，则为最佳走法，若不是，则还原，再模拟一次另一个走法。其中必然有正解。伪代码如下：

数组c记录移动之前的局面；

while (true) {

while(不是有效白块移动) {

移动白块

}

获得表示当前局面的字符串；

计算最短路径d；

if(最短路径d相比较之前最短步数d0减1)

{

用记录数组c还原移动之前局面；

输出这一步移动（找到了最佳的走法了）

break; }

if(模拟之前局面最短步数d0==1)

{

用记录数组c还原移动之前局面；

break;

}else

{

用记录数组c还原移动之前局面；

}

}

找到最佳走法之后，我们让程序移动白块就可以了。

运行结果

“

我们是图灵智能创新团队，同时也是广东海洋大学第一个人工智能创新团队，我们团队的主要方向有：计算机视觉和自然语言处理。本公众号主要面向对人工智能感兴趣的读者，如果想了解更多，欢迎关注我们！

”

—END—