Java源代码案例--骑士巡游问题

 展示了一个KT(Knight's Tour)小程序， 用来演示一个限制版的骑士巡游问题。 骑士并不是从任何一个方格开始， 而是从角落上的四个方格之一开始。这个applet的界面如图1所示： 

 

　　 图1： KT的界面由一个棋盘， 一个选择开始方格的组合框和一个开始游历的按钮组成

 

　 　　　　　　　图2： 巡游从左上角开始

　　现在你已经看到了这个小程序的界面和巡游过程， 让我们开始学习它的源代码吧。 |||

　　清单1. KT.java

// KT.java

import java.applet.Applet; 
import java.awt.event.*; 
import java.util.ArrayList;

public class KT extends Applet 
// 线程延迟以毫秒为单位

　public final static int DELAY = 500;

　// 开始骑士巡游线程

　private Thread thd;

　// 初始化小程序

　public void init () 
// 创建一个标签对象来标明小程序的标题

　　Label lblTitle = new Label ("Knight's Tour", Label.CENTER); 

　　// 把标签对象加到小程序的面板容器

　　add (lblTitle);

　　// 创建一个ChessBoard对象,它具有显示一个棋盘、移动骑士到 

　　final ChessBoard cb = new ChessBoard (this);

　　//把ChessBoard对象加入到小程序的面板容器

　　add (cb);

　　// 创建一个Panel对象来保存Label,Choice和按钮对象.

　　Panel pnl = new Panel ();

　　//创建一个标签来标明Choice对象并把它添加到Panel中

　　pnl.add (new Label ("Choose starting position:"));

　　//创建一个Choice对象,用来选择骑士的开始位置（棋盘的四个角落） 
final Choice c = new Choice (); 
c.add ("Upperright corner");

　　//创建Choice的item listener,这个监听器按选择结果来重设骑士的开始位置.

　　c.addItemListener (new ItemListener () 
public void itemStateChanged (ItemEvent e) 
Choice c = (Choice) e.getSource (); 
cb.moveKnight (1); 
cb.moveKnight (8); 
} 
pnl.add (c);

　　//把Panel加入到小程序的面板容器

　　add (pnl);

　　//创建一个按钮对象用来开始骑士巡游.

　　final Button btn = new Button ("Take the Tour");

　　//创建按钮的Action listener(动作监听器),用来确定骑士巡游的位置. 

　　ActionListener al; 
{ 
{ 
r = new Runnable () 
int boardPositions1 = 
1, 18, 33, 50, 60, 54, 64, 47, 
53, 63, 48, 31, 16, 6, 12, 2, 
23, 8, 14, 4, 10, 27, 44, 38, 
62, 56, 39, 24, 7, 13, 3, 9, 
}; 
{ 
25, 10, 4, 14, 24, 39, 56, 62, 
22, 32, 47, 64, 54, 60, 50, 33, 
20, 37, 43, 28, 38, 48, 63, 53, 
31, 46, 36, 19, 29, 44, 27, 21 

　　　　public void run () 
cb.reset (); 
// 以便停止小程序的运行. 
{ 
cb.moveKnight (boardPositions1 [i]); 
cb.moveKnight (boardPositions2 [i]); 
{ 
} 
{ 
} 
btn.setEnabled (true); 
}; 
btn.setEnabled (false); 
thd.start (); 
}; 
//添加按钮到小程序面板容器 
} 

　public void stop () 
//用户离开网页时必须停止"骑士巡游"线程 
} 

　final class ChessBoard extends Canvas 
//非白色方格的颜色 
//棋盘方格的尺寸 
//棋盘方格的尺寸（包括黑边框） 
//棋盘左上角的左坐标（X坐标） 
//棋盘左上角的顶坐标(Y坐标) 
//棋盘长度 
// 棋盘宽度 
// 图像缓冲 
// Graphics context associated with image buffer. 
// 骑士图像 
// 骑士图像的长度 
// 骑士图像的宽度 
//骑士轨迹的坐标 
// Left coordinate of knight rectangle origin (upper-left corner). 
// Top coordinate of knight rectangle origin (upper-left corner). 
// 创建ChessBoard的Applet--调用它的getImage()和getDocumentBase()方法, 

