java - 骑士之旅:无法解决

我写了这段代码来打印一个可能的骑士之旅，以便每个地方都被精确访问一次。

public class Main{
         static int move[][]=new int[8][8];
         static int X[]={1 , 2 , 2 , 1 ,-1 ,-2 ,-2,-1};
         static int Y[]={2 , 1 ,-1 ,-2 ,-2 ,-1 , 1, 2};
         static boolean printMove(int x,int y,int step){
   if(step==65){

       return true;
   }
   else{
       int x1,y1;

       for(int l=0;l<8;l++){
           x1=x+X[l];
           y1=y+Y[l];
           if(x1<8&&y1<8&&x1>=0&&y1>=0&&move[x1][y1]==0){

               move[x1][y1]=step;
               if(printMove(x1,y1,step+1)){
                   return true;
               }
               else
               move[x1][y1]=0;


           }
       }
       return false;

   }
}

 static void printSteps(){
       for(int i=0;i<8;i++){
          for(int j=0;j<8;j++){
               System.out.print(move[i][j]+" ");
             }
           System.out.println();
             }
    }
public static void main(String args[]){

     move[0][0]=1;

     printMove(0,0,2);
     printSteps();


   }
}

此代码有效，但以下代码无效，我对X []和Y []所做的改动很小，不会影响算法。

    public class Main{
         static int move[][]=new int[8][8];
         static int X[]={-1, 1 , 2 , 2 , 1 ,-1 ,-2 ,-2};
         static int Y[]={ 2, 2 , 1 ,-1 ,-2 ,-2 ,-1 , 1};
         static boolean printMove(int x,int y,int step){
   if(step==65){

       return true;
   }
   else{
       int x1,y1;

       for(int l=0;l<8;l++){
           x1=x+X[l];
           y1=y+Y[l];
           if(x1<8&&y1<8&&x1>=0&&y1>=0&&move[x1][y1]==0){

               move[x1][y1]=step;
               if(printMove(x1,y1,step+1)){
                   return true;
               }
               else
               move[x1][y1]=0;


           }
       }
       return false;

   }
}

 static void printSteps(){
       for(int i=0;i<8;i++){
          for(int j=0;j<8;j++){
               System.out.print(move[i][j]+" ");
             }
           System.out.println();
             }
    }
public static void main(String args[]){

     move[0][0]=1;

     printMove(0,0,2);
     printSteps();


   }
}

我刚换

         static int X[]={1 , 2 , 2 , 1 ,-1 ,-2 ,-2,-1};
         static int Y[]={2 , 1 ,-1 ,-2 ,-2 ,-1 , 1, 2};

至

         static int X[]={-1, 1 , 2 , 2 , 1 ,-1 ,-2 ,-2};
         static int Y[]={ 2, 2 , 1 ,-1 ,-2 ,-2 ,-1 , 1};

最佳答案

我怀疑发生的是您的第二个程序实际上正常工作。这两个程序都使用蛮力搜索，效率极低，但是第一个程序碰巧很快就绊倒了，而第二个程序却没有。