八数码问题实验报告
一、 实验要求：
九宫重排问题: 在 3×3 的井子九宫格棋盘上摆有 8 个牌，分别标有 1-8 个数
码。棋盘上尚有一个空格，允许其周围的将牌向空格移动。这个通过移动将牌
就可以变换将牌布局。现给定如下两种布局，一种为初始状态，一种为目标状
态，问如何移动将牌，以将初始状态变换为目标状态？
二、 实验思路：
A*算法
取 g(n)=d(n)，h(n)=w(n)，其中 w(n)表示以目标为基准，结点 n 的状态中不在位
将牌的个数。由于从结点 n 转换成目标结点至少需要 w(n)步，所以对任意 n，
恒有 w(n) ≤h*(n)。
三、 实验代码：
#include<iostream>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
#define size 3
long total;
typedef char board[size][size];
board target = {1,2,3,8,0,4,7,6,5}; // 目标状态
class Node{
public:
board data; //存放状态
Node *parent; //存放父节点地址
Node *child[4]; //存放子节点地址,最多个
Node *next;
int f,h,g,how; //how中记录了其父节点如何移动生成该节点
Node();
int geth();
};
