原创 （c语言）－个拼图游戏－－求拼成需要的最少步骤

背景：

要将以下的一数组

    1    3    0    4

    6    2    7    8

    5    9   10   12

   13   14   11   15

变成以下数组

    1    2    3    4

    5    6    7    8

    9   10   11   12

   13   14   15    0

0代表空

最少需要多少步吗？该怎么走呢？？

那就让电脑告诉我们！！！！！！！！！

以下是我编的c语言：（有点长）

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define SNUM 100
int a[SNUM][SNUM],line,max,NUM;
int c[]={1,0,-1,0},d[]={0,-1,0,1};
int ii[100],jj[100],g,finish=0;
int iii[100],jjj[100];
/**********************从文件中提取数组****************************/
void geta(int (*p)[SNUM])
{FILE *fp;
int b[100],i,j,k=0;
if((fp=fopen("D:\\in.txt","r"))==NULL)
{printf("can't not open the file\n");
 exit(0);
}
while(fscanf(fp,"%d",&b[k])!=EOF)
{
    k++;
}
line=sqrt(k);
k=0;
for(i=0;i<line;i++)
for(j=0;j<line;j++)
{
    p[j]=b[k];
     k++;
}
fclose(fp);
}
/***************判断数组是否满足要求****************************/
int ifright(int (*p)[SNUM])
{ int i,j,n=1,m=1;
for(i=0;i<line;i++)
for(j=0;j<line;j++)
{if(p[j]==n)
    m++;
    n++;
}
if(n==m+1&&p[line-1][line-1]==0)
 return 1;
else
return 0;
}
/****************获取0的行*********************************/
int geti(int (*p)[SNUM])
{int i,j,n;
for(i=0;i<line;i++)
for(j=0;j<line;j++)
if(p[j]==0)
 n=i;
return n;
}
/****************获取0的列***********************************/
int getj(int (*p)[SNUM])
{int i,j,n;
for(i=0;i<line;i++)
for(j=0;j<line;j++)
if(p[j]==0)
n=j;
return n;
}
/*****************向文件中输入二维数组***********************/
void print(int (*p)[SNUM])
{int i,j;
char a='\n';
 FILE *fp1;
 if((fp1=fopen("D:\\out.txt","a"))==NULL)
 {printf("can't create the file\n");
  exit(0);
 }
     for(i=0;i<line;i++)
     {     for(j=0;j<line;j++)
          fprintf(fp1,"%5d",p[j]);
          fputc(a,fp1);
          fputc(a,fp1);
     }
         fclose(fp1);
}
/*****************向文件中输入一维数组*************************/
void printa(int *p)
{int i;
char a='\n';
 FILE *fp2;
 if((fp2=fopen("D:\\out.txt","a"))==NULL)
 {printf("can't create the file\n");
  exit(0);
 }
     for(i=0;i<max-1;i++)
          fprintf(fp2,"%5d",p);
          fputc(a,fp2);
         fclose(fp2);
}
/*****************向文件中输入一个数*************************/
void printc(int n)
{FILE *fp3;
 char a='\n';
 if((fp3=fopen("D:\\out.txt","a"))==NULL)
 {printf("can't create the file\n");
  exit(0);
 }
 fprintf(fp3,"%d",n);
 fputc(a,fp3);
     fclose(fp3);
}
/*****************向文件中输入一字符串***********************/
void printx(char *p)
{FILE *fp3;
 char a='\n';
 if((fp3=fopen("D:\\out.txt","a"))==NULL)
 {printf("can't create the file\n");
  exit(0);
 }
 fputs(p,fp3);
 fputc('\n',fp3);
 fputc('\n',fp3);
 fclose(fp3);
}
/*****************使文件内容清空**********************************/
void clear()
{FILE *fp3;
 if((fp3=fopen("D:\\out.txt","w"))==NULL)
 {printf("can't create the file\n");
  exit(0);
 }
 fclose(fp3);
}
/****************递归函数（主体部分，用了回溯法）******************/
int tray(int (*p)[SNUM],int i,int j,int li,int lj,int num,int max)
{ int q=0,v,u,k,temp,kk;
  if(num<max)
  {  if(ifright(p))
      { print(p);
        printx("要移动的最小步数：");
        printc(num);
        printx("坐标:");
        printa(ii);
        printa(jj);
        for(kk=0;kk<num;kk++)
        {iii[kk]=ii[kk];
         jjj[kk]=jj[kk];
        }
        NUM=num;
      q=1;
      finish=1;
      }
  for(k=0;k<4;k++)
  {u=i+c[k];
   v=j+d[k];
   if(u>=0&&u<line&&v>=0&&v<line)
      { if(u==li&&v==lj)
        continue;
        else
       {p[j]=p[v];
        temp=p[v];
        p[v]=0;
        ii[num]=u;
        jj[num]=v;
        q=tray(p,u,v,i,j,num+1,max);
       if(q=1)
       {p[v]=temp;
       p[j]=0;
       }
   }
       }
  }
  }else
      q=1;
  return q;
}

/****************主函数**********************************/
void main()
{int xi,xj,i,j,k=0;
geta(a);
xi=geti(a);
xj=getj(a);
clear();
printx("the start array is:");
print(a);
printx("the finish array is:");
for(max=0;max<1000;max++)
{ tray(a,xi,xj,xi,xj,0,max);
if(finish==1)
break;
}
printx("the game start!!");
while(k<NUM)
{i=iii[k];
 j=jjj[k];
a[xi][xj]=a[j];
xi=iii[k];
xj=jjj[k];
a[j]=0;
k++;
printx("next:");
print(a);
}
printx("the game over!!");
}

以上是原代码（总共是198行）

结果：（内容在out.txt中）

the start array is:

    1    3    0    4

    6    2    7    8

    5    9   10   12

   13   14   11   15

the finish array is:

    1    2    3    4

    5    6    7    8

    9   10   11   12

   13   14   15    0

要移动的最小步数：

8
坐标:

    0    1    1    2    2    2    3    3
    1    1    0    0    1    2    2    3
the game start!!

next:

    1    0    3    4

    6    2    7    8

    5    9   10   12

   13   14   11   15

next:

    1    2    3    4

    6    0    7    8

    5    9   10   12

   13   14   11   15

next:

    1    2    3    4

    0    6    7    8

    5    9   10   12

   13   14   11   15

next:

    1    2    3    4

    5    6    7    8

    0    9   10   12

   13   14   11   15

next:

    1    2    3    4

    5    6    7    8

    9    0   10   12

   13   14   11   15

next:

    1    2    3    4

    5    6    7    8

    9   10    0   12

   13   14   11   15

next:

    1    2    3    4

    5    6    7    8

    9   10   11   12

   13   14    0   15

next:

    1    2    3    4

    5    6    7    8

    9   10   11   12

   13   14   15    0

the game over!!