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