#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MaxSize 20
typedef struct Node//状态结点
{
int data[2][2]; //状态结点数组
struct Node *parent; //指向状态结点的父结点指针
}SNode;
typedef struct//OpenList 循环队列
{
SNode *data[MaxSize]; //状态结点地址数组
int front;
int rear;
}Que;
typedef struct//CLOSEDList 顺序栈
{
SNode *data[MaxSize]; //状态结点地址数组
int top;
int n; //待扩展/已扩展状态结点序号(选)
}Stack;
void Initqueue(Que *&Q)//初始队列
{
Q=(Que *)malloc(sizeof(Que));
Q->front=Q->rear=0;
}
void Initstack(Stack *&St)//初始栈
{
St=(Stack *)malloc(sizeof(Stack));
St->top=-1;
}
int Enststack(Stack *&St,SNode *S)//进栈 Close表不用出栈
{
if(St->top==MaxSize-1)
return 0;
else
{
St->top++;
St->data[St->top]=S;
St->n++;
return 1;
}
}
int Enqueue(Que *&Q,SNode *S)//进队
{
if ((Q->rear+1) % MaxSize == Q->front)
return 0;
Q->rear=(Q->rear+1) % MaxSize;
Q->data[Q->rear]=S;
return 1;
}
int dequeue(Que *&Q,SNode *&S)//出队
{
Q->front=(Q->front+1) % MaxSize;
S=Q->data[Q->front];
return 1;
}
int Emptyqueue(Que *&Q)//队空判断
{
if (Q->front==Q->rear)
return 1;
else
return 0;
}
int JudgeGoalS(SNode *So,SNode *Sg)//判断目标状态
{
int i,j;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
if(So->data[i][j] != Sg->data[i][j])
return 0;
}
}
return 1;
}
//判断新生成的状态结点是否在搜索图中出现过
int Checkopenlist(Que *Q, int data[2][2])//检查 OPENList
{
if(Emptyqueue(Q) == 1)//队空
return 0;
int i,j,m;
for(m=Q->front+1;m<=Q->front+((Q->rear-Q->front+MaxSize)%MaxSize);m++)
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
if(data[i][j] != Q->data[m]->data[i][j])
i=2;
if(i==1 && j==1)
return 1;
}
}
return 0;
/*int i,j,k,m=0,check_sum;
int check[4]={0};//Check whether eql
for(k=Q->front+1;k<=Q->front+((Q->rear-Q->front+MaxSize)%MaxSize);k++)
{
check_sum=0;
m=0;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
if(Q->data[k]->data[i][j] == data[i][j])
check[m]=1;
check_sum+=check[m];
m++;
}
}
if(check_sum == 4)//same
return 1;
}
return 0;//new S */
}
int Checkclosedlist(Stack *&St, int data[2][2])//检查 ClosedList
{
int i,j,m;
for(m=0;m<=St->top;m++)
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
if(data[i][j] != St->data[m]->data[i][j])
i=2;
if(i==1 && j==1)
return 1;
}
}
return 0;
/*int i,j,k,m=0,check_sum=0;
int check[4]={0};//Check whether eql
for(k=0;k<=St->top;k++)
{
check_sum=0;
m=0;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
if(St->data[k]->data[i][j] == data[i][j])
check[m]=1;
check_sum+=check[m];
m++;
}
}
if(check_sum == 4)//same
return 1;
}
return 0;//new S */
}
//扩展结点
int JudgeOPostion(SNode *So)//判断待扩展结点的空格位置
{
int i,j;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
if(So->data[i][j]==0)
{
if(i==0 && j==0)
return 1;
else if(i==0 && j==1)
return 2;
else if(i==1 && j==0)
return 3;
else if(i==1 && j==1)
return 4;
}
}
}
return 0;
}
void developSnode(SNode *&S, SNode *So, int c, int n, int temp)//扩展结点
{
switch(c)
{
case 1:if(n==2)//向下
{
S->data[0][0]=So->data[1][0]; S->data[0][1]=So->data[0][1];
S->data[1][0]=So->data[0][0]; S->data[1][1]=So->data[1][1];
}
else if(n==1)//向右
{
S->data[0][0]=So->data[0][1]; S->data[0][1]=So->data[0][0];
S->data[1][0]=So->data[1][0]; S->data[1][1]=So->data[1][1];
}
break; //i=0;j=0;
case 2:if(n==2)//向左
{
S->data[0][0]=So->data[0][1]; S->data[0][1]=So->data[0][0];
S->data[1][0]=So->data[1][0]; S->data[1][1]=So->data[1][1];
}
else if(n==1)//向下
{
S->data[0][0]=So->data[0][0]; S->data[0][1]=So->data[1][1];
S->data[1][0]=So->data[1][0]; S->data[1][1]=So->data[0][1];
}
break; //i=0;j=1;
case 3:if(n==2)//向右
{
S->data[0][0]=So->data[0][0]; S->data[0][1]=So->data[0][1];
S->data[1][0]=So->data[1][1]; S->data[1][1]=So->data[1][0];
}
else if(n==1)//向上
{
S->data[0][0]=So->data[1][0]; S->data[0][1]=So->data[0][1];
S->data[1][0]=So->data[0][0]; S->data[1][1]=So->data[1][1];
}
break; //i=1;j=0;
default:if(n==2)//向上
{
S->data[0][0]=So->data[0][0]; S->data[0][1]=So->data[1][1];
S->data[1][0]=So->data[1][0]; S->data[1][1]=So->data[0][1];
}
else if(n==1)//向左
{
S->data[0][0]=So->data[0][0]; S->data[0][1]=So->data[0][1];
S->data[1][0]=So->data[1][1]; S->data[1][1]=So->data[1][0];
}
break; //i=1,j=1;
}
}
/*注：
switch (c):
c=1,2,3,4(default) 对应结点空格的四个位置，以确定如何生成子结点。
case 1: //i=0;j=0;
case 2: //i=0;j=1;
case 3: //i=1;j=0;
default: //i=1,j=1;
扩展结点 So，新生成结点 S
n:每个结点最多生成 2 个子结点
n=2 新生成结点 S,入队
n=1 新生成结点 S,入队
temp 表示空格,在此以0表示空格
*/
void Print_Solution(SNode *S)//打印节点
{
int i,j;
printf("\n");
while(S != NULL)
{
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
printf("%d ",S->data[i][j]);
if(j==1)
printf("\n");
}
if(S->parent!=NULL)
{
printf(" ^\n");
printf(" |\n");
}
S=S->parent;
}
printf("\n");
}
void Print_Open(SNode *S)
{
int i,j;
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
printf("%d ",S->data[i][j]);
if(j==1)
printf("\n");
}
printf("\n");
}
void Print_Close(Stack *St)
{
int i,j,k;
printf("Close List:\n");
for(k=0;k<=St->top;k++)
{
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
printf("%d ",St->data[k]->data[i][j]);
if(j==1)
printf("\n");
}
printf("\n");
}
}
void main()
{
SNode *Sn,*S,*So,*Sg;
Que *Q;
Stack *St;
int j,i,n=2,c;//n is number of developed subnodes //,top
int dataso[2][2]={0,1,
2,3},
datasg[2][2]={1,2,
0,3};
//int dataso[2][2]={0,1,3,2},datasg[2][2]={1,2,0,3};
So=(SNode *)malloc(sizeof(SNode));
Sg=(SNode *)malloc(sizeof(SNode));
So->parent=NULL;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
So->data[i][j]=dataso[i][j];
Sg->data[i][j]=datasg[i][j];
}
}
Initqueue(Q);
Initstack(St);
printf("Open List:\n");
Enqueue(Q,So);//进队
Print_Open(So);
while(Emptyqueue(Q) !=1 ) // Search States Space Graph
{
dequeue(Q,S);//取出open表第一个节点
Enststack(St,S);//放入close表
So=S; // Saved Parent
if (JudgeGoalS(So,Sg)==1)
{
Print_Close(St);//
printf("Find solution!\n");
Print_Solution(So);
break;
}
else
{
c=JudgeOPostion(So);//int JugeOPostion(Snoed *So);
while(n>=1)
{
Sn=(SNode *)malloc(sizeof(SNode)); // Sn New Generating Node
developSnode(Sn,So,c,n,0); // Sn->Parent=So, c: So空格位置, n: Possible New Node Number, 0:空格取值
if((Checkopenlist(Q,Sn->data) !=1) && (Checkclosedlist(St,Sn->data) !=1)) // Check whether Sn in OPEN＋CLOSED
{
Sn->parent=So;// Sn Parent
Enqueue(Q,Sn);// Sn Enter Que
Print_Open(Sn);
}
n--; // Next Child Node of So
} //Generating two children Nodes SnS of So
n=2; // when develop Next So，reset number of sub-nodes of So
}
}
if (Emptyqueue(Q)==1)
printf("No solution!\n");
}
