//
// main.c
// dong_c2
//
// Created by 神威 on 2018/10/24.
// Copyright © 2018 神威. All rights reserved.
//
#include <stdbool.h>
#include <stdio.h>
#define M 3
#define N 3
int b[M][N]={{1,2,3},{8,0,4},{7,6,5}};//目标状态
int c[9999][9]={{2,8,3,1,6,4,7,0,5}};//用于保存，已有过的状态
int main(int argc, const char * argv[]) {
void sort(int a[M][N],int i,int j,int deep,int num);
bool equal(int a[M][N],int b[M][N]);
void prin(int a[M][N]);
bool isExist(int a[M][N],int num);
int insert(int a[M][N],int num);
int i=2,j=1;//初始空格位置
int a[M][N] = {//初始状态，用0代表空格
{2,8,3},
{1,6,4},
{7,0,5}
};
//printf("\n调用函数之后:\n");
sort(a, i, j, 1,1);
}
//d为当前状态，i j为0所在的位置，deep为深度，num为已有过的状态的个数
void sort(int d[M][N],int i,int j,int deep,int num){
//prin(a);
int t,x,y;
int a[M][N] ={0};//a用于保存，操作左上右下后的状态
for(x=0;x<M;x++)//a初始化
for(y=0;y<N;y++)
a[x][y] = d[x][y];
if(j - 1 >= 0){//能左移
t = a[i][j];//左移，交换
a[i][j] = a[i][j-1];
a[i][j-1] = t;
deep++;
printf("Go left ,deep=%d\n",deep);
prin(a);
if(equal(a, b)){//若左移后，打到目标状态，退出程序
printf("secuess!\n");
exit(0);
}else{//否则进行下列操作
if(deep < 7){//当deep没超限时
if(isExist(a, num)){//若此状态已经存在，a置于上一步，输出上一步状态
printf("This is exist!So can't go left\nback to the last state,like this:\n");
for(x=0;x<M;x++)
for(y=0;y<N;y++)
a[x][y] = d[x][y];
deep--;
prin(a);
}else{//不存在，保存此状态，并进行递归
num = insert(a, num);
sort(a,i,j-1,deep,num);
deep--;
printf("return back to this state:\n! Now the deep is %d!(left)\n",deep);
for(x=0;x<M;x++)
for(y=0;y<N;y++)
a[x][y] = d[x][y];
prin(a);
}
}else{//若deep超限，a置于上一步，输出上一步状态
printf("deep >= 7 and it is not target state!(left)\nback to the last state,like this:\n");
for(x=0;x<M;x++)
for(y=0;y<N;y++)
a[x][y] = d[x][y];
prin(a);
deep--;
}
}
}else printf("can't go left\n");//若不能左移，则不做任何操作
if(i - 1 >= 0){//能上移
t = a[i][j];
a[i][j] = a[i-1][j];
a[i-1][j] = t;
deep++;
printf("Go up ,deep=%d\n",deep);
prin(a);
if(equal(a, b)){
printf("secuess!\n");
exit(0);
}else{
if(deep < 7){
if(isExist(a, num)){//若此状态已经存在，a置于上一步，输出上一步状态
printf("This is exist!So can't go up\nback to the last state,like this:\n");
for(x=0;x<M;x++)
for(y=0;y<N;y++)
a[x][y] = d[x][y];
deep--;
prin(a);
}else{//不存在，保存此状态，并进行递归
num = insert(a, num);
sort(a,i-1,j,deep,num);
deep--;
printf("return back to this state:\n! Now the deep is %d!(up)\n",deep);
for(x=0;x<M;x++)
for(y=0;y<N;y++)
a[x][y] = d[x][y];
prin(a);
}
}else{
printf("deep >= 7 and it is not target state!(up)\nback to the last state,like this:\n");
for(x=0;x<M;x++)
for(y=0;y<N;y++)
a[x][y] = d[x][y];
prin(a);
deep--;
}
}
}else printf("can't go up\n");
if(j + 1 < N){//能右移
t = a[i][j];
a[i][j] = a[i][j+1];
a[i][j+1] = t;
deep++;
printf("Go right ,deep=%d\n",deep);
prin(a);
if(equal(a, b)){
printf("secuess!\n");
exit(0);
}else{
if(deep < 7){
if(isExist(a, num)){//若此状态已经存在，a置于上一步，输出上一步状态
printf("This is exist!So can't go right\nback to the last state,like this:\n");
for(x=0;x<M;x++)
for(y=0;y<N;y++)
a[x][y] = d[x][y];
deep--;
prin(a);
}else{//不存在，保存此状态，并进行递归
num = insert(a, num);
sort(a,i,j+1,deep,num);
deep--;
printf("return back to this state:\n! Now the deep is %d!(right)\n",deep);
for(x=0;x<M;x++)
for(y=0;y<N;y++)
a[x][y] = d[x][y];
prin(a);
}
}else{
printf("deep >= 7 and it is not target state!(right)\nback to the last state,like this:\n");
for(x=0;x<M;x++)
for(y=0;y<N;y++)
a[x][y] = d[x][y];
prin(a);
deep--;
}
}
}else printf("can't go right\n");
if(i + 1 < M){//能下移
t = a[i][j];
a[i][j] = a[i+1][j];
a[i+1][j] = t;
deep++;
printf("Go down ,deep=%d\n",deep);
prin(a);
if(equal(a, b)){
printf("secuess!\n");
exit(0);
}else{
if(deep < 7){
if(isExist(a, num)){//若此状态已经存在，a置于上一步，输出上一步状态
printf("This is exist!So can't go down\nback to the last state,like this:\n");
for(x=0;x<M;x++)
for(y=0;y<N;y++)
a[x][y] = d[x][y];
deep--;
prin(a);
}else{//不存在，保存此状态，并进行递归
num = insert(a, num);
sort(a,i+1,j,deep,num);
deep--;
printf("return back to this state:\n! Now the deep is %d!(down)\n",deep);
for(x=0;x<M;x++)
for(y=0;y<N;y++)
a[x][y] = d[x][y];
prin(a);
}
}else{
printf("deep >= 7 and it is not target state!(down)\nback to the last state,like this:\n");
for(x=0;x<M;x++)
for(y=0;y<N;y++)
a[x][y] = d[x][y];
prin(a);
deep--;
}
}
}else printf("can't go down\n");
return;
}
//判断当前状态与目标状态是否一致
bool equal(int a[M][N],int b[M][N]){
int i=0,j=0;
for(i=0;i<M;i++)
for(j=0;j<N;j++)
if(a[i][j] != b[i][j])
return false;
return true;
}
//输出当前状态
void prin(int a[M][N]){
int i=0,j=0;
for(i=0;i<M;i++){
for(j=0;j<N;j++)
if(a[i][j] == 0)
printf(" ");
else
printf("%d ",a[i][j]);
printf("\n");
}
printf("----------------\n");
}
//判断此状态是否已经存在过了
bool isExist(int a[M][N],int num){
int i,j,q=0,p=1;
int temp[9]={0};
for(i=0;i<M;i++)
for(j=0;j<N;j++){
temp[q] = a[i][j];
q++;
}
for(i=0;i<=num;i++){
if(p == 0) return true;//检查一条，发现全部相同，返回，true
for(j=0;j<9;j++){
//printf("\n----\nc[3][3]is:%d",c[i][j]);
if(c[i][j] == temp[j]){
p=0;
}else{
p=1; //不同，检查下一条
break;
}
}
}
return false;
}
//保存此步状态
int insert(int a[M][N],int num){
int i,j,q=0;
int temp[9]={0};
for(i=0;i<M;i++)
for(j=0;j<N;j++){
temp[q] = a[i][j];
q++;
}
for(j=0;j<9;j++)
c[num][j] = temp[j];
return num+1;
}
