|
|
| 贴子作者：王志成 |
发贴日期：2003-2-25 21:21 |
| 阅读次数：1099 |
回复条数：4 |
| 所属版块：计算机与网络 |
最后回复日期：2003-2-26 14:34 |
|
|
|
| 标题：骑士游历(Knight's Tour)问题 |
| 内容： |
|
骑士游历(Knight's Tour)问题：一个骑士（也就是象棋中的“马”）在国际象棋的棋盘(8*8)中从一个点开始移动，问他是否能经过64格中的每一格且每一格只能经过一次。你可以在一张纸上画一个8*8的棋盘自己试一下看你能走多远。
以下是我用java编写的解决这个问题的算法，有兴趣的同学可以研究一下，也不枉我这么辛苦地写注释，这可是有史以来注释写地最详细的一次了，学C的同学可以从actionPerformed()（也就是单击“GO”按钮）开始看起。前面的init()方法是在Applet中加载GUI构件用的，可以不与理会。
李凡希可不可以把他编译后嵌入该页面中。把文件保存为Knight.java(注意大小写)编译后，在网页中插入<applet code="Knight.class" width=290 height=210></applet>代码。
//start of Knight.java
//exercise 7.23 in <java how to program> on page258
//Knight's Tour Knight.java
//data 2003.2.24
/*
**骑士游历(Knight's Tour)问题：一个骑士（也就是象棋中的“马”）
**在国际象棋的棋盘(8*8)中从一个点开始移动，问他是否能经过64格中
**的每一格且每一格只能经过一次。
*/
//import class & package
import javax.swing.JApplet;
import javax.swing.JLabel;
import javax.swing.JButton;
import javax.swing.JTextArea;
import javax.swing.JTextField;
import java.text.DecimalFormat;
import java.awt.Container;
import java.awt.*;
import java.awt.event.*;
public class Knight extends JApplet implements ActionListener{
final int CHESSBOARD_WIDTH = 8; //the width of chessboard
int currentRow, //Knight's current Row
currentColumn, //Knight's current Column
currentStep; //current step
JTextArea outputArea;
JLabel outputLabel,enterLabelX,enterLabelY;
JTextField enterFieldX,enterFieldY;
JButton button;
int accessibility[][]; //the accessibility of every grid , if it >=8 means this grid is go acrossed
int horizontal[] = { 2, 1,-1,-2,-2,-1, 1, 2},
vertical[] = {-1,-2,-2,-1, 1, 2, 2, 1}; //8 kinds of actions
int board[][]; //chessboard status
public void init(){
accessibility = new int[ CHESSBOARD_WIDTH ][ CHESSBOARD_WIDTH ];
board = new int[ CHESSBOARD_WIDTH ][ CHESSBOARD_WIDTH ];
Container c = getContentPane();
c.setLayout( new FlowLayout() );
//add Graphics User Interface to applet
outputLabel = new JLabel( "Please intput your position on the chessboard:");
c.add( outputLabel );
enterLabelX = new JLabel( "X:" );
c.add( enterLabelX );
enterFieldX = new JTextField( 10 );
enterFieldX.setText( "1" );
c.add( enterFieldX );
enterLabelY = new JLabel( "Y:" );
c.add( enterLabelY );
enterFieldY = new JTextField( 10 );
enterFieldY.setText( "1" );
c.add( enterFieldY );
outputArea = new JTextArea( 8,12 );
outputArea.setEditable( false );
c.add( outputArea );
button = new JButton( "GO" );
button.addActionListener( this );
c.add( button );
}
public void actionPerformed( ActionEvent e ){ //while the "GO" button is clicked
boolean flag = true; //the sign of while end
currentRow = Integer.parseInt( enterFieldX.getText() )-1; //get the X value from TextField
currentColumn = Integer.parseInt( enterFieldY.getText() )-1; //get the Y value from TextField
if ( outofBoundary( currentRow,currentColumn ) ) {
showStatus( "You input is out of Boundary, you input mast between 1 to " + CHESSBOARD_WIDTH + ",input again!" );
System.exit(0);
}
//initial valuables
initialBoard();
initialAccessibility();
currentStep = 1;
board[ currentRow ][ currentColumn ] = currentStep; //sign the grid which is go across
modifyAccessibility(); //modify the accessibility table
while ( flag ){
int minimal;
minimal = getMin(); //get the minimal accessibility among the next steps
if ( minimal != -1 )
moveNumber( minimal );
else
flag = false; //no grid to go
if ( currentStep == ( CHESSBOARD_WIDTH * CHESSBOARD_WIDTH ) ) flag = false; //every grid is go acrossed
}
buildOutput();
} //end of actionPerformed
public void initialBoard(){
for( int i=0 ; i<CHESSBOARD_WIDTH ; i++ ){
for ( int l=0 ; l<CHESSBOARD_WIDTH ; l++ ){
board[ i ][ l ] = 0;
} //end of for l
} //end of for i
} // end of initialBoard
public void initialAccessibility(){
int row,column;
for ( int i=0 ; i<CHESSBOARD_WIDTH ; i++ ){
for ( int l=0 ; l<CHESSBOARD_WIDTH ; l++ ){
accessibility[ i ][ l ] = 0;
}
}
for ( int i=0 ; i<CHESSBOARD_WIDTH ; i++ ){
for ( int l=0 ; l<CHESSBOARD_WIDTH ; l++ ){
for( int m=0 ; m<8 ; m++ ){
row = i + vertical[ m ];
column = l + horizontal[ m ];
if ( !outofBoundary( row,column ) )
accessibility[ row ][ column ]++;
} //end of for m
} //end of for l
} //end of for i
} //end of initialAccessibility
public int getMin(){ //get the minimal accessibility among the next steps
int row,column,
i, //the loop variable
min, //the minimal action
minRow, //the row of minimal action
minColumn; //the column of minimal action
for ( i=0 ; i<8 ; i++ ){ //verify is there any grid to go
row = currentRow + vertical[ i ];
column = currentColumn + horizontal[ i ];
if ( !outofBoundary( row,column ) && accessibility[ row ][ column ] <= 8 ) //verify if it can go , if >=8 means it has been go acrossed
break;
} //end of for i
if ( i < 8 ){ //means this grid can be gone
min = i;
minRow = currentRow;
minColumn = currentColumn;
}
else return -1; //i=8 there is no grid can be gone
for ( ; i<8 ; i++ ){ //go on search minimal
row = currentRow + vertical[ i ];
column = currentColumn + horizontal[ i ];
if ( !outofBoundary( row,column ) && ( accessibility[ row ][ column ] < accessibility[ minRow ][ minColumn ] ) ){
min = i;
minRow = row;
minColumn = column;
} //end of if
} //end of for i
return min;
} //end of getMin
public void moveNumber( int moveNum ){ //the knight move from one to another , moveNum is move action code
currentRow += vertical[ moveNum ];
currentColumn += horizontal[ moveNum ];
currentStep++;
board[ currentRow ][ currentColumn ] = currentStep;
modifyAccessibility();
}
public void modifyAccessibility(){ //modify the accessibility for current grid
int row,column;
accessibility[ currentRow ][ currentColumn ] = 100;
for( int i=0 ; i<8 ; i++ ){
row = currentRow + vertical[ i ];
column = currentColumn + horizontal[ i ];
if ( !outofBoundary( row , column ) ){
accessibility[ row ][ column ]--;
} //end of if
} //end of for i
} //end of modifyAccessibility
public boolean outofBoundary( int testRow , int testColumn ){ //verify if testRow,testColumn is out of boundary
if ( testRow < 0 || testRow > CHESSBOARD_WIDTH-1 || testColumn < 0 || testColumn > CHESSBOARD_WIDTH-1 )
return true;
else
return false;
}
public void buildOutput(){
String output = "";
DecimalFormat towDigital = new DecimalFormat( "00" );
for ( int i=0 ; i<CHESSBOARD_WIDTH ; i++ ){
for( int l=0 ; l<CHESSBOARD_WIDTH ; l++ ){
if ( board[ i ][ l ] == 0 )
output += " ";
else
output += towDigital.format( board[ i ][ l ] ) + " ";
} //end of for l
if ( i<CHESSBOARD_WIDTH-1 )output += "\n";
} //end of for i
outputArea.setText( output );
} //end of buildOutput
} //end of class Knight
|
回复：
| 贴子作者：lifanxi |
发贴日期：2003-2-25 22:42 |
已经按你的要求编译了这个程序并放上网，访问网址：
http://asp.6to23.com/szzx/knight.htm
不过这个页面只能在机器上安装了Sun的JDK或JRE，并把它们作为IE的Java插件时才能正常访问，用微软的Java虚拟机是不行的。Sun公司的所谓"Write once, Run everywhere"原来…… |
| 贴子作者：王志成 |
发贴日期：2003-2-26 14:26 |
注：以下网址可以免费下载到SDK和JRE1.4.1版本
http://java.sun.com/j2se/1.4.1/download.html |
| 贴子作者：wangwzc |
发贴日期：2003-2-26 14:33 |
|
Sun公司的"Write once, Run everywhere"前景还是很不错的，只是目前微弱使用了不公平的竞争手段，所以在目前还不能很好的" Run everywhere ".相信以后的版本会有好转，上次SUN公司控告MISCROSOFT垄断案的官司打赢了只后，MISCROSOFT公司必须在以后的版本中加入SUN的相关技术。 |
| 贴子作者：王志成 |
发贴日期：2003-2-26 14:34 |
|
Sun公司的"Write once, Run everywhere"前景还是很不错的，只是目前微弱使用了不公平的竞争手段，所以在目前还不能很好的" Run everywhere ".相信以后的版本会有好转，上次SUN公司控告MISCROSOFT垄断案的官司打赢了只后，MISCROSOFT公司必须在以后的版本中加入SUN的相关技术。 |
您尚未登陆网站，不能回复贴子！
|
|
|
