knightstour.java~1~

这是一个通过java 编程的学生信息管理系统和学籍管理系统

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 KnightsTour

class 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 ;
   }
}