#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=30;//最大搜索深度

enum Direction{None,Up,Down,Left,Right};//方向
struct Chess//棋盤
{
    int cell[N][N];//數碼數組
    int Value;//評估值
    Direction BelockDirec;//所屏蔽方向
    struct Chess * Parent;//父節點
};

//打印棋盤
void PrintChess(struct Chess *TheChess)
{
    printf("------------------------------------------------------------------------\n");
    for(int i=0;i<N;i++)
    {
        printf("\t");
        for(int j=0;j<N;j++)
        {
            printf("%d\t",TheChess->cell[i][j]);
        }
        printf("\n");
    }
    printf("\t\t\t\t差距:%d\n",TheChess->Value);
}
//移動棋盤
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->cell[i][j]==0)
            {
                HasGetBlankCell=true;
                break;
            }
        }
        if(HasGetBlankCell)
            break;
    }

    //移動數字
    int t_i=i,t_j=j;
    bool AbleMove=true;
    switch(Direct)
    {
    case Up:
        t_i++;
        if(t_i>=N)
            AbleMove=false;
        break;
    case Down:
        t_i--;
        if(t_i<0)
            AbleMove=false;
        break;
    case Left:
        t_j++;
        if(t_j>=N)
            AbleMove=false;
        break;
    case Right:
        t_j--;
        if(t_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->cell[x][y]=TheChess->cell[x][y];
        }
    }
    else
        NewChess=TheChess;
    NewChess->cell[i][j]=NewChess->cell[t_i][t_j];
    NewChess->cell[t_i][t_j]=0;

    return NewChess;
}

//初始化一個初始棋盤
struct Chess * RandomChess(const struct Chess * TheChess)
{
    int M=30;//隨機移動棋盤步數
    struct Chess * NewChess;
    NewChess=new Chess();
    memcpy(NewChess,TheChess,sizeof(Chess));
    srand((unsigned)time(NULL));
    for(int i=0;i<M;i++)
    {    
        int Direct=rand()%4;
        //printf("%d\n",Direct);
        NewChess=MoveChess(NewChess,(Direction) Direct,false);
    }
    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->cell[i][j]!=Target->cell[i][j])
                Value++;
        }
    }
    TheChess->Value=Value;
    return Value;
}

//搜索函數
struct Chess * Search(struct Chess* Begin,struct Chess * Target)
{
    Chess * p1,*p2,*p;
    int Step=0;//深度
    p=NULL;
    queue<struct Chess *> Queue1;
    Queue1.push(Begin);
    //搜索
    do{
        p1=(struct Chess *)Queue1.front();
        Queue1.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;
                    }
                    Queue1.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 || Queue1.size()<=0);

    return p;
}

void main()
{
    Chess * Begin,Target,* T;
    //設定目標棋盤 [0 1 2],[3 4 5],[6 7 8]
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            Target.cell[i][j]=i*N+j;
        }
    }
    //獲取初始棋盤
    Begin=RandomChess(&Target);
    Appraisal(Begin,&Target);
    Begin->Parent=NULL;
    Begin->BelockDirec=None;
    Target.Value=0;
    printf("目標棋盤:\n");
    PrintChess(&Target);
    printf("初始棋盤:\n");
    PrintChess(Begin);
    //圖搜索
    T=Search(Begin,&Target);        
    //打印
    if(T)
    {
        /*把路徑倒序*/
        Chess *p=T;
        stack<Chess *>Stack1;
        while(p->Parent!=NULL)
        {
            Stack1.push(p);
            p=p->Parent;
        }
        printf("搜索結果:\n");
        while(!Stack1.empty())
        {
            PrintChess(Stack1.top());
            Stack1.pop();
        }
        printf("\n完成!");
    }else
        printf("搜索不到結果.深度為%d\n",Max_Step);

    scanf("%d",T);
}