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

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.                myPanel.showNext() ;
  125.             }
  126.          }
  127.          );//end call to addActionListener
  128.          nextTour.addActionListener(
  129.             //anonymous inner class
  130.             new ActionListener() {
  131.                public void actionPerformed ( ActionEvent e ) {
  132.                   if ( recordCount < recordXpos.length - 1 ) {
  133.                      recordCount ++ ;
  134.                   } else {
  135.                      recordCount = 0 ;
  136.                   }
  137.                   myPanel.initboard ( recordXpos [ recordCount ] , recordYpos [ recordCount ] );
  138.                   myPanel.repaint();
  139.                }
  140.             }
  141.             );//end call to addActionListener
  142.    }
  143.    public void paint (Graphics g )
  144.    {
  145.       super.paint( g );
  146. /*      success = false ;
  147.       countMoving = -1;
  148.       access = arrayCopy ( accessbak );
  149.       tour ( 7 , 6 );
  150.       for ( int row = 0 ; row < 9 ; row ++ )
  151.       {
  152.          g.drawLine( 10 , 10 + 32 * row , 32 * 8 + 10 , 10 + 32 * row  );
  153.       }
  154.       for ( int column = 0 ; column < 9 ; column ++ )
  155.       {
  156.          g.drawLine( 10 + 32 * column , 10  , 10 + 32 * column , 32 * 8 + 10 );
  157.       };
  158.       for ( int count = 0 ; count < tourXpos.length ; count ++ )
  159.       {
  160.          g.drawString("" + count , 26 + 32 * tourXpos[ count ] ,32 + 32 * tourYpos [ count ] );
  161.       };*/
  162.    }
  163. }//end of class KnightsTour
  164. class AccessibleSquares {
  165.    private static int horizontal[] = {2,1,-1,-2,-2,-1,1,2};
  166.    private static int vertical  [] = {-1,-2,-2,-1,1,2,2,1};
  167.    private int xpos[] ;
  168.    private int ypos[] ;
  169.    private int accessibility [];
  170.    private int ownxpos ,ownypos ;
  171.    private int ownAccessibility ;
  172.    private int arrayPos ;
  173.    private int countAccessibility;
  174.    public AccessibleSquares(int x , int y ){
  175.       int testXPos;
  176.       int testYPos;
  177.       xpos = new int [ 8 ];
  178.       ypos = new int [ 8 ];
  179.       accessibility = new int [ 8 ];
  180.       arrayPos = 0 ;
  181.       ownxpos = x ;
  182.       ownypos = y ;
  183.       ownAccessibility = KnightsTour.access[ x ][ y ];
  184.       for (int i = 0 ; i < horizontal.length ; i++ ){
  185.          testXPos = x + horizontal[ i ];
  186.          testYPos = y + vertical  [ i ];
  187.          if ( (testXPos >= 0 ) & ( testXPos < 8 ) &
  188.               (testYPos >= 0 ) & ( testYPos < 8 ) ) {
  189.             xpos [ arrayPos ] = testXPos ;
  190.             ypos [ arrayPos ] = testYPos ;
  191.             accessibility [ arrayPos ] = KnightsTour.access [testXPos][testYPos];
  192.             //because  accessibility [ arrayPos ] = 0 indicating the square has been occupied
  193.             if (accessibility [ arrayPos ] > 0 )
  194.                arrayPos ++ ;
  195.          }//end of if
  196.       }// end of for
  197.       countAccessibility = arrayPos ;
  198.       if (countAccessibility > 0 )
  199.          {sortAll();}
  200.       arrayPos = -1 ;
  201.    }// end of constructor
  202.    public boolean hasMoreAccessible(){
  203.       // arrayPos + 1 point to the next accessible
  204.       if ( (arrayPos + 1 ) < countAccessibility ){
  205.          return true;
  206.       }else {
  207.          return false;
  208.       }
  209.    }//end of the hasMoreAccessible()
  210.    public AccessibleSquares nextAccessible(){
  211.       arrayPos ++ ;
  212.       return this;
  213.    }
  214.    public AccessibleSquares accessibleAt( int pos){
  215.       if ((pos >= 0) & (pos < countAccessibility ))
  216.       arrayPos = pos ;
  217.       return this;
  218.    }
  219.    public int getXpos(){
  220.       return xpos[ arrayPos ];
  221.    }
  222.    public int getYpos(){
  223.       return ypos[ arrayPos ];
  224.    }
  225.    public int getAccessibility(){
  226.       return accessibility[ arrayPos ];
  227.    }
  228.    public int getTotalAccessible(){
  229.       return countAccessibility;
  230.    }
  231.    //bubble sorting
  232.    private void sortAll (){
  233.       for ( int begin = 0 ; begin < countAccessibility - 1 ; begin ++ ){
  234.          for ( int i = begin + 1; i < countAccessibility ; i ++ ){
  235.             if ( accessibility [ begin ] > accessibility [ i ] ){
  236.                swapAll( begin, i );
  237.             }//end of if
  238.          }// end of inner for
  239.       }// end of outer for
  240.    }// end of sortAll
  241.    private void swapAll ( int i , int j ){
  242.       int temp ;
  243.       temp = xpos [ i ];
  244.       xpos [ i ] = xpos [ j ];
  245.       xpos [ j ] = temp;
  246.       temp = ypos [ i ];
  247.       ypos [ i ] = ypos [ j ];
  248.       ypos [ j ] = temp;
  249.       temp = accessibility [ i ];
  250.       accessibility [ i ] = accessibility [ j ];
  251.       accessibility [ j ] = temp;
  252.    }
  253.    public void domoving(){
  254.       for ( int i = 0 ; i < countAccessibility ; i ++ ){
  255.          KnightsTour.access[ xpos [i] ][ ypos[i] ] -- ;
  256.       }
  257.        KnightsTour.access[ ownxpos ][ ownypos ] = 0 ;
  258.    }
  259.    public void undomoving(){
  260.       for ( int i = 0 ; i < countAccessibility ; i ++ ){
  261.          KnightsTour.access[ xpos [i] ][ ypos[i] ] ++ ;
  262.       }
  263.       KnightsTour.access[ ownxpos ][ ownypos ] = ownAccessibility ;
  264.    }
  265. }
  266. class MyPanel extends JPanel {
  267.    public static final int WHITE = 0 ;
  268.    public static final int BLACK = 1 ;
  269.    public static final int WKNIGHT = 2 ;
  270.    public static final int BKNIGHT = 3 ;
  271.    private int chessboard[][];
  272.    private int xrecord [] ;
  273.    private int yrecord [] ;
  274.    private int displayCount ;
  275.    private int lastxpos ,lastypos ,nextxpos ,nextypos ;
  276.    ImageIcon images[] ;
  277.    private boolean start ;
  278.    public MyPanel() {
  279.       initvariance();
  280.    }
  281.    public MyPanel( int [] newxrecord ,int [] newyrecord ) {
  282.       initvariance();
  283.       initboard( newxrecord , newyrecord );
  284.    }
  285.    public void initvariance () {
  286.       chessboard = new int[ 8 ][ 8 ];
  287.       xrecord = new int [ 64 ] ;
  288.       yrecord = new int [ 64 ];
  289.       images = new ImageIcon [ 4 ];
  290.       images[ 0 ] = new ImageIcon( "white.jpg");
  291.       images[ 1 ] = new ImageIcon( "black.jpg");
  292.       images[ 2 ] = new ImageIcon( "wknight.jpg");
  293.       images[ 3 ] = new ImageIcon( "bknight.jpg");
  294.    }
  295.    public void initboard ( int [] newxrecord ,int [] newyrecord ){
  296.       start = true ;
  297.       displayCount = -1 ;
  298.       for (int row = 0 ; row < 8 ;row ++){
  299.          for ( int column = 0 ; column < 8 ; column ++ ){
  300.             // white use 0 ,black use 1
  301.             chessboard [ row ][ column ] = ( row + column ) % 2 ;
  302.          }
  303.       }//end of outer for
  304.       for ( int row = 0 ; row < newxrecord .length ; row ++ ) {
  305.          xrecord [ row ] = newxrecord [ row ] ;
  306.          yrecord [ row ] = newyrecord [ row ] ;
  307.       }
  308.       displayCount = 0 ;
  309.       chessboard [ xrecord [ displayCount ] ][ yrecord [ displayCount ] ] += 2 ;
  310.    }//end of initboard
  311.    public void showNext() {
  312.       if ( displayCount < xrecord.length - 1 ){
  313.          displayCount ++ ;
  314.          chessboard [ xrecord [ displayCount ] ][ yrecord [ displayCount ] ] += 2 ;
  315.          repaint();
  316.       }
  317.    }
  318.    public void paintComponent ( Graphics g ) {
  319.       for (int row = 0 ; row < 8 ;row ++){
  320.          for ( int column = 0 ; column < 8 ; column ++ ){
  321.             images[ chessboard[ row ][ column ] ].paintIcon( this , g, 40 * row,40 * column );
  322.          }//end of inner for
  323.       }//end of outer for
  324.       if ( displayCount > 0 ){
  325.          lastxpos = xrecord [ displayCount  - 1];
  326.          lastypos = yrecord [ displayCount  - 1];
  327.          nextxpos = xrecord [ displayCount ];
  328.          nextypos = yrecord [ displayCount ];
  329.          g.setColor( Color.green);
  330.          g.drawRect( 40 * xrecord [ displayCount - 1 ] + 2,40 * yrecord [ displayCount - 1 ] + 2, 36, 36 );
  331.          g.setColor( Color.green);
  332.          g.drawRect( 40 * xrecord [ displayCount ] + 2 ,40 * yrecord [ displayCount ] + 2, 36, 36 );
  333.          g.setColor( Color.blue);
  334.          g.drawRect( 40 * Math.min( nextxpos, lastxpos ),
  335.             40 * Math.min( nextypos, lastypos ),
  336.             ( Math.abs( nextxpos - lastxpos ) + 1 ) * 40,
  337.             ( Math.abs( nextypos - lastypos ) + 1 ) * 40 );
  338.       }//end of if
  339.       g.setColor( Color.red );
  340.       g.drawRect ( 40 * xrecord [ 0 ] + 2,40 * yrecord [ 0 ] + 2, 36, 36 ) ;
  341.    }// end of the method paintComponent
  342. }