common.cpp

选择深度优先算法来求解该八数码问题（3×3九宫格棋盘）

#include <iostream.h>
#include <iomanip.h>
#include "stdio.h"
#include "malloc.h"
#include <stdlib.h>
typedef struct node
{
	int ** Data;
	int Deep;
	struct node * next;
	struct node * parent;
} Node; //data sturcture of Node

typedef struct node_save
{
	int ** Data1;
	struct node_save * next;
} Node_Save ;//data struct of the node which has been visited 


/*  the data structure of 8_puzzle question */
int up = 0, down = 1, left = 2, right = 3; //the direct of move

int ** target;//the target node
int start[3][3];  // the first node
int Temp_data[3][3]; // the node 
Node * List, * Tail; //the stack
Node_Save * Save_List, *Node_Tail; //the list which saves the visited node



/* campare one  node with the other node;if it is equal,return 1;or return 0 */
int compare(int ** Data_1,int **Data_2 )
{
	int i,j;
	int num_equ = 0;
	for(i = 0; i < 3; i++)
		for(j = 0; j < 3; j++)
			if(Data_1[i][j] == Data_2[i][j])
			{
				num_equ++;
			}
	if(num_equ == 9)
		return 1;
	else
		return 0;
}

/* the zero element move ,so get the new node. the move direction has 4.up ,down , left, right*/
int move(int ** Data_Input,int direct)
{
	int i , j , Zero_i , Zero_j , new_i , new_j, temp;
	for(i = 0; i < 3; i++)
		for(j = 0; j < 3; j++)
		{
			if(Data_Input[i][j] == 0)
			{
				Zero_i = i;
				Zero_j = j;
			}
			Temp_data[i][j] = Data_Input[i][j];
		}

			

	switch(direct)
	{
	case 0 :	{                               //up
					new_i = Zero_i - 1;
					new_j = Zero_j;
					if(new_i < 0)
						return 0;
					else
					{
						temp = Temp_data[new_i][new_j];
						Temp_data[new_i][new_j] = 0;
						Temp_data[Zero_i][Zero_j] = temp;
					}
					break;
				 
				}
	
	case 1 :	{                                  //down 
					new_i = Zero_i + 1;
					new_j = Zero_j;
					if(new_i > 2)
						return 0;
					else
					{
						temp = Temp_data[new_i][new_j];
						Temp_data[new_i][new_j] = 0;
						Temp_data[Zero_i][Zero_j] = temp;
					}
					break;
				
				 
				}
	case 2 :	{                                    //left
					new_i = Zero_i ;
					new_j = Zero_j - 1;
					if(new_j < 0)
						return 0;
					else
					{
						temp = Temp_data[new_i][new_j];
						Temp_data[new_i][new_j] = 0;
						Temp_data[Zero_i][Zero_j] = temp;
					}
					break;
				
				  
				}
	case 3 :	{                              //right
					new_i = Zero_i;
					new_j = Zero_j + 1;
					if(new_j > 2)
						return 0;
					else
					{
						temp = Temp_data[new_i][new_j];
						Temp_data[new_i][new_j] = 0;
						Temp_data[Zero_i][Zero_j] = temp;
								
					}
					break;
					
					
				}
				
	
	}
	return 1;
}




/* push the node int stack */
void push (Node * New_Node)
{

	Tail -> next = New_Node ;
	Tail = New_Node;
}

/* pop the node from the stack */
void pop(Node ** Node_Out)
{
	Node * Index,* front;
	*Node_Out = Tail;
	for(Index = List; Index != NULL; Index = Index ->next)
	{
		if(Index->next == Tail)
		{
			front = Index;
		}
	}
	if(List->next == NULL)
	{
		List = Tail;
	}
	else
	{
		Tail = front;
		Tail->next = NULL;
	}
}

