参考资料：

http://blog.csdn.net/ray58750034/archive/2006/02/15/599897.aspx
http://flyingviolin.blogchina.com/flyingviolin/3158588.html

///////////////////////////////////////
// 九??算法；
//////////////////////////////////////

#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define LINE_MAX 4
#define ROW_MAX 4

//////////////////////////////////
//// the function defination
//////////////////////////////////
//int curr_line, curr_row;

//int aim[LINE_MAX][ROW_MAX]={{1,2,3},{8,0,4},{7,6,5}};
//int init_array[LINE_MAX][ROW_MAX]={{1,0,3},{8,2,4},{7,6,5}};

//int aim[LINE_MAX][ROW_MAX]={{1,2,3},{4,5,6},{7,8,0}};
//int init_array[LINE_MAX][ROW_MAX]={{2,0,3},{1,8,5},{4,7,6}};
//int init_array[LINE_MAX][ROW_MAX]={{4,3,2},{1,0,5},{6,7,8}};
//int init_array[LINE_MAX][ROW_MAX]={{8,3,5},{1,2,7},{4,6,0}};

int aim[LINE_MAX][ROW_MAX]={{1,2,3,4},{12,13,14,5},{11,0,15,6},{10,9,8,7}};
int init_array[LINE_MAX][ROW_MAX]={{1,2,3,4},{12,13,14,5},{11,15,0,6},{10,9,8,7}};

struct Node{
int flag;
int curr_line, curr_row;
int status[LINE_MAX][ROW_MAX];
struct Node* next;
struct Node* parent;
struct Node* child;
}*head;
/*
const int LINE_MAX = 3;
const int ROW_MAX = 3;
*/
void create(int [][ROW_MAX]);
void show(int [][ROW_MAX]);
void set_value(int [][ROW_MAX]);
void aim_get();
void target(struct Node *head);
int modify(int [][ROW_MAX]);
void switch_up(struct Node* tnode);
void switch_down(struct Node* tnode);
void switch_left(struct Node* tnode);
void switch_right(struct Node* tnode);
int try_up(struct Node *tnode);
int try_down(struct Node *tnode);
int try_left(struct Node *tnode);
int try_right(struct Node *tnode);
void sort(int a[], int b[]);
void copy(int src[LINE_MAX][ROW_MAX], int dest[LINE_MAX][ROW_MAX]);
int judge_array(int array[][ROW_MAX]);
int ExistOrNot(struct Node *head, struct Node * a);
///////////////////////////////////////
////// the main function body ////
////////////////////////////////////////

main()
{
int cDiagram[LINE_MAX][ROW_MAX];
srand(time(NULL));

create(cDiagram); /////// creat the new array ,set the value are 10;
set_value(cDiagram);
aim_get();

return 0;
}

///////////////////////////////////////
/// 建立一个3*3数?，初?都??10；//
//////////////////////////////////////

void create(int array[][ROW_MAX])
{
int line;
int row;
printf("nn***********************************nn");
printf("九??算法???程nn");
printf("***********************************nn");
head = (struct Node*) malloc(sizeof(struct Node));
head->parent = head;
head->next = NULL;
head->child = NULL;
for(line=0;line<LINE_MAX;line++)
{
for(row=0;row<ROW_MAX;row++)
{
array[line][row]=10;
}
}
}

/////////////////////////////////////////
/// ?示数?状? ////
////////////////////////////////////////

void show(int array[][ROW_MAX])
{
int i,j ;
for(i=0;i<LINE_MAX;i++)
{
for(j=0;j<ROW_MAX;j++)
{
printf("%3d",array[i][j]);

}
printf("nn");
}

}

///////////////////////////////
/// ?生数?的初始状? ///////
///////////////////////////////

void set_value(int array[][ROW_MAX])
{
int i,j;
copy(init_array, array);
copy(init_array, head->status);
for (i=0; i<LINE_MAX; i++) {
for (j=0; j<ROW_MAX; j++) {
if (array[i][j] == 0) {
head->curr_line=i;
head->curr_row=j;
}
}
}
printf(" Begin with this!!n");
show(array);

}

////////////////////////////////////////////////////////
//// judge the initial array get the target or no ! ///
//////////////////////////////////////////////////////////

