独立钻石跳棋问题 回溯法.txt

７＊７方格去掉四角各四个各

  int   tableai[TABLESIZE][TABLESIZE];   
  int   findn=0;   
  struct   {   
    int   x,y;   
    int   d,res;   
  }history[TABLESIZE*TABLESIZE-16];   
  int   steps=0;   
    
  void   move(int   x,int   y,int   d){   
  tableai[x][y]=NONE_NAIL;   
  switch(d){   
    case   LEFT:tableai[x-1][y]=NONE_NAIL;tableai[x-2][y]=NAIL;break;   
    case   RIGHT:tableai[x+1][y]=NONE_NAIL;tableai[x+2][y]=NAIL;break;   
    case   UP:tableai[x][y-1]=NONE_NAIL;tableai[x][y-2]=NAIL;break;   
    case   DOWN:tableai[x][y+1]=NONE_NAIL;tableai[x][y+2]=NAIL;break;   
  }   
  history[steps].x=x;   
  history[steps].y=y;   
  history[steps].d=d;   
  steps++;   
  }   
  void   demove(int   x,int   y,int   d){   
  tableai[x][y]=NAIL;   
  switch(d){   
    case   LEFT:tableai[x-1][y]=NAIL;tableai[x-2][y]=NONE_NAIL;break;   
    case   RIGHT:tableai[x+1][y]=NAIL;tableai[x+2][y]=NONE_NAIL;break;   
    case   UP:tableai[x][y-1]=NAIL;tableai[x][y-2]=NONE_NAIL;break;   
    case   DOWN:tableai[x][y+1]=NAIL;tableai[x][y+2]=NONE_NAIL;break;   
  }   
  steps--;   
  }   
    
  void   showmove(){   
  int   i;   
  int   t[TABLESIZE][TABLESIZE];   
  redraw();   
  for(i=0;i<TABLESIZE*TABLESIZE;i++)t[0][i]=table[0][i];   
  for(i=0;i<steps;i++){   
  delay(1000);   
  action(history[i].x,history[i].y);   
  switch(history[i].d){   
    case   LEFT:action(history[i].x-2,history[i].y);break;   
    case   RIGHT:action(history[i].x+2,history[i].y);break;   
    case   UP:action(history[i].x,history[i].y-2);break;   
    case   DOWN:action(history[i].x,history[i].y+2);break;   
  }   
  }   
  for(i=0;i<TABLESIZE*TABLESIZE;i++)table[0][i]=t[0][i];   
  getch();   
  }   
  int   teststep(int   x,int   y,int   d){   
  int   i,j=0,k=0;   
  switch(d){   
    case   LEFT:if(x>1&&tableai[x-1][y]==NAIL&&tableai[x-2][y]==NONE_NAIL)j=1;break;   
    case   RIGHT:if(x<TABLESIZE-2&&tableai[x+1][y]==NAIL&&tableai[x+2][y]==NONE_NAIL)j=1;break;   
    case   UP:     if(y>1&&tableai[x][y-1]==NAIL&&tableai[x][y-2]==NONE_NAIL)j=1;break;   
    case   DOWN:if(y<TABLESIZE-2&&tableai[x][y+1]==NAIL&&tableai[x][y+2]==NONE_NAIL)j=1;break;   
  }   
  if(!j)return   0;   
  move(x,y,d);   
  for(i=0;i<TABLESIZE;i++)   
  for(j=0;j<TABLESIZE;j++)   
  if(tableai[i][j]==NAIL){   
  k=teststep(i,j,UP)+   
  teststep(i,j,DOWN)+   
  teststep(i,j,LEFT)+   
  teststep(i,j,RIGHT);   
  }   
  if(steps==(TABLESIZE*TABLESIZE-18))   
  //printf("%d   ",++findn);   
  {showmove();}   
  demove(x,y,d);   
  return   k;   
  }   
  void   franchai(){   
  int   i,j;   
  steps=TABLESIZE*TABLESIZE-17;   
  for(i=0;i<TABLESIZE;i++)   
  for(j=0;j<TABLESIZE;j++){   
  tableai[i][j]=table[i][j];   
  if(tableai[i][j]==NAIL)steps--;   
  }   
  teststep(TABLESIZE/2-2,TABLESIZE/2,RIGHT);   
  }