问题描述：八数码问题即是找出一条状态路径，使初始状态（start）转换到目标状态（end），一般选取目标状态为：1 2 3 4 5 6 7 8 0（0代表空格）
0 1 2 1 2 3
3 4 5 ——> 4 5 6
6 7 8 7 8 0
下面通过几个问题来对求解策略进行讨论。
（Q1）任意给定初态和终态，是否存在路径（可解性）？
八数码问题的可解性，存在一个判定定理：八数码问题可解当且仅当初态数字（除空格）的逆序数之和与终态的逆序数之和奇偶性一致。详细课参考http://wenku.baidu.com/link?url=PtvqjecMh5AJNaXso2Lq2Yg_VSpyDZpj8-3noewRp0CEs_-NcMZTn61Nb2pwxKkVf1R3o-wC7YKDgUkiUajFoHeni73_wd3OStpTOEKGQoS
（Q2）如何存储状态节点？
采用3*3或者1*9矩阵来存储状态节点，笔者也不例外，因为该存储结构方便计算评价函数值以及打印路径等。但是在此基础上，笔者添加了一个mark域（一个int型）,sizeof(int)=4*8=8*4,即能表示8个十六进制数，则能够标志唯一一个状态，这样两个状态是否相同的判断就从9个int型数据的比较变为1个int型的比较，因此能够节省大量的时间（虽然说，计算标志时也相当于一次矩阵比较，但是却能做到“一劳永逸”）。
（Q3）为什么选择链式存储结构？
与静态存储结构相比，链式存储结构是“量体裁衣”，不会造成空间的浪费；另一方面，对于不同的初态，搜索的深度不知，静态表的长度也不能确定一个合适的值（既不浪费也能够用）；最重要的一点，搜索过程，经常要进行节点的删除，添加，若用静态链表存储必定会浪费大量的时间。
（Q4）搜索方法如何选取？
八数码问题的解空间树属排列树，用于排列树搜索的方法主要有两大类:一类是盲目搜索，如深度优先搜索DFS和广度优先搜索BFS；另一类是启发式搜索，如A*算法。对于八数码问题，深度优先搜索的状态空间搜索树的深度可能很深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。应用此策略很可能得不到解。宽度优先搜索的优势在于当问题有解时，一定能找到解，且能找到最优解。但其搜索时需要保存所有的待扩展结点，这样很容易扩展那些没有用的结点，造成状态的指数增长，甚至"组合爆炸"。这对宽度优先搜索很不利。这两种搜索方法的共同缺点是结点排序杂乱无章，往往在搜索了大量无关结点后才能得到目的结点，只适合于复杂度较低的问题的求解。启发式搜索利用特定问题自身所携带的启发信息在一定程度上避免了盲目搜索的不足。
（Q5）如何选取评价函数？
对于f(n)的考虑最简单的便是比较每个状态与目标状态相比错位的个数。这个启发意味着如果其他条件相同，那么错位的个数最少的状态可能最接近目标状态。然而这个启发没有使用从棋盘格局中可以得到的所有信息，因为它没有把数字必要的移动距离纳入考虑。一个“更好一点”的启发是对错位的牌必须要移动的距离求和，为了达到这个目的，每张牌必须要移动的每个方格算为一个距离单位。本文采用后者。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
/***************构造数据结构******************/
typedef struct Node
{
int a[9]; //棋盘的状态
int mark; //该状态的标志（为比较两状态是否相同节省时间）
int dx; //深度
int fx; //评价函数值
struct Node* parent; //标志父亲节点（为打印路径）
struct Node* prior; //指示前驱
struct Node* next; //方便查表
}Node,*SNode; //棋盘状态节点
typedef struct StateQueue
{
SNode front; //头指针
SNode rear; //尾指针
}StateQueue; //以棋盘状态为节点的状态队列
StateQueue closed,open; //closed 表和 open表
/************相关子函数申明***************/
void copySNode(SNode &t,SNode s);
void initSQueue(StateQueue &Q , SNode s);
void markState(SNode s);
SNode searchSQueue(StateQueue Q,SNode s);
void exSNode(SNode t);
void childSolve(SNode s);
void evaluate(SNode s);
void insertOpen(SNode s);
void eightPuzzle();
void printPath(SNode s);
void openClosed(SNode s);
bool isOK();
SNode start,end;
/***************主函数****************/
int main()
{
printf("/****************八数码游戏**************/\n");
printf("问题描述：从给定初态达到目标状态:\n");
printf("1 2 3 \n");
printf("4 5 6 \n");
printf("7 8 0\n" );
printf("请给出求解路径！\n");
printf("/***************************************/");
printf("\n\n请输入初始状态：\n\n");
int i=0;
start=(SNode)malloc(sizeof(Node));
end=(SNode)malloc(sizeof(Node));
//freopen("in.txt","r",stdin);
for(i=0;i<9;++i)
{
scanf("%d",&start->a[i]);
end->a[i]=i+1;
}
end->a[8]=0;
start->dx=0;
if(!isOK())
{
printf("不能达到目的状态！！！\n");
return 0;
}
evaluate(start);
markState(start);
markState(end);
start->next=NULL;
start->parent=NULL;
start->prior=NULL;
eightPuzzle();
return 0;
}
/**************相关子函数*****************/
/**
*SNode节点的赋值
*/
void copySNode(SNode &t,SNode s)
{
int i;
t=(SNode)malloc(sizeof(Node));
for(i=0;i<9;++i)
{
t->a[i]=s->a[i];
}
t->dx=s->dx;
t->fx=s->fx;
t->mark=s->mark;
t->next=s->next;
t->parent=s->parent;
t->prior=s->prior;
}
/**
*初始化StateQueue
*/
void initSQueue(StateQueue &Q , SNode s)
{
Q.front=s;
Q.rear=s;
}
/**
*为棋盘状态mark赋值
*/
void markState(SNode s)
{
int i,mark=0;
s->mark=0;
for(i=0;i<8;++i)
{
mark=s->a[i];
s->mark+=mark<<(4*(7-i));
}
}
/**
*查StateQueue表，判断s节点是否存在并返回查到节点
*/
SNode searchSQueue(StateQueue Q,SNode s)
{
SNode q=Q.front;
if(!q) return NULL;
do
{
if(q->mark==s->mark)
return q;
q=q->next;
}while(q);
return NULL;
}
/**
*扩展节点s并交由childSolve函数处理子节点
*/
void exSNode(SNode t)
{
int i;
SNode s;
for(i=0;i<9;++i) //寻找空格位置
{
if(!t->a[i]) break;
}
if(i%3) //空格向左移动
{
copySNode(s,t);
s->dx++;
s->parent=t;
s->a[i]=s->a[i-1];
s->a[i-1]=0;
markState(s);
childSolve(s); //处理扩展的子节点
}
if(i%3!=2) //空格向右移动
{
copySNode(s,t);
s->dx++;
s->parent=t;
s->a[i]=s->a[i+1];
s->a[i+1]=0;
markState(s);
childSolve(s); //处理扩展的子节点
}
if(i/3) //空格向上移动
{
copySNode(s,t);
s->dx++;
s->parent=t;
s->a[i]=s->a[i-3];
s->a[i-3]=0;
markState(s);
childSolve(s); //处理扩展的子节点
}
if(i/3!=2) //空格向下移动
{
copySNode(s,t);
s->dx++;
s->parent=t;
s->a[i]=s->a[i+3];
s->a[i+3]=0;
markState(s);
childSolve(s); //处理扩展的子节点
}
}
/**
*处理子节点(即是，判断是否加入open表，插入位置)
*/
void childSolve(SNode s)
{
SNode p;
if(p=searchSQueue(open,s)) //在open表中
{
if(p->dx>s->dx) //若子状态沿着更短的路径
{
s->fx=p->fx-p->dx+s->dx;
s->mark=p->mark;
if(!p->prior) //表头
{
p->next->prior=NULL;
open.front=p->next;
}
else if(!p->next) //表尾
{
p->prior->next=NULL;
open.rear=p->prior;
}
else
{
p->next->prior=p->prior;
p->prior->next=p->next;
}
free(p);
}
else return ; //若子状态路径更长，不加入open表
}
else if(p=searchSQueue(closed,s)) //在closed表中
{
if(p->dx>s->dx) //若子状态沿着更短路径，
{
s->fx=p->fx-p->dx+s->dx;
s->mark=p->mark;
if(!p->prior) //表头
{
p->next->prior=NULL;
closed.front=p->next;
}
else if(!p->next) //表尾
{
p->prior->next=NULL;
closed.rear=p->prior;
}
else
{
p->next->prior=p->prior;
p->prior->next=p->next;
}
free(p);
}
else return ; //否则，不加入open表
}
else //既不在open表，也不在closed表中
{
evaluate(s); //评价该状态
}
insertOpen(s); //把s插入open表中
}
/**
*evaluate评价该状态，即为求fx的值
*/
void evaluate(SNode s)
{
int i,value=0;
s->fx=s->dx;
for(i=0;i<9;++i)
{
if(!s->a[i]) value=8-i;
else value=s->a[i]-i-1;
if(value>0)
{
s->fx+=value;
}
else s->fx-=value;
}
}
/**
*insertOpen插入open表中
*/
void insertOpen(SNode s)
{
SNode p=open.front;
while(p->next&&p->fx<=s->fx)
{
p=p->next;
}
if(p->fx>s->fx)
{
s->prior=p->prior; //更改前驱及后继指针
s->next=p;
if(p->prior) p->prior->next=s;
else open.front=s;
p->prior=s;
}
else
{
p->next=s;
s->prior=p;
s->next=NULL;
open.rear=s;
}
}
/**
*调试程序是用到的辅助函数
void print()
{
SNode p;
p=open.front;
printf("\nopen:\n");
while(p)
{
printf("%.8x\n",p->mark);
p=p->next;
}
p=closed.front;
printf("\nclosed:\n");
while(p)
{
printf("%.8x\n",p->mark);
p=p->next;
}
}
**/
/**
*八数码问题求解策略
*/
void eightPuzzle()
{
initSQueue(open,start);
initSQueue(closed,NULL);
SNode s=open.front;
while(s->mark!=end->mark)
{
exSNode(s);
openClosed(s); //把s从open表移到closed表的队尾
s=open.front;
}
printPath(s);
}
/**
*把s从open表移到closed表的队尾
*/
void openClosed(SNode s)
{
if(!s->prior) //表头
{
s->next->prior=NULL;
open.front=s->next;
}
else if(!s->next) //表尾
{
s->prior->next=NULL;
}
else
{
s->next->prior=s->prior;
s->prior->next=s->next;
}
if(!closed.front)
{
closed.front=s;
closed.rear=s;
s->next=NULL;
s->prior=NULL;
}
else
{
if(!closed.front->next) closed.front->next=s;
closed.rear->next=s;
s->prior=closed.rear;
s->next=NULL;
closed.rear=s;
}
}
/**
*打印出移动路径
*/
void printPath(SNode s)
{
SNode p=s;
int i,j;
p->next=NULL;
while(p->parent)
{
p->parent->next=p;
p=p->parent;
}
while(p)
{
for(i=0;i<3;++i)
{
for(j=i*3;j<3*(i+1);++j)
{
printf("%d ",p->a[j]);
}
printf("\n");
}
printf("\n\n");
p=p->next;
}
}
/**
*判断初始状态能否到达目标状态
*/
bool isOK()
{
int i,j,count=0; //count记录逆序数和
for(i=0;i<9;++i)
{
if(start->a[i])
{
for(j=i+1;j<9;++j)
{
if(start->a[j]&&start->a[j]<start->a[i])
{
count++;
}
}
}
}
if(!(count%2)) return true;
else return false ;
}
不足之处：1）评价函数可以更加合理，提高搜索效率；2）本质是找出一系列状态，从start->end，end状态也可以随意变化。
注：改进方法还是比较简单的，希望看到此博文的人可以自行练习。