void aim_get()
{

int judge=0;

judge=judge_array(head->status);
while(judge!=0)
{
int a[4],b[4];
int i,length=4;
struct Node* tNode=NULL;
struct Node* tHead=head;

a[0]=try_up(head);
a[1]=try_down(head);
a[2]=try_left(head);
a[3]=try_right(head);
sort(a,b);

for(i=0;i<length;i++) {
// if (a[b[i]] <= judge) {
tNode=(struct Node*)malloc(sizeof(struct Node));
if (tNode == NULL) {
printf("memory is not enough!");
exit(1);
}
tNode->parent=head;
tNode->flag=b[i];
tNode->next=tHead;
tNode->child=NULL;
//whether it has been passed or not
copy(head->status, tNode->status);
tNode->curr_line=head->curr_line;
tNode->curr_row=head->curr_row;
switch (tNode->flag){
case 0: switch_up(tNode);
break;
case 1: switch_down(tNode);
break;
case 2: switch_left(tNode);
break;
case 3: switch_right(tNode);
break;
}
if (ExistOrNot(head, tNode)) {
free(tNode);
continue;
}

tHead=tNode;
// }
}
if (head != tHead) {
//extend
head->child=tHead;
head=tHead;
} else {
//lookup back
while(head->parent!=head) {
tNode=head;
if (tNode->next != tNode->parent) {
head=tNode->next;
tNode->parent->child=head;
free(tNode);
break;
}
head=tNode->next;
tNode->parent->child=NULL;
free(tNode);
}
}

//modified Array when new Node has been added or recover to the parent
if (head->next!=NULL) {
judge = judge_array(head->status);
} else {
break;
}

} //end while

target(head);

}

/////////////////////////////////////
/////// the target diagram //////////
/////////////////////////////////////

void target(struct Node *head)
{
struct Node* ptr = head;
while(ptr->parent != ptr) {
ptr=ptr->parent;
}
while(ptr!=NULL) {
printf("nn ****** the diagram is : ****** n");
show(ptr->status);
ptr=ptr->child;
}
}
/*
*
*/
int judge_array(int array[][ROW_MAX]) {
int line;
int row;
int judge=0;
for(line=0;line<LINE_MAX;line++)
{
for(row=0;row<ROW_MAX;row++)
{
if(array[line][row]!=aim[line][row])
{
judge++;
}
}
}
return judge;
}

void switch_up(struct Node *tnode) {
int temp;
int curr_line=tnode->curr_line;
int curr_row=tnode->curr_row;
if (curr_line > 0) {
temp = tnode->status[curr_line][curr_row];
tnode->status[curr_line][curr_row] = tnode->status[curr_line - 1][curr_row];
tnode->status[curr_line - 1][curr_row] = temp;
tnode->curr_line = curr_line-1;
}
}
void switch_down(struct Node *tnode) {
int temp;
int curr_line=tnode->curr_line;
int curr_row=tnode->curr_row;
if (curr_line < LINE_MAX - 1) {
temp = tnode->status[curr_line][curr_row];
tnode->status[curr_line][curr_row] = tnode->status[curr_line + 1][curr_row];
tnode->status[curr_line + 1][curr_row] = temp;
tnode->curr_line = curr_line + 1;
}

}
void switch_left(struct Node *tnode) {
int temp;
int curr_line=tnode->curr_line;
int curr_row=tnode->curr_row;
if (curr_row > 0) {
temp = tnode->status[curr_line][curr_row];
tnode->status[curr_line][curr_row] = tnode->status[curr_line][curr_row - 1];
tnode->status[curr_line][curr_row - 1] = temp;
tnode->curr_row = curr_row - 1;
}
}
void switch_right(struct Node *tnode) {
int temp;
int curr_line=tnode->curr_line;
int curr_row=tnode->curr_row;
if (curr_row < ROW_MAX - 1) {
temp = tnode->status[curr_line][curr_row];
tnode->status[curr_line][curr_row] = tnode->status[curr_line][curr_row + 1];
tnode->status[curr_line][curr_row + 1] = temp;
tnode->curr_row = curr_row + 1;
}
}

