8sm2.c

双向广度优先搜索算法法见8SM2.cpp文件

#include <stdio.h>
#include <math.h>
#include <CONIO.h>
struct bsm
 {
  int s[9];
  int prep,pos;
 } ar1[1000],ar2[1000];
int h1,r1,h2,r2,step;
struct bsm p;
int pd(int k)
{
int i,j,b1,b2;
b1=1;
p.s[p.pos+k]=p.s[p.pos]+p.s[p.pos+k];
p.s[p.pos]=p.s[p.pos+k]-p.s[p.pos];
p.s[p.pos+k]=p.s[p.pos+k]-p.s[p.pos];
p.pos=p.pos+k;
for (i=0;i<=r1;i++)
 {
 b2=0;
 for (j=0;j<9;j++)
  if (!(ar1[i].s[j]==p.s[j])) b2=1;
 b1=b1*b2;
 }
return(b1);
}
int pd0(int k)
{
int i,j,b1,b2;
b1=1;
p.s[p.pos+k]=p.s[p.pos]+p.s[p.pos+k];
p.s[p.pos]=p.s[p.pos+k]-p.s[p.pos];
p.s[p.pos+k]=p.s[p.pos+k]-p.s[p.pos];
p.pos=p.pos+k;
for (i=0;i<=r2;i++)
 {
 b2=0;
 for (j=0;j<9;j++)
  if (!(ar2[i].s[j]==p.s[j])) b2=1;
 b1=b1*b2;
 }
return(b1);
}
int pd1()
{
int i,j,b1,b2;
b1=0;
for (i=h2;i<=r2;i++)
 {
 b2=0;
 for (j=0;j<9;j++)
  if (!(ar2[i].s[j]==p.s[j])) b2=1;
 if (0==b2)
  {
  r2=i;
  b1=1;
  }
 }
return(b1);
}
int pd2()
{
int i,j,b1,b2;
b1=0;
for (i=h1;i<=r1;i++)
 {
 b2=0;
 for (j=0;j<9;j++)
  if (!(ar1[i].s[j]==p.s[j])) b2=1;
 if (0==b2)
  {
  r1=i;
  b1=1;
  }
 }
return(b1);
}
void out1(struct bsm m)
 {
 int i,j;
 step++;
 printf("Step:%d",step);
 for (i=0;i<9;i++)
  {
   if (0==i%3) printf("\n");
   printf("%d ",m.s[i]);
  }
 while (!kbhit());
 i=getch();
 printf("\n");
 }
void out()
{
int i,j,k;
int arr[1000];
j=-1;
while (r1>0)
 {
  j=j+1;
  arr[j]=r1;
  r1=ar1[r1].prep;
 }
j=j+1;
arr[j]=r1;
for (i=j;i>-1;i--)
 {
  out1(ar1[arr[i]]);
 }
while (r2>0)
 {
  out1(ar2[ar2[r2].prep]);
  r2=ar2[r2].prep;
 }
}
void main()
{
int i,j;
step=0;
for (i=0;i<9;i++)
 {
 ar1[0].s[i]=(i+1)%9;
 scanf("%d",&ar2[0].s[i]);
 if (0==ar2[0].s[i]) ar2[0].pos=i;
 }
ar1[0].pos=8;
ar1[0].prep=-1;
ar2[0].prep=-1;
h1=0;r1=0;h2=0;r2=0;
while(((h1<=r1)&&(r1<999))||((h2<=r2)&&(r2<999)))
 {
 if ((h1<=r1)&&(r1<999))
  {
   p=ar1[h1];
   if (p.pos>2)
    {
    if (1==pd(-3))
     {
      p.prep=h1;
      r1++;
      ar1[r1]=p;
      if (1==pd1())
      {
       out();return;
      }
     }
    }
   p=ar1[h1];
   if (p.pos%3>0)
    {
    if (1==pd(-1))
     {
      p.prep=h1;
      r1++;
      ar1[r1]=p;
      if (1==pd1())
      {
       out();return;
      }
     }
    }
   p=ar1[h1];
   if (p.pos<6)
    {
    if (1==pd(3))
     {
      p.prep=h1;
      r1++;
      ar1[r1]=p;
      if (1==pd1())
      {
       out();return;
      }
     }
    }
   p=ar1[h1];
   if (p.pos%3<2)
    {
    if (1==pd(1))
     {
      p.prep=h1;
      r1++;
      ar1[r1]=p;
      if (1==pd1())
      {
       out();return;
      }
     }
    }
   h1++;
  }
 if ((h2<=r2)&&(r2<999))
  {
   p=ar2[h2];
   if (p.pos>2)
    {
    if (1==pd0(-3))
     {
      p.prep=h2;
      r2++;
      ar2[r2]=p;
      if (1==pd2())
      {
       out();return;
      }
     }
    }
   p=ar2[h2];
   if (p.pos%3>0)
    {
    if (1==pd0(-1))
     {
      p.prep=h2;
      r2++;
      ar2[r2]=p;
      if (1==pd2())
      {
       out();return;
      }
     }
    }
   p=ar2[h2];
   if (p.pos<6)
    {
    if (1==pd0(3))
     {
      p.prep=h2;
      r2++;
      ar2[r2]=p;
      if (1==pd2())
      {
       out();return;
      }
     }
    }
   p=ar2[h2];
   if (p.pos%3<2)
    {
    if (1==pd0(1))
     {
      p.prep=h2;
      r2++;
      ar2[r2]=p;
      if (1==pd2())
      {
       out();return;
      }
     }
    }
   h2++;
  }
 }
 if (step==0) printf("I cannot find the answer!");
}