用C語言實作八數位問題

#include<stdio.h>

#include<conio.h>

int n,m;

typedef struct Node

{

char matrix[10];

char operate;

char extend;

int  father;

}Node;

char start[10]={"83426517 "};

char end[10]={"1238 4765"};

Node base[4000];

int result[100];

int match()

{

int i;

for(i=0;i<9;i++)

{

  if(base[n-1].matrix[i]!=end[i])

  {

   return 0;

  }

}

return 1;

}

void show()

{

int i=1;

while(m>=0)

{

  int mm=result[m];

  clrscr();

  printf("/n/n/n   http://www.zhensoft.com   ZHEN  SHI  LEI/t/tStep %d",i);

  printf("/n/n/n/n/n/t/t/t%c/t%c/t%c/n",base[mm].matrix[0],base[mm].matrix[1],base[mm].matrix[2]);

  printf("/n/n/t/t/t%c/t%c/t%c/n",base[mm].matrix[3],base[mm].matrix[4],base[mm].matrix[5]);

  printf("/n/n/t/t/t%c/t%c/t%c/n",base[mm].matrix[6],base[mm].matrix[7],base[mm].matrix[8]);

  sleep(1);

  m--;

  i++;

}

}

void leave()

{

n--;

while(base[n].father!=-1)

{

  result[m]=n;

  m++;

  n=base[n].father;

}

result[m]=0;

result[m+1]='/0';

show();

clrscr();

printf("/n/n/n/n/n/n/n/n/n/t/t/t/tThe End/n/n/n/n/n/n/n/n/n/n");

getch();

exit(0);

}

int left(int x)

{

int i,j;

char ch;

for(i=0;i<9;i++)

{

  if(base[x].matrix[i]==' ')

   break;

}

if(i==0||i==3||i==6||i==9)

{

  return 0;

}

for(j=0;j<9;j++)

{

  base[n].matrix[j]=base[x].matrix[j];

}

ch=base[n].matrix[i-1];

base[n].matrix[i-1]=base[n].matrix[i];

base[n].matrix[i]=ch;

base[n].operate='R';

base[n].extend='Y';

base[n].father=x;

base[x].extend='N';

n++;

        if(match(i))

leave();

return 1;

}

int right(int x)

{

int i,j;

char ch;

for(i=0;i<9;i++)

{

  if(base[x].matrix[i]==' ')

   break;

}

if(i==2||i==5||i==8||i==9)

{

  return 0;

}

for(j=0;j<9;j++)

{

  base[n].matrix[j]=base[x].matrix[j];

}

ch=base[n].matrix[i+1];

base[n].matrix[i+1]=base[n].matrix[i];

base[n].matrix[i]=ch;

base[n].operate='L';

base[n].extend='Y';

base[n].father=x;

base[x].extend='N';

n++;

if(match(i))

leave();

return 1;

}

int up(int x)

{

int i,j;

char ch;

for(i=0;i<9;i++)

{

  if(base[x].matrix[i]==' ')

   break;

}

if(i==0||i==1||i==2||i==9)

{

  return 0;

}

for(j=0;j<9;j++)

{

  base[n].matrix[j]=base[x].matrix[j];

}

ch=base[n].matrix[i-3];

base[n].matrix[i-3]=base[n].matrix[i];

base[n].matrix[i]=ch;

base[n].operate='D';

base[n].extend='Y';

base[n].father=x;

base[x].extend='N';

n++;

        if(match(i))

leave();

return 1;

}

int down(int x)

{

int i,j;

char ch;

for(i=0;i<9;i++)

{

  if(base[x].matrix[i]==' ')

   break;

}

if(i==6||i==7||i==8||i==9)

{

  return 0;

}

for(j=0;j<9;j++)

{

  base[n].matrix[j]=base[x].matrix[j];

}

ch=base[n].matrix[i+3];

base[n].matrix[i+3]=base[n].matrix[i];

base[n].matrix[i]=ch;

base[n].operate='U';

base[n].extend='Y';

base[n].father=x;

base[x].extend='N';

n++;

        if(match(i))

leave();

return 1;

}

main()

{

int i;

char a[20],b[20];

n=1;

textcolor(LIGHTGREEN);

clrscr();

printf("Please input the start 9 chars:");

scanf("%s",a);

printf("Please input the end 9 chars:");

scanf("%s",b);

for(i=0;i<9;i++)

{

  if(a[i]=='0')

  {

   start[i]=' ';

   continue;

  }

  if(b[i]=='0')

  {

   end[i]=' ';

   continue;

  }

  start[i]=a[i];

  end[i]=b[i];

}

start[9]='/0';

end[9]='/0';

for(i=0;i<9;i++)

{

  base[0].matrix[i]=start[i];

}

base[0].operate='N';

base[0].extend='Y';

base[0].father=-1;

for(i=0;n<4000;i++)

{

  if(base[i].extend=='Y')

  {

   if(base[i].operate=='L')

   {

    right(i);up(i);down(i);

   }

   if(base[i].operate=='R')

   {

    left(i);up(i);down(i);

   }

   if(base[i].operate=='U')

   {

    left(i);right(i);down(i);

   }

   if(base[i].operate=='D')

   {

    left(i);right(i);up(i);

   }

   if(base[i].operate=='N')

   {

    left(i);right(i);up(i);down(i);

   }

  }

}

}