KnightsTour.java~60~
上传用户:liming9091
上传日期:2014-10-27
资源大小:3376k
文件大小:11k
源码类别:

Java编程

开发平台:

Java

  1. package gao;
  2. import java.awt.*;
  3. import java.awt.event.*;
  4. import javax.swing.*;
  5. import java.awt.image.*;
  6. public class KnightsTour extends JApplet {
  7.    public static int access[][] = {
  8.       {2,3,4,4,4,4,3,2},
  9.       {3,4,6,6,6,6,4,3},
  10.       {4,6,8,8,8,8,6,4},
  11.       {4,6,8,8,8,8,6,4},
  12.       {4,6,8,8,8,8,6,4},
  13.       {4,6,8,8,8,8,6,4},
  14.       {3,4,6,6,6,6,4,3},
  15.       {2,3,4,4,4,4,3,2}};
  16.    public static int accessbak[][] = arrayCopy ( access ) ;
  17.    // the value indicate the No.value moving
  18.    int countMoving = -1 ;
  19.    int tourXpos [] = new int [ 64 ];
  20.    int tourYpos [] = new int [ 64 ];
  21.    private int recordXpos [][];
  22.    private int recordYpos [][];
  23.    private int recordCount = - 1 ;
  24.    private boolean success = false;
  25.    MyPanel myPanel ;
  26.    public void tour ( int xpos ,int ypos ){
  27. //      int x,y;
  28.       countMoving ++ ;
  29.       //all the  64 squares has been touch , return
  30.       if (countMoving == 63 )
  31.       {
  32.          tourXpos [ countMoving ] = xpos ;
  33.          tourYpos [ countMoving ] = ypos ;
  34.          success = true ;
  35.          countMoving -- ;
  36.          return ;
  37.       }
  38.       AccessibleSquares nextSquare = new AccessibleSquares( xpos, ypos );
  39.       while (nextSquare.hasMoreAccessible())
  40.       {
  41.          // do moving
  42.          nextSquare.domoving();
  43.          //record this moving
  44.          tourXpos [ countMoving ] = xpos ;
  45.          tourYpos [ countMoving ] = ypos ;
  46.          // try the next moving
  47.          nextSquare.nextAccessible();
  48.          tour ( nextSquare.getXpos() , nextSquare.getYpos() );
  49.          //all the  64 squares has been touch , return
  50.          if ( success )
  51.          {
  52.             countMoving -- ;
  53.             return ;
  54.          }
  55.          //this moving try is a faillure, pick it up from the chess board
  56.          nextSquare.undomoving();
  57.       }// end of while
  58.       countMoving -- ;
  59.    }//end of tour method
  60.    public static int[] arrayCopy ( int array1[] )
  61.    {
  62.      int[]array2 = new int [array1.length];
  63.      for ( int row = 0 ; row < array1.length ; row ++ )
  64.      {
  65.           array2 [ row ] = array1  [ row ] ;
  66.      };
  67.      return array2;
  68.    }
  69.    public static int[][] arrayCopy ( int array1[][]  )
  70.    {
  71.       int[][] array2 = new int [array1.length][array1[0].length];
  72.      for ( int row = 0 ; row < array1.length ; row ++ )
  73.      {
  74.         for ( int column = 0 ; column < array1[0].length ; column ++ )
  75.         {
  76.           array2 [ row ][ column ] = array1  [ row ][ column ];
  77.         };
  78.      };
  79.      return array2;
  80.    }
  81.    public void initialArray ( int chessBoard[][]  )
  82.    {
  83.      for ( int row = 0 ; row < 8 ; row ++ )
  84.      {
  85.         for ( int column = 0 ; column < 8 ; column ++ )
  86.         {
  87.           chessBoard [ row ][ column ] = 0 ;
  88.         };
  89.      };
  90.    }
  91. /*   public static void main( String args[] ) {
  92.       KnightsTour application = new KnightsTour();
  93.       application.tour( 0 , 0 );
  94.    }
  95. */
  96.    public void init () {
  97.       recordCount = -1 ;
  98.       recordXpos = new int [ 64 ][ 64 ] ;
  99.       recordYpos = new int [ 64 ][ 64 ] ;
  100.       for (int row = 0 ; row < 8 ;row ++){
  101.          for ( int column = 0 ; column < 8 ; column ++ ){
  102.             success = false ;
  103.             countMoving = -1;
  104.             access = arrayCopy ( accessbak );
  105.             tour ( row ,column );
  106.             recordCount ++ ;
  107.             recordXpos [ recordCount ] = arrayCopy ( tourXpos ) ;
  108.             recordYpos [ recordCount ] = arrayCopy ( tourYpos ) ;
  109.          }
  110.       }
  111.       recordCount = -1 ;
  112.       myPanel = new MyPanel( recordXpos [ 0 ] ,recordYpos [ 0 ]) ;
  113.       JPanel buttonPanel = new JPanel();
  114.       JButton nextMoving = new JButton( "Next Moving" );
  115.       JButton nextTour = new JButton( "Next Tour" );
  116.       buttonPanel.add( nextTour );
  117.       buttonPanel.add( nextMoving );
  118.       getContentPane().add( buttonPanel, BorderLayout.SOUTH );
  119.       getContentPane().add( myPanel );
  120.       nextMoving.addActionListener(
  121.          //anonymous inner class
  122.          new ActionListener() {
  123.             public void actionPerformed ( ActionEvent e ) {
  124.             }
  125.          }
  126.          );//end call to addActionListener
  127.          nextTour.addActionListener(
  128.             //anonymous inner class
  129.             new ActionListener() {
  130.                public void actionPerformed ( ActionEvent e ) {
  131.                   if ( recordCount < recordXpos.length - 1 ) {
  132.                      recordCount ++ ;
  133.                   } else {
  134.                      recordCount = 0 ;
  135.                   }
  136.                   myPanel.initboard ( recordXpos [ recordCount ] , recordYpos [ recordCount ] );
  137.                   myPanel.showNext() ;
  138.                }
  139.             }
  140.             );//end call to addActionListener
  141.    }
  142.    public void paint (Graphics g )
  143.    {
  144.       super.paint( g );
  145. /*      success = false ;
  146.       countMoving = -1;
  147.       access = arrayCopy ( accessbak );
  148.       tour ( 7 , 6 );
  149.       for ( int row = 0 ; row < 9 ; row ++ )
  150.       {
  151.          g.drawLine( 10 , 10 + 32 * row , 32 * 8 + 10 , 10 + 32 * row  );
  152.       }
  153.       for ( int column = 0 ; column < 9 ; column ++ )
  154.       {
  155.          g.drawLine( 10 + 32 * column , 10  , 10 + 32 * column , 32 * 8 + 10 );
  156.       };
  157.       for ( int count = 0 ; count < tourXpos.length ; count ++ )
  158.       {
  159.          g.drawString("" + count , 26 + 32 * tourXpos[ count ] ,32 + 32 * tourYpos [ count ] );
  160.       };*/
  161.    }
  162. }//end of class KnightsTour
  163. class AccessibleSquares {
  164.    private static int horizontal[] = {2,1,-1,-2,-2,-1,1,2};
  165.    private static int vertical  [] = {-1,-2,-2,-1,1,2,2,1};
  166.    private int xpos[] ;
  167.    private int ypos[] ;
  168.    private int accessibility [];
  169.    private int ownxpos ,ownypos ;
  170.    private int ownAccessibility ;
  171.    private int arrayPos ;
  172.    private int countAccessibility;
  173.    public AccessibleSquares(int x , int y ){
  174.       int testXPos;
  175.       int testYPos;
  176.       xpos = new int [ 8 ];
  177.       ypos = new int [ 8 ];
  178.       accessibility = new int [ 8 ];
  179.       arrayPos = 0 ;
  180.       ownxpos = x ;
  181.       ownypos = y ;
  182.       ownAccessibility = KnightsTour.access[ x ][ y ];
  183.       for (int i = 0 ; i < horizontal.length ; i++ ){
  184.          testXPos = x + horizontal[ i ];
  185.          testYPos = y + vertical  [ i ];
  186.          if ( (testXPos >= 0 ) & ( testXPos < 8 ) &
  187.               (testYPos >= 0 ) & ( testYPos < 8 ) ) {
  188.             xpos [ arrayPos ] = testXPos ;
  189.             ypos [ arrayPos ] = testYPos ;
  190.             accessibility [ arrayPos ] = KnightsTour.access [testXPos][testYPos];
  191.             //because  accessibility [ arrayPos ] = 0 indicating the square has been occupied
  192.             if (accessibility [ arrayPos ] > 0 )
  193.                arrayPos ++ ;
  194.          }//end of if
  195.       }// end of for
  196.       countAccessibility = arrayPos ;
  197.       if (countAccessibility > 0 )
  198.          {sortAll();}
  199.       arrayPos = -1 ;
  200.    }// end of constructor
  201.    public boolean hasMoreAccessible(){
  202.       // arrayPos + 1 point to the next accessible
  203.       if ( (arrayPos + 1 ) < countAccessibility ){
  204.          return true;
  205.       }else {
  206.          return false;
  207.       }
  208.    }//end of the hasMoreAccessible()
  209.    public AccessibleSquares nextAccessible(){
  210.       arrayPos ++ ;
  211.       return this;
  212.    }
  213.    public AccessibleSquares accessibleAt( int pos){
  214.       if ((pos >= 0) & (pos < countAccessibility ))
  215.       arrayPos = pos ;
  216.       return this;
  217.    }
  218.    public int getXpos(){
  219.       return xpos[ arrayPos ];
  220.    }
  221.    public int getYpos(){
  222.       return ypos[ arrayPos ];
  223.    }
  224.    public int getAccessibility(){
  225.       return accessibility[ arrayPos ];
  226.    }
  227.    public int getTotalAccessible(){
  228.       return countAccessibility;
  229.    }
  230.    //bubble sorting
  231.    private void sortAll (){
  232.       for ( int begin = 0 ; begin < countAccessibility - 1 ; begin ++ ){
  233.          for ( int i = begin + 1; i < countAccessibility ; i ++ ){
  234.             if ( accessibility [ begin ] > accessibility [ i ] ){
  235.                swapAll( begin, i );
  236.             }//end of if
  237.          }// end of inner for
  238.       }// end of outer for
  239.    }// end of sortAll
  240.    private void swapAll ( int i , int j ){
  241.       int temp ;
  242.       temp = xpos [ i ];
  243.       xpos [ i ] = xpos [ j ];
  244.       xpos [ j ] = temp;
  245.       temp = ypos [ i ];
  246.       ypos [ i ] = ypos [ j ];
  247.       ypos [ j ] = temp;
  248.       temp = accessibility [ i ];
  249.       accessibility [ i ] = accessibility [ j ];
  250.       accessibility [ j ] = temp;
  251.    }
  252.    public void domoving(){
  253.       for ( int i = 0 ; i < countAccessibility ; i ++ ){
  254.          KnightsTour.access[ xpos [i] ][ ypos[i] ] -- ;
  255.       }
  256.        KnightsTour.access[ ownxpos ][ ownypos ] = 0 ;
  257.    }
  258.    public void undomoving(){
  259.       for ( int i = 0 ; i < countAccessibility ; i ++ ){
  260.          KnightsTour.access[ xpos [i] ][ ypos[i] ] ++ ;
  261.       }
  262.       KnightsTour.access[ ownxpos ][ ownypos ] = ownAccessibility ;
  263.    }
  264. }
  265. class MyPanel extends JPanel {
  266.    public static final int WHITE = 0 ;
  267.    public static final int BLACK = 1 ;
  268.    public static final int WKNIGHT = 2 ;
  269.    public static final int BKNIGHT = 3 ;
  270.    private int chessboard[][];
  271.    private int xrecord [] ;
  272.    private int yrecord [] ;
  273.    private int displayCount ;
  274.    private int lastxpos ,lastypos ,nextxpos ,nextypos ;
  275.    ImageIcon images[] ;
  276.    private boolean start ;
  277.    public MyPanel() {
  278.       initvariance();
  279.    }
  280.    public MyPanel( int [] newxrecord ,int [] newyrecord ) {
  281.       initvariance();
  282.       initboard( newxrecord , newyrecord );
  283.    }
  284.    public void initvariance () {
  285.       chessboard = new int[ 8 ][ 8 ];
  286.       xrecord = new int [ 64 ] ;
  287.       yrecord = new int [ 64 ];
  288.       images = new ImageIcon [ 4 ];
  289.       images[ 0 ] = new ImageIcon( "white.jpg");
  290.       images[ 1 ] = new ImageIcon( "black.jpg");
  291.       images[ 2 ] = new ImageIcon( "wknight.jpg");
  292.       images[ 3 ] = new ImageIcon( "bknight.jpg");
  293.    }
  294.    public void initboard ( int [] newxrecord ,int [] newyrecord ){
  295.       start = true ;
  296.       displayCount = -1 ;
  297.       for (int row = 0 ; row < 8 ;row ++){
  298.          for ( int column = 0 ; column < 8 ; column ++ ){
  299.             // white use 0 ,black use 1
  300.             chessboard [ row ][ column ] = ( row + column ) % 2 ;
  301.          }
  302.       }//end of outer for
  303.       for ( int row = 0 ; row < newxrecord .length ; row ++ ) {
  304.          xrecord [ row ] = newxrecord [ row ] ;
  305.          yrecord [ row ] = newyrecord [ row ] ;
  306.       }
  307.       displayCount = 0 ;
  308.       chessboard [ xrecord [ displayCount ] ][ yrecord [ displayCount ] ] += 2 ;
  309.    }//end of initboard
  310.    public void showNext() {
  311.       if ( displayCount < xrecord.length - 1 ){
  312.          displayCount ++ ;
  313.          chessboard [ xrecord [ displayCount ] ][ yrecord [ displayCount ] ] += 2 ;
  314.          repaint();
  315.       }
  316.    }
  317.    public void paintComponent ( Graphics g ) {
  318.       for (int row = 0 ; row < 8 ;row ++){
  319.          for ( int column = 0 ; column < 8 ; column ++ ){
  320.             images[ chessboard[ row ][ column ] ].paintIcon( this , g, 40 * row,40 * column );
  321.          }//end of inner for
  322.       }//end of outer for
  323.       if ( displayCount > 0 ){
  324.          lastxpos = xrecord [ displayCount  - 1];
  325.          lastypos = yrecord [ displayCount  - 1];
  326.          nextxpos = xrecord [ displayCount ];
  327.          nextypos = yrecord [ displayCount ];
  328.          g.setColor( Color.green);
  329.          g.drawRect( 40 * xrecord [ displayCount - 1 ] + 2,40 * yrecord [ displayCount - 1 ] + 2, 36, 36 );
  330.          g.setColor( Color.green);
  331.          g.drawRect( 40 * xrecord [ displayCount ] + 2 ,40 * yrecord [ displayCount ] + 2, 36, 36 );
  332.          g.setColor( Color.blue);
  333.          g.drawRect( 40 * Math.min( nextxpos, lastxpos ),
  334.             40 * Math.min( nextypos, lastypos ),
  335.             ( Math.abs( nextxpos - lastxpos ) + 1 ) * 40,
  336.             ( Math.abs( nextypos - lastypos ) + 1 ) * 40 );
  337.       }//end of if
  338.       g.setColor( Color.red );
  339.       g.drawRect ( xrecord [ 0 ] + 2, yrecord [ 0 ] + 2, 36, 36 ) ;
  340.    }// end of the method paintComponent
  341. }