int try_up(struct Node *tnode) {
int res;
int temp;
int curr_line=tnode->curr_line;
int curr_row=tnode->curr_row;
res=judge_array(tnode->status);
if (curr_line > 0) {
temp = tnode->status[curr_line][curr_row];
tnode->status[curr_line][curr_row] = tnode->status[curr_line - 1][curr_row];
tnode->status[curr_line - 1][curr_row] = temp;
curr_line = curr_line - 1;

res=judge_array(tnode->status);

temp = tnode->status[curr_line][curr_row];
tnode->status[curr_line][curr_row] = tnode->status[curr_line + 1][curr_row];
tnode->status[curr_line + 1][curr_row] = temp;
curr_line = curr_line + 1;
}

return res;
}
int try_down(struct Node *tnode) {
int res;
int temp;
int curr_line=tnode->curr_line;
int curr_row=tnode->curr_row;
res=judge_array(tnode->status);
if (curr_line < LINE_MAX - 1) {
temp = tnode->status[curr_line][curr_row];
tnode->status[curr_line][curr_row] = tnode->status[curr_line + 1][curr_row];
tnode->status[curr_line + 1][curr_row] = temp;
curr_line = curr_line + 1;

res=judge_array(tnode->status);

temp = tnode->status[curr_line][curr_row];
tnode->status[curr_line][curr_row] = tnode->status[curr_line - 1][curr_row];
tnode->status[curr_line - 1][curr_row] = temp;
curr_line = curr_line-1;
}
return res;
}

int try_left(struct Node *tnode) {
int res;
int temp;
int curr_line=tnode->curr_line;
int curr_row=tnode->curr_row;
res=judge_array(tnode->status);
if (curr_row > 0) {
temp = tnode->status[curr_line][curr_row];
tnode->status[curr_line][curr_row] = tnode->status[curr_line][curr_row - 1];
tnode->status[curr_line][curr_row - 1] = temp;
curr_row = curr_row - 1;

res=judge_array(tnode->status);

temp = tnode->status[curr_line][curr_row];
tnode->status[curr_line][curr_row] = tnode->status[curr_line][curr_row + 1];
tnode->status[curr_line][curr_row + 1] = temp;
curr_row = curr_row + 1;
}
return res;
}

int try_right(struct Node *tnode) {
int res;
int temp;
int curr_line=tnode->curr_line;
int curr_row=tnode->curr_row;
res=judge_array(tnode->status);
if (curr_row < ROW_MAX - 1) {
temp = tnode->status[curr_line][curr_row];
tnode->status[curr_line][curr_row] = tnode->status[curr_line][curr_row + 1];
tnode->status[curr_line][curr_row + 1] = temp;
curr_row = curr_row + 1;

res=judge_array(tnode->status);

temp = tnode->status[curr_line][curr_row];
tnode->status[curr_line][curr_row] = tnode->status[curr_line][curr_row - 1];
tnode->status[curr_line][curr_row - 1] = temp;
curr_row = curr_row - 1;
}
return res;
}

void sort(int a[], int b[]) {
int length = 4;
int i,j,temp;
for (i=0; i<length; i++) {
b[i]=i;
}
for(i=0; i<length - 1; i++) {
for (j=0; j<length-1-i; j++)
if (a[b[j]] < a[b[j+1]]) {
temp = b[j+1];
b[j+1]=b[j];
b[j]=temp;
}
}
}
void copy(int src[LINE_MAX][ROW_MAX], int dest[LINE_MAX][ROW_MAX]) {
int i,j;
for (i=0; i<LINE_MAX; i++) {
for (j=0; j<ROW_MAX; j++) {
dest[i][j] = src[i][j];
}
}
}
int compare(int src[LINE_MAX][ROW_MAX], int dest[LINE_MAX][ROW_MAX]) {
int i,j;
for (i=0; i<LINE_MAX; i++) {
for (j=0; j<ROW_MAX; j++) {
if (dest[i][j] != src[i][j]) {
return 0;
}
}
}
return 1;
}
int ExistOrNot(struct Node *head, struct Node * a){
while (head!=NULL&&a!=NULL) {
if (compare(head->status, a->status)) {
return 1;
}
head = head->next;
}
return 0;
}