#include <iostream>
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "string.h"
#include <queue>
#include <stack>
using namespace std;
const int N=3;//3*3棋盘
const int Max_Step=32;//最大搜索深度
enum Direction{None,Up,Down,Left,Right};//方向,分别对应上下左右
struct Chess//棋盘
{
int chessNum[N][N];//棋盘数码
int Value;//评估值
Direction BelockDirec;//所屏蔽方向
struct Chess * Parent;//父节点
};
void PrintChess(struct Chess *TheChess);//打印棋盘
struct Chess * MoveChess(struct Chess * TheChess,Direction Direct,bool CreateNewChess);//移动棋盘数字
int Appraisal(struct Chess * TheChess,struct Chess * Target);//估价函数
struct Chess * Search(struct Chess* Begin,struct Chess * Target);//A*搜索函数
int main()
{
//本程序的一组测试数据为
/*初始棋盘
*1 4 0*
*3 5 2*
*6 7 8*
*/
/*目标棋盘
*0 1 2*
*3 4 5*
*6 7 8*
*/
Chess Target;
Chess *Begin,*ChessList;
Begin=new Chess;
int i;
cout<<"请输入初始棋盘,各数字用空格隔开:"<<endl;
for(i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cin>>Begin->chessNum[i][j];
}
}
cout<<"请输入目标棋盘,各数字用空格隔开:"<<endl;
for(i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cin>>Target.chessNum[i][j];
}
}
//获取初始棋盘
Appraisal(Begin,&Target);
Begin->Parent=NULL;
Begin->BelockDirec=None;
Target.Value=0;
cout<<"初始棋盘:";
PrintChess(Begin);
cout<<"目标棋盘:";
PrintChess(&Target);
ChessList=Search(Begin,&Target);//搜索
//打印
if(ChessList)
{
/*将返回的棋盘列表利用栈将其倒叙*/
Chess *p=ChessList;
stack<Chess *>Stack;
while(p->Parent!=NULL)
{
Stack.push(p);
p=p->Parent;
}
cout<<"搜索结果:"<<endl;
int num=1;
while(!Stack.empty())
{
cout<<"第"<<num<<"步: ";
num++;
PrintChess(Stack.top());
Stack.pop();
}
cout<<"\n完成!"<<endl;
}else
cout<<"搜索不到结果,搜索深度大于32\n"<<endl;
return 0;
}
//打印棋盘
void PrintChess(struct Chess *TheChess)
{
cout<<"(评估值为";
cout<<TheChess->Value;
cout<<")"<<endl;
for(int i=0;i<N;i++)
{
cout<<" ";
for(int j=0;j<N;j++)
{
cout<<TheChess->chessNum[i][j]<<" ";
}
cout<<endl;
}
}
//移动棋盘
struct Chess * MoveChess(struct Chess * TheChess,Direction Direct,bool CreateNewChess)
{
struct Chess * NewChess;
//获取空闲格位置
int i,j;
for(i=0;i<N;i++)
{
bool HasGetBlankCell=false;
for(j=0;j<N;j++)
{
if(TheChess->chessNum[i][j]==0)
{
HasGetBlankCell=true;
break;
}
}
if(HasGetBlankCell)
break;
}
int ii=i,jj=j;
bool AbleMove=true;
//判断是否可以移动
switch(Direct)
{
case Up:
i++;
if(i>=N)
AbleMove=false;
break;
case Down:
i--;
if(i<0)
AbleMove=false;
break;
case Left:
j++;
if(j>=N)
AbleMove=false;
break;
case Right:
j--;
if(j<0)
AbleMove=false;
break;
};
if(!AbleMove)//不可以移动则返回原节点
{
return TheChess;
}
if(CreateNewChess)
{
NewChess=new Chess();
for(int x=0;x<N;x++)
{
for(int y=0;y<N;y++)
NewChess->chessNum[x][y]=TheChess->chessNum[x][y];//创建新棋盘,此时值与原棋盘一致
}
}
else
NewChess=TheChess;
NewChess->chessNum[ii][jj] = NewChess->chessNum[i][j];//移动数字
NewChess->chessNum[i][j]=0;//将原数字位置设置为空格
return NewChess;
}
//估价函数
int Appraisal(struct Chess * TheChess,struct Chess * Target)
{
int Value=0;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(TheChess->chessNum[i][j]!=Target->chessNum[i][j])
Value++;
}
}
TheChess->Value=Value;
return Value;
}
//A*搜索函数
struct Chess * Search(struct Chess* Begin,struct Chess * Target)
{
Chess *p1,*p2,*p;
int Step=0;//深度
p=NULL;
queue<struct Chess *> Queue;
Queue.push(Begin);//初始棋盘入队
//搜索
do{
p1=(struct Chess *)Queue.front();
Queue.pop();//出队
for(int i=1;i<=4;i++)//分别从四个方向推导出新子节点
{
Direction Direct=(Direction)i;
if(Direct==p1->BelockDirec)//跳过屏蔽方向
continue;
p2=MoveChess(p1,Direct,true);//移动数码
if(p2!=p1)//数码是否可以移动
{
Appraisal(p2,Target);//对新节点估价
if(p2->Value<=p1->Value)//是否为优越节点
{
p2->Parent=p1;
switch(Direct)//设置屏蔽方向,防止往回推
{
case Up:p2->BelockDirec=Down;break;
case Down:p2->BelockDirec=Up;break;
case Left:p2->BelockDirec=Right;break;
case Right:p2->BelockDirec=Left;break;
}
Queue.push(p2);//存储节点到待处理队列
if(p2->Value==0)//为0则,搜索完成
{
p=p2;
i=5;
}
}
else
{
delete p2;//为劣质节点则抛弃
p2=NULL;
}
}
}
Step++;
if(Step>Max_Step)
return NULL;
}while(p==NULL || Queue.size()<=0);
return p;
}