《算法程序范例集》（11）九宫问题.docVIP

九宫问题

?

题目叙述：九宫问题又称“八数码问题”，是说在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，从某种初始状态开始，对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态变换至目标状态。求其最少步数。

?

?

/*****************************/

/*EIGHTDIGITPROBLEM*/

/*唐国峰2012年4月23日*/

/*****************************/

?

//预编译命令

#includeiostream

#includestdlib.h

usingnamespacestd;

?

//棋盘大小

#definesize3

?

//定义二维数组来存储数据表示某一个特定状态

typedefintstatus[size][size];

?

//定义状态图中的节点数据结构，即节点的状态信息等

typedefstructNode

{

statusdata; //节点所存储的状态

structNode*parent; //指向节点的父亲节点

structSpringLink*child; //指向节点的后继节点

structNode*next; //指向链表的后一个节点

intf_value; //由初始状态经由当前节点至目标状态的总耗散值

intg_value; //由初始状态经到当前节点实际耗散值

inth_value; //由当前节点到目标状态的预计耗散值

}NNode,*PNode;

?

?

//定义表述指向当前节点的扩展节点的链表

typedefstructSpringLink

{

structNode*pointData; //指向节点的指针

structSpringLink*next; //指向当前节点的其他扩展节点

}SPLink,*PSPLink;

?

//声明OPEN表和CLOSED表

PNodeopen;

PNodeclosed;

?

//计算棋盘状态的逆序数

intInverseNumber(statusa)

{

inti,j,sum=0;

intdata_chang[size*size]={0};

?

//将二维数组转换成一维数组，以方便求逆序数

for(i=0;isize;i++)

{

for(j=0;jsize;j++)

{

data_chang[i*size+j]=a[i][j];

}

}

?

?

//计算序列中除零外的逆序数

for(i=0;i=size*size;i++)

{

if(data_chang[i]!=0)

{

//要比较多少次,从最后一个元素开始比较

for(j=i;j=0;j--)

{

//当后一个数比前一个数小时

if(data_chang[i]data_chang[j])

{

sum++;

}

}

}

}

returnsum;

}

?

//判断是否存在解决方案

boolhasSolution(statusstartStatus,statustargetStatus)

{

intstartInverseNumber=InverseNumber(startStatus);

inttatgetInverseNumber=InverseNumber(targetStatus);

?

//判断初始状态和目标状态除零外的序列逆序数奇偶性，相同则可求值，不同则不可求

if((startInverseNumber%2)!=(tatgetInverseNumber%2))

{

returnfalse;

}

else

{

returntrue;

}

}

?

?

//初始化一个空链表

voidinitLink(PNodeHead)

{

Head=(PNode)malloc(sizeof(NNode));

Head-next=NULL;

}

?

?

//判断链表是否为空

boolisEmpty(PNodeHead)

{

if(Head-next==NULL)

{

returntrue;

}

else

{

returnfalse;

}

}

?

?

//从链表中拿出一个数据

voidpopNode(PNodeHead,PNodeFNode)

{

if(isEmpty(Head))

{

F