package gao;import java.awt.*;import java.awt.event.*;import javax.swing.*;import java.awt.image.*;public class KnightsTour extends JApplet {   public static int access[][] = {      {2,3,4,4,4,4,3,2},      {3,4,6,6,6,6,4,3},      {4,6,8,8,8,8,6,4},      {4,6,8,8,8,8,6,4},      {4,6,8,8,8,8,6,4},      {4,6,8,8,8,8,6,4},      {3,4,6,6,6,6,4,3},      {2,3,4,4,4,4,3,2}};   // the value indicate the No.value moving   int chessboard [][] = new int[ 8 ][ 8 ];   int countMoving = -1 ;   int tourXpos [] = new int [ 64 ];   int tourYpos [] = new int [ 64 ];   private int tourRecordXpos [][];   private boolean success = false;   public void tour ( int xpos ,int ypos ){//      int x,y;      countMoving ++ ;      //all the  64 squares has been touch , return      if (countMoving == 63 )      {         tourXpos [ countMoving ] = xpos ;         tourYpos [ countMoving ] = ypos ;         success = true ;         countMoving -- ;         return ;      }      AccessibleSquares nextSquare = new AccessibleSquares( xpos, ypos );      while (nextSquare.hasMoreAccessible())      {         // do moving         nextSquare.domoving();         //record this moving         tourXpos [ countMoving ] = xpos ;         tourYpos [ countMoving ] = ypos ;         // try the next moving         nextSquare.nextAccessible();         tour ( nextSquare.getXpos() , nextSquare.getYpos() );         //all the  64 squares has been touch , return         if ( success )         {            countMoving -- ;            return ;         }         //this moving try is a faillure, pick it up from the chess board         nextSquare.undomoving();      }// end of while      countMoving -- ;   }//end of tour method/*   public static void main( String args[] ) {      KnightsTour application = new KnightsTour();      application.tour( 0 , 0 );   }*/   public void init () {      for (int row = 0 ; row < 8 ;row ++){         for ( int column = 0 ; column < 8 ; column ++ ){            success = false ;            countMoving = -1;            tour ( row ,column );         }      }   }   public void paint (Graphics g )   {      super.paint( g );      //draw the cheess board/*      for (int row = 0 ; row < 8 ;row ++){         for ( int column = 0 ; column < 8 ; column ++ ){            success = false ;            tour ( row ,column );         }      }*///      tour ( 7 , 0 );      for ( int row = 0 ; row < 9 ; row ++ )      {         g.drawLine( 10 , 10 + 32 * row , 32 * 8 + 10 , 10 + 32 * row  );      }      for ( int column = 0 ; column < 9 ; column ++ )      {         g.drawLine( 10 + 32 * column , 10  , 10 + 32 * column , 32 * 8 + 10 );      };      for ( int count = 0 ; count < tourXpos.length ; count ++ )      {         g.drawString("" + count , 26 + 32 * tourXpos[ count ] ,32 + 32 * tourYpos [ count ] );      };   ///  BufferedImage white = new BufferedImage ( "white.jpg");   }}//end of class KnightsTourclass AccessibleSquares {   private static int horizontal[] = {2,1,-1,-2,-2,-1,1,2};   private static int vertical  [] = {-1,-2,-2,-1,1,2,2,1};   private int xpos[] ;   private int ypos[] ;   private int accessibility [];   private int ownxpos ,ownypos ;   private int ownAccessibility ;   private int arrayPos ;   private int countAccessibility;   public AccessibleSquares(int x , int y ){      int testXPos;      int testYPos;      xpos = new int [ 8 ];      ypos = new int [ 8 ];      accessibility = new int [ 8 ];      arrayPos = 0 ;      ownxpos = x ;      ownypos = y ;      ownAccessibility = KnightsTour.access[ x ][ y ];      for (int i = 0 ; i < horizontal.length ; i++ ){         testXPos = x + horizontal[ i ];         testYPos = y + vertical  [ i ];         if ( (testXPos >= 0 ) & ( testXPos < 8 ) &              (testYPos >= 0 ) & ( testYPos < 8 ) ) {            xpos [ arrayPos ] = testXPos ;            ypos [ arrayPos ] = testYPos ;            accessibility [ arrayPos ] = KnightsTour.access [testXPos][testYPos];            //because  accessibility [ arrayPos ] = 0 indicating the square has been occupied            if (accessibility [ arrayPos ] > 0 )               arrayPos ++ ;         }//end of if      }// end of for      countAccessibility = arrayPos ;      if (countAccessibility > 0 )         {sortAll();}      arrayPos = -1 ;   }// end of constructor   public boolean hasMoreAccessible(){      // arrayPos + 1 point to the next accessible      if ( (arrayPos + 1 ) < countAccessibility ){         return true;      }else {         return false;      }   }//end of the hasMoreAccessible()   public AccessibleSquares nextAccessible(){      arrayPos ++ ;      return this;   }   public AccessibleSquares accessibleAt( int pos){      if ((pos >= 0) & (pos < countAccessibility ))      arrayPos = pos ;      return this;   }   public int getXpos(){      return xpos[ arrayPos ];   }   public int getYpos(){      return ypos[ arrayPos ];   }   public int getAccessibility(){      return accessibility[ arrayPos ];   }   public int getTotalAccessible(){      return countAccessibility;   }   //bubble sorting   private void sortAll (){      for ( int begin = 0 ; begin < countAccessibility - 1 ; begin ++ ){         for ( int i = begin + 1; i < countAccessibility ; i ++ ){            if ( accessibility [ begin ] > accessibility [ i ] ){               swapAll( begin, i );            }//end of if         }// end of inner for      }// end of outer for   }// end of sortAll   private void swapAll ( int i , int j ){      int temp ;      temp = xpos [ i ];      xpos [ i ] = xpos [ j ];      xpos [ j ] = temp;      temp = ypos [ i ];      ypos [ i ] = ypos [ j ];      ypos [ j ] = temp;      temp = accessibility [ i ];      accessibility [ i ] = accessibility [ j ];      accessibility [ j ] = temp;   }   public void domoving(){      for ( int i = 0 ; i < countAccessibility ; i ++ ){         KnightsTour.access[ xpos [i] ][ ypos[i] ] -- ;      }       KnightsTour.access[ ownxpos ][ ownypos ] = 0 ;   }   public void undomoving(){      for ( int i = 0 ; i < countAccessibility ; i ++ ){         KnightsTour.access[ xpos [i] ][ ypos[i] ] ++ ;      }      KnightsTour.access[ ownxpos ][ ownypos ] = ownAccessibility ;   }}