#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <time.h>

using namespace std;
#define N 3 // 数码组大小
#define Max_STEP 50 // 最大搜索深度
#define MAX 50

typedef struct node // 八数码结构体
{
int form[N][N];
int evalue; // 评估值
int udirect; // 所屏蔽方向，防止往回推到上已状态，1上2下3左4右
struct node *parent; // 父节点
}Graph;

Graph *Qu[MAX]; // 队列
Graph *St[MAX]; // 堆栈

// 打印数码组
void Print(Graph *The_graph)
{
int i, j;
if (The_graph == NULL)
{
printf("图为空\n");
}
else
{
printf("----------------\n");
for (i = 0; i < N; ++i)
{
printf("|\t");
for (j = 0; j < N; ++j)
{
printf("%d\t", The_graph->form[i][j]); // 遍历打印
}
printf("\t|\n");
}
printf("|\t\t\t差距:%d\t\n", The_graph->evalue); // 差距显示
printf("----------------\n");
}
}

// 评价函数
int Evaluate(Graph *The_graph, Graph *End_graph)
{
int valute = 0; // 差距数
int i, j;
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
if (The_graph->form[i][j] != End_graph->form[i][j])
{
valute++;
}
}
}
The_graph->evalue = valute;
return valute;
}

// 移动数码组
Graph *Move(Graph *The_graph, int Direct, int CreatNew_graph)
{
Graph *New_graph;
int HasGetBlank = 0; // 是否获取空格位置
int AbleMove = 1; // 是否可移动
int i, j, t_i, t_j, x, y;
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
if (The_graph->form[i][j] == 0)
{
HasGetBlank = 1;
break;
}
}
if (HasGetBlank == 1)
{
break;
}
}
// printf("空格位置:%d,%d\n", i, j);
t_i = i;
t_j = j;

// 移动空格
switch(Direct)
{
case 1:// 上
t_i--;
if (t_i < 0)
AbleMove = 0;
break;
case 2:// 下
t_i++;
if (t_i >= N)
AbleMove = 0;
break;
case 3: // 左
t_j--;
if (t_j < 0)
AbleMove = 0;
break;
case 4: // 右
t_j++;
if (t_j >= N)
AbleMove = 0;
break;
}
if (AbleMove == 0) // 不能移动则返回原结点
{
return The_graph;
}
if (CreatNew_graph == 1)
{
New_graph = new Graph; // 生成节点
for (x = 0; x < 3; ++x)
{
for (y = 0; y < 3; ++y)
{
New_graph->form[x][y] = The_graph->form[x][y]; // 复制数码组
}
}
}
else
{
New_graph = The_graph;
}
// 移动后
New_graph->form[i][j] = New_graph->form[t_i][t_j];
New_graph->form[t_i][t_j] = 0;
return New_graph;
}

// 搜索函数
Graph *Search(Graph *Begin, Graph *End)
{
Graph *g1, *g2, *g;
int Step = 0; // 深度
int Direct = 0; // 方向
int i;
int front, rear;
front = rear = -1; // 队列初始化
g = NULL;
rear++; // 入队
Qu[rear] = Begin;
while (rear != front)
{ // 队列不为空
front++; // 出队
g1 = Qu[front];
for (i = 1; i <= 4; ++i) // 分别从4个方向推导出新子节点
{
Direct = i;
if (Direct == g1->udirect) // 跳过屏蔽方向
{
continue;
}
g2 = Move(g1, Direct, 1); // 移动数码组

if (g2 != g1) // 数码组是否可以移动
{
// 可以移动
Evaluate(g2, End); // 评价新的节点
if (g2->evalue <= g1->evalue + 1)
{ // 是优越节点
g2->parent = g1;
// 移动空格
switch(Direct) // 设置屏蔽方向，防止往回推
{
case 1:// 上
g2->udirect = 2;
break;
case 2: // 下
g2->udirect = 1;
break;
case 3:
g2->udirect = 4;
break;
case 4:
g2->udirect = 3;
break;
}
rear++;
Qu[rear] = g2; // 存储节点到待处理队列
if (g2->evalue == 0) // 为0则搜索完成
{
g = g2;
// i = 5;
break;
}
}
else
{
free(g2); // 抛弃劣质节点
g2 = NULL;
}
}
}
if (g != NULL)
{
if (g->evalue == 0)
{
break;
}
}
++Step; // 统计深度
if (Step > Max_STEP)
{
break;
}
}
return g;
}
int main(int argc, const char *argv[])
{
cout << "------------------实验一：八数码游戏-------------------" << endl;
cout << "------------------贝佳洋 2012020052-------------------" << endl;

Graph Begin_graph = {
{
{
2, 8, 3
},
{
1, 6, 4
},
{
7, 0, 5
}
}, 0, 0, NULL
};
// 目标数码组
Graph End_graph = {
{
{
1, 2, 3
},
{
8, 0, 4
},
{
7, 6, 5
}
}, 0, 0, NULL
};
Evaluate(&Begin_graph, &End_graph); // 对初始的数码组评价
printf("初始数码组:\n");
Print(&Begin_graph);
printf("目标数码组:\n");
Print(&End_graph);

Graph *G, *P;
int top = -1;
// 图搜索
G = Search(&Begin_graph, &End_graph);
// 打印
if (G)
{
// 把路径倒序
P = G;
// 压栈
while (P != NULL)
{
++top;
St[top] = P;
P = P->parent;
}
printf("<<<<<<<<<<<<<<<<<搜索结果>>>>>>>>>>>>>>>\n");
// 弹栈打印
while (top > -1)
{
P = St[top];
--top;
Print(P);
}
printf("<<<<<<<<<<<<<<<<<完成>>>>>>>>>>>>>>>\n");
}
else
{
printf("搜索不到结果，深度为%d\n", Max_STEP);
// 设计搜索深度范围主要是防止队列内存越界
}
return 0;
}