　　Applet a; 
ChessBoard (Applet a) 
// 确定部件的大小 
height = BOARDDIM+1; 
boardx = (width - BOARDDIM) / 2 + 1; 
//使用MediaTracker来确保骑士图像在我们获取它的长和宽之前被完全导入 
// 导入骑士图像 
mt.addImage (imKnight, 0); 
{ 
} 
//获得骑士的长度和宽度, 帮助骑士定位于方格中央 
knightHeight = imKnight.getHeight (a); 
ox = boardx + (SQUAREDIM - knightWidth) / 2 + 1; 
//创建一个数据结构, 用来保存骑士巡游时的轨迹 
//保存applet引用以便后面调用drawImage()时使用. 
} 
// The code in this method cannot be called in the ChessBoard constructor 
// return a meaningful value until the ChessBoard component has been added 
// time ChessBoard is added to a container. 
{ 
super.addNotify (); 
imBuffer = createImage (width, height); 
imG = imBuffer.getGraphics (); 
//当小程序的布局管理器布置它的组件时，会调用这个方法。 
public Dimension getPreferredSize () 
return new Dimension (width, height); 
//移动骑士到指定的棋盘位置。如果位置小于1或大于64则抛出一个异常 
{ 
64) 
int rebasedBoardPosition = boardPosition-1; 
int row = rebasedBoardPosition / 8; 
oy = boardy + row * SQUAREDIM + (SQUAREDIM - knightHeight) / 2 + 1; 
repaint (); 
//画出所有部件--先棋盘然后是骑士 
{ 
paintChessBoard (imG, boardx, boardy); 
paintKnight (imG, ox, oy); 
paintTrail (imG); 
g.drawImage (imBuffer, 0, 0, this); 
//画出棋盘--（x, y）是左上角坐标 
{ 
g.setColor (Color.black); 
//画出棋盘 
{ 
for (int col = 0; col < 8; col++) 
g.fillRect (x + 1 + col * SQUAREDIM, y + 1 + row * SQUAREDIM, 
g.setColor ((g.getColor () == SQUARECOLOR) ? Color.white : SQUARECOLOR); 
} 
//画出骑士--（x, y）是图片左上角坐标 
{ 
} 
void paintTrail (Graphics g) 
g.setColor (Color.black); 
if (len == 0) 
Point pt = (Point) trail.get (0); 
int oy = pt.y; 
{ 
g.drawLine (ox, oy, pt.x, pt.y); 
oy = pt.y; 
} 
public void reset () 
trail.clear (); 
// The AWT invokes the update() method in response to the repaint() method 
// this method, which is inherited from the Container class, clears the 
// This clearing followed by drawing causes flicker. KT overrides 
// the flicker. 
{ 
} 
||| 

　　ChessBoard继承自java.awt.Canvas，从定制的AWT组件中实例化ChessBoard。构造器负责决定各个部件的大小，导入骑士图片，安置左上角为骑士的初始位置和创建一个数据结构来保存骑士巡游的轨迹。程序覆盖了public Dimension getPreferredSize()方法，用来返回组件的大小，通知布局管理器ChessBoard希望在布局操作时维持这些尺寸为首选的大小。

　　我同样也覆盖了public void addNotify()方法，以便createImage()方法被调用时不返回null值。当Canvas（或许我应该说ChessBoard）创建完成时这个方法才返回null。在addNotify() 中调用super.addNotify()后，null不会被返回。

　　public void moveKnight(int boardPosition)方法移动骑士到boardPosition指定的位置上。这个参数必须在1-64的范围内，否则将抛出异常。除了将骑士的图像画在指定位置的中央外，这个方法还将图像的位置保存在前面创建的数据结构中（参看构造器）。public void reset()方法清除数据结构中的内容。如果没有这个方法，连续的巡游将会同时显示以前和新的巡游轨迹。此外，数据结构应该控制大小的增长，避免浪费内存和最终导致内存不足的错误。剩下的方法负责画出棋盘，画出骑士的图像和轨迹。同样，update()方法被覆盖来防止闪烁。

　　编译清单1以后，你应该想运行这个小程序。但是，在你能运行它之前，你必须通过HTML来向小程序查看器（appletviewer）描述我们编写的小程序。清单2提供了所需的HTML

　　清单2. KT.html

 

　　在我们学习清单1的时候，你可能已经注意到了一个遗漏：你可以从左上角或右上角来开始一次巡游，但是却不能从左下角或右下角开始。我故意漏掉这两个角落来让你去实现它。因为每个巡游过程都反映了另一个，为剩下的巡游指出开始位置应该不会太难。 

　　回顾

　　国际象棋提供了许多有趣的娱乐，比如说骑士巡游。它要求骑士从任何方格开始，游历剩余的63个方格而不能重复同一个位置。KT小程序选择了一个简单的实现，限制开始位置为左上角和右上角的方格。在你完成这个小程序之后，请研究一个通用的解决办法使骑士可以从任何方格开始巡游。