注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

易拉罐的博客

心静自然凉

 
 
 

日志

 
 

转 八数码问题程序实现  

2011-01-04 22:52:52|  分类: 人工智能 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

问题描述:
有一个3*3的棋盘,其中有0-8 9个数字,0表示空格,其他的数字可以和0交换位置。求由初始状态
1 2 3
4 5 6
7 8 0
到达目标状态步数最少的解。
输入方法:
例如:
input(从键盘):
1 2 3 7 4 5 8 0 6
output(向屏幕):
Step:1
1 2 3
4 5 6
7 8 0
Step:2
1 2 3
4 5 0
7 8 6
Step:3
1 2 3
4 0 5
7 8 6
Step:4
1 2 3
0 4 5
7 8 6
Step:5
1 2 3
7 4 5
0 8 6
Step:6
1 2 3
7 4 5
8 0 6
程序:
#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!");
}

  评论这张
 
阅读(291)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017