八数码问题实验报告
学号：SY1003528
一、 实验要求：
八数码问题是指这样一种游戏：将分别标有数字 1，2，3，…，8 的八块正方形数码牌
任意地放在一块 3×3 的数码盘上。放牌时要求不能重叠。于是，在 3×3 的数码盘上出现
了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放
的数码盘逐步摆成某种特殊的排列。
二.状态表示
用一个二维数组a[3][3]表示数码盘上的某种布局，a[i][j]表示数码盘上第（i+1）行第
（j+1）列的数码牌，空格则用零来表示，为了编程方便用结构体jiedian表示搜索中生成
的每个结点，存储结构采用的是单链表，形成一个类似线性表的数据结构，结构体jiedian
中成员C[3][3]表示数码盘上数码牌的某种状态，成员quanzhi表示A*算法中针对C[3][3]计
算出的w(n)，成员parent表示该结点的父结点，成员next表示在链表存储结构中该
结点的下一个节点，成员layer表示该结点所处的层数。
三．编程规则
空格周围的棋子可以向空格移动，换种角度看，也就是空格可以向上下左右四个方
向移动，假设空格所处的位置为（a,b）,则有四条规则：
（1）如果a-1>=0,则空格可以向上移动，数码牌的布局改变如下c[a][b]= c[a-1][b]，
c[a-1][b]=0;
（2）如果b-1>=0,则空格可以向左移动，数码牌的布局改变如下c[a][b]= c[a][b-1]，
c[a][b-1]=0;
（3）如果a+1<=2,则空格可以向下移动，数码牌的布局改变如下c[a][b]= c[a+1][b]，
c[a+1][b]=0;
（4）如果b+1<=2,则空格可以向右移动，数码牌的布局改变如下c[a][b]= c[a][b+1]，
c[a][b+1]=0;
四．A*搜索算法
取 g(n)=d(n)，h(n)=w(n)，其中 w(n)表示以目标为基准，结点 n 的状态中每
一个数码牌与其目标位置之间的距离（不考虑夹在其间的数码牌）的总和，由于
