独立钻石其.txt

独立钻石其

 “独立钻石棋”是起源与法国的一种棋类游戏，具体布局如下：   
  　　　　　　口口口   
  　　　　　　口口口   
  　　　　口口口口口口口   
  　　　　口口口　口口口   
  　　　　口口口口口口口   
  　　　　　　口口口   
  　　　　　　口口口   
  　　行棋规则：每个子只能沿着棋盘上的纵横线“隔子跳”（像跳棋一样，跳过一个相   
  邻的棋子），跳到一个空格处，跳后被跳过的棋子将拿掉。   
  　　这样，棋子跳到最后，无子可再动时，游戏结束。   
  　　当游戏结束时，只剩一个棋子，并且这个棋子落在棋盘的中央，为最佳结果！     
    
    
  独立钻石棋有以下算法：（P43.0一分钟之内算出：）   
  #include   <stdio.h>   
    
  int   map[7][7]={   
  {2,2,1,1,1,2,2},   
  {2,2,1,1,1,2,2},   
  {1,1,1,1,1,1,1},   
  {1,1,1,0,1,1,1},   
  {1,1,1,1,1,1,1},   
  {2,2,1,1,1,2,2},   
  {2,2,1,1,1,2,2}};   
    
  struct   jump   
  {   
          int   x1,y1,x2,y2;   
  }   l[32];   
    
  int   p=0;   
    
  bool   move(int   x1,int   y1,int   x2,int   y2);   
    
  main()   
  {   
          if(!move(1,3,3,3))printf("\nFailure!");   
  }   
    
  bool   move(int   x1,int   y1,int   x2,int   y2)   
  {   
          bool   tmp=false;   
          int   i,j;   
          if(0<=x2&&x2<=7&&0<=y2&&y2<=7&&map[x2][y2]==0&&map[(x1+x2)/2][(y1+y2)/2]==1)   
          {   
                  map[x2][y2]=1;map[x1][y1]=0;map[(x1+x2)/2][(y1+y2)/2]=0;   
                  l[p].x1=x1;l[p].y1=y1;l[p].x2=x2;l[p].y2=y2;p++;   
                  if(p==31&&map[3][3]==1)   
                  {   
                          for(i=0;i<p;i++)   
                          {   
                                  if(i%5==0)printf("\n");   
                                  printf("(%d,%d)->(%d,%d)     ",l[i].x1,l[i].y1,l[i].x2,l[i].y2);   
                          }   
                          tmp=true;   
                  }   
                  for(i=0;i<7&&!tmp;i++)for(j=0;j<7&&!tmp;j++)if(map[i][j]==1)   
                          tmp=move(i,j,i-2,j)||move(i,j,i,j-2)||move(i,j,i+2,j)||move(i,j,i,j+2);   
                  map[x2][y2]=0;map[x1][y1]=1;map[(x1+x2)/2][(y1+y2)/2]=1;p--;   
          }   
          return   tmp;   
  }   
    
  但如果把棋盘变复杂了(加一层)：   
  #include   <iostream.h>   
  int   diamond[9][9]=   
  {{2,2,2,1,1,1,2,2,2}   
  ,{2,2,2,1,1,1,2,2,2}   
  ,{2,2,2,1,1,1,2,2,2}   
  ,{1,1,1,1,1,1,1,1,1}   
  ,{1,1,1,1,0,1,1,1,1}   
  ,{1,1,1,1,1,1,1,1,1}   
  ,{2,2,2,1,1,1,2,2,2}   
  ,{2,2,2,1,1,1,2,2,2}   
  ,{2,2,2,1,1,1,2,2,2}};   
  struct   procession   
  {   
          int   x1,x2,y1,y2;   
  }pro[44];   
  int   p=0;   
  bool   move(int   x1,int   y1,int   x2,int   y2);   
  void   main()   
  {   
          if(!move(2,4,4,4))   
                  cout<<"不存在走法。";   
  }   
  bool   move(int   x1,int   y1,int   x2,int   y2)   
  {   
          bool   flag=false;   
          int   i,j;   
          if(x2>=0&&x2<=9&&y2>=0&&y2<=9&&diamond[x2][y2]==0&&diamond[(x1+x2)/2][(y1+y2)/2]==1)   
          {   
                  diamond[x2][y2]=1;   
                  diamond[x1][y1]=0;   
                  diamond[(x1+x2)/2][(y1+y2)/2]=0;   
                  pro[p].x1=x1;   
                  pro[p].y1=y1;   
                  pro[p].x2=x2;   
                  pro[p].y2=y2;   
                  p++;   
                  if(p==43&&diamond[4][4]==1)   
                  {   
                          for(i=0;i<p;i++)   
                                  cout<<pro[i].x1<<pro[i].y1<<"->"<<pro[i].x2<<pro[i].y2<<endl;   
                          flag=true;   
                  }   
                  for(i=0;i<9&&!flag;i++)   
                          for(j=0;j<9&&!flag;j++)   
                                  if(diamond[i][j]==1)   
                                          flag=move(i,j,i,j-2)||move(i,j,i+2,j)||move(i,j,i,j+2)||move(i,j,i-2,j);   
                  diamond[x2][y2]=0;   
                  diamond[x1][y1]=1;   
                  diamond[(x1+x2)/2][(y1+y2)/2]=1;   
                  p--;   
          }   
          return   flag;   
  }   
  且好久也算不出：   
  大家有办法吗？