/* free the List */
void free(Node * List)
{
	Node * Index, *Free_Node;
	Free_Node = List;
	for(Index = List->next; Index != NULL; Index = Index -> next)
	{
		List = Index;
		free(Free_Node);
		Free_Node = List;
	}
}


/* add the new node to the list */

void add(Node_Save * Visited)
{
	Node_Tail -> next = Visited;
	Node_Tail = Visited;
}


/* deep first search*/
Node * Deep_First_Search(Node * List_Node)
{
	Node * Index,* temp,* visited,**temp2;
	Node_Save * temp_Node,* Index2 ;
	int * temp3;
	int * temp4;
	int flag = 0;
	int flag_Stack = 0; //the flag used to init the stack
 
	int i ,j,k,l;
	Index = List_Node;
	visited = NULL;
	temp2 =(Node **)malloc(sizeof(Node *)); //apply for a free space
	if(temp2 == NULL)
	{
		printf(" no free space\n");
	}
 /*the flag used to init the list*/
	temp_Node =(Node_Save *) malloc(sizeof(Node_Save));
	if(temp_Node == NULL)
	{
		printf("no free space\n");
		exit(0);
	}
	temp_Node->Data1 = (int **)malloc(3*sizeof(int *));
	if(temp_Node->Data1 == NULL)
	{
		printf("no free space\n");
	}
	for(i =0 ; i< 3; i++)
	{
		temp3 = (int *)malloc(3*sizeof(int));
		if(temp3 == NULL)
		{
			printf(" no free space\n");
		}
		temp_Node->Data1[i] = temp3;
	}


 

	for(i = 0; i < 3; i++)
		for(j = 0; j < 3; j++)
		{
			temp_Node->Data1[i][j] = List_Node ->Data[i][j];
		}
	temp_Node ->next = NULL;

	Save_List = temp_Node;
	Node_Tail = Save_List;

	

	while(0 == compare(Index->Data,target))  //compare
	{
		if(Index ->Deep < 8)
		{  for(i = 0; i < 4 ;i++)
			{flag = 0;            //blank move 
				if(move(Index->Data,i) == 1)
				{  
					temp =(Node *) malloc(sizeof(Node));
					temp->Data = (int **)malloc(3*sizeof(int *));
					if(temp->Data == NULL)
					{
						printf("no free space\n");
					}
					else
					{
						for(j = 0; j < 3; j++)
						{
							temp3 = (int *)malloc(3*sizeof(int));
							if(temp3 == NULL)
							{
								printf(" no free space\n");
							}
							temp->Data[j] = temp3;
						
						}
					}
					if(temp == NULL)
					{
						printf(" no free space \n");
						exit(0);
					}
					else
					{

						for(k = 0; k < 3; k++)
							for(l = 0; l < 3; l++)
							{
								temp ->Data[k][l] = Temp_data[k][l];
							}
						temp ->Deep = Index->Deep + 1;
						temp ->next = NULL;
						temp ->parent = Index;
					}


	
				
				
					for(Index2 = Save_List; Index2 != NULL; Index2 = Index2 -> next)
					{
						if(1 == compare(Index2 ->Data1,temp ->Data))  //see whether it has been visited
						{
							free(temp);
							flag = 1; // show the two matix is same
							break;
						}
					}
							
					if(0 == flag&&flag_Stack ==0)
					{
						List = temp;     //init the stack 
						Tail = temp;
						flag_Stack = 1;
					}
					else if(0 == flag&& flag_Stack == 1)
					{

						push(temp);  // push the stack
					}                     
				
				}
				
			}	
		
		}
		 
			pop(temp2);
			Index = *temp2;
/*
			printf("%d,%d,%d,\t%d\n",Index->Data[0][0],Index->Data[0][1],Index->Data[0][2],Index->Deep);
			printf("%d,%d,%d,\t%d\n",Index->Data[1][0],Index->Data[1][1],Index->Data[1][2],Index->Deep);
			printf("%d,%d,%d,\t%d\n",Index->Data[2][0],Index->Data[2][1],Index->Data[2][2],Index->Deep);
			printf("\n");*/
				// have the visited node to save
			temp_Node =(Node_Save *) malloc(sizeof(Node_Save));
			
			temp_Node->Data1 = (int ** )malloc(3*sizeof(int *));
			if(temp_Node->Data1 == NULL)
			{
				printf(" no free space\n");
				exit(0);
			}
		
			for( i = 0; i <3 ;i++)
			{
				temp4 = (int *)malloc(3*sizeof(int));
				if(temp4 == NULL)
				{
					printf("no free space\n");
					exit(0);
				}
				temp_Node->Data1[i] = temp4;
			}

			if(temp_Node == NULL)
			{
				printf("no free space\n");
				exit(0);
			}
			for(i = 0; i < 3; i++)
				for(j = 0; j < 3; j++)
				{
					temp_Node->Data1[i][j] = Index ->Data[i][j];
				}
			
			temp_Node ->next = NULL;

			add(temp_Node);

			
			
		}
	return Index;
}
void main( )
{
	Node * First_Node,* temp,*Result;
	int i,j,k,l;
	int * temp1;

	List = NULL; //init the stack
	Tail = NULL;
	Save_List = NULL;
	
 //init the list used to save the visited node
	target = (int **)malloc(3*sizeof(int *));
	if(target == NULL)
	{
		printf("no free space\n");
		exit(0);
	}
	for(i =0 ;i < 3; i++)
	{
		temp1 = (int *)malloc(3*sizeof(int));
		if(temp1 == NULL)
		{
			printf("no free space\n");
			exit(0);
		}
		target[i] = temp1;
	}
		
		
	target[0][0] = 1; target[0][1] = 2 ;target[0][2] = 3;
	target[1][0] = 8; target[1][1] = 0; target[1][2] = 4;
	target[2][0] = 7; target[2][1] = 6 ;target[2][2] = 5;

	printf("please input the number\n");	
/* input the start node */
	//scanf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d",&start[0][0],&start[0][1],&start[0][2],
	//&start[1][0],&start[1][1],&start[1][2],&start[2][0],&start[2][1],&start[2][2]);
	start[0][0] = 2; start[0][1] = 8; start[0][2] = 3; 
	start[1][0] = 1; start[1][1] = 6; start[1][2] = 4;
	start[2][0] = 7; start[2][1] = 0; start[2][2] = 5;


	
	temp = (Node *)malloc(sizeof(Node));
	temp->Data = (int **)malloc(3*sizeof(int *));
	if(temp1 == NULL)
	{
		printf("no free space\n");
	}

	for(i = 0; i <3; i++)
    {		
		temp1 = (int *)malloc(3*sizeof(int));
		if(temp1 == NULL)
		{
			printf("no free space \n");
		}
		else
		{
			temp->Data[i] = temp1;
		}
	}

	if(temp == NULL)
	{
		printf("no free space\n");
		exit(0);
	}
	else
	{
		for(i = 0; i < 3; i++)
			for(j = 0; j < 3; j++)
			{
				temp->Data[i][j] = start[i][j];
			}
		temp ->Deep = 1;
		temp ->next = NULL;
		temp -> parent = NULL;
	}
	First_Node = temp;
	Result = Deep_First_Search(First_Node);

for(temp = Result; temp !=NULL; temp = temp->parent)
	{
		printf("%d,%d,%d,\t%d\n",temp ->Data[0][0],temp ->Data[0][1],temp ->Data[0][2],temp->Deep);
		printf("%d,%d,%d,\t%d\n",temp ->Data[1][0],temp ->Data[1][1],temp ->Data[1][2],temp->Deep);
		printf("%d,%d,%d,\t%d\n",temp ->Data[2][0],temp ->Data[2][1],temp ->Data[2][2],temp->Deep);
		printf("\n");
	}
}