八数码实验报告
姓名： 凌伟杰 学号： 03122997
学校： 上海大学 学院： 计算机学院
关键字：八数码、人工智能、
A*
算法、双向广搜、启发式函数
摘要：
九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。问题是在 3 × 3 方格盘上，
放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目
标位置，要求通过一系列的数码移动，将初始位置转化为目标位置 。本文介绍用普通搜索方法、双
向广度搜索和启发式搜索如何缩短寻找路径的时间，以及各算法间的利与弊。
目录：
1. 问题简介
2. 问题分析
3. 算法设计
4. 程序实现
5. 相关链接
一、 问题简介：
所谓八数码问题是指这样一种游戏：将分别标有数字 1 ， 2 ， 3 ， … ， 8 的八块正方形数码牌任 意
地放在一块 3 × 3 的数码盘上。放牌时要求不能重叠。于是，在 3 × 3 的数码盘上出现了一个空格。
现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某
种特殊的排列。如下图表示了一个具体的八数码问题求解。
二、 问题分析：
首先， 八数码问题包括一个初始状态 (START) 和 目标状态 (END) ， 所谓解八数码问题就是在 两
个状态间寻找一系列可过渡状态 （ START>STATE1>STATE2>...>END ） 。 这个状态是否存在就是 我
们要解决的第一个问题：
Q1 ：每一个状态及每一次操作的表示方法？
有许多表示方法，比如一个 3*3 的八数码盘可以压缩成一个 int 值表示，但不适用于 15 puzzle
或大于 8 的 puzzle 问题。如果对空间要求很高，应该还可以再压缩。本文采用一个 int 表示的方法 。
表示方法如下：由于 int 的表示范围大于 1e9 ，所以我们取一个 int 的低 9 位，为了方便寻找空
格的位置， int 的个位我们用来放空格的位置（ 19 ） 。而前 8 位，按照行从上到下，列从左到右的顺
序依次记录对应位置上的数字。例如：
