1 

八数码问题算法

文献综述报告

摘要：

随着计算机和网络的大范围普及，

电脑游戏也普遍存在于人们的生活

中，但是大部分的人都只是看重游戏的娱乐价值（启发思维，培养观察能力、耐

心等）

，而不在乎其本质，比如说它有着什么样的数据结构，它的核心算法是什

么等等这些问题。

本文就目前一个很经典的算法问题

——

八数码问题来分析其核

心的算法，并且借助前人得出的研究，进一步分析和设计算法。

关键词：

八数码；拼图游戏；广度优先搜索；深度优先搜索；

A*

搜索

1

引言

从古至今，

“游戏”这个词对于人们来说都不陌生，从古代的斗禽，蹴鞠等

到现在的一系列的电脑游戏。尤其是如今的电脑游戏，不胜其数，种类繁多，不

亦乐乎，

拼图游戏就是其中的一种。

所谓的拼图游戏就是把一副完整的图片通过

规则的或者不规则的切割后打乱成零片，

玩家只需把零片拼凑回原形即可。

在这

个过程中，要发生无数次的状态改变，在电脑上也如此。不同的是，电脑上的拼

图游戏需要一个“看不见”的存储空间来存储这一个个不同的状态。

这就必须涉

及到数据的存贮方式。尤其是算法，

它是拼图游戏的核心，

它决定了计算机怎样

解决这个问题，同时还影响着这个游戏程序的存储方式。但是，

并不是一个能玩

的游戏都具有理想的算法和数据结构。

因此，

对一个游戏的算法进行分析优化并

设计出一个理想的算法显得更加重要。此拼图游戏是建立在一个

3*3 

的方格棋

盘上，把棋盘上的打散的八块图片分别用数字

1-8

标识，棋盘上空的那块标识为

0

，那么拼图游戏就可以转化成我们算法中极为极为经典的八数码问题。

2 

八数码问题的研究现状

2.1 

八数码问题的概念