当前页面位置: » 丰搜网 » 文档中心 » 详细内容
java源代码案例--骑士巡游问题
一个骑士不重复地游历国际象棋棋盘的每一个方格子
摘要
国际象棋提供了许多与它本身并无关系的有趣的娱乐。骑士巡游问题就是其中的一个。这部分的"java游戏与娱乐"向你介绍骑士巡游问题，然后给出一个applet小程序。它能让你观察整个巡游过程。
国际象棋游戏衍生出了许多与它本身无关的有趣的娱乐方式。 这其中的许多种都基于骑士那奇怪的l形移动方式。一个经典的例子就是骑士巡游问题。
骑士巡游问题从十八世纪初开始，就一直吸引着大批的数学家和猜谜狂热者：把一个骑士放在棋盘64个格子中的任何一个上，然后移动骑士经过剩下的63个方格， 每个方格必须经过一次且只能是一次。
版权声明：任何获得matrix授权的网站，转载时请务必保留以下作者信息和链接
作者:jeff friesen；jk88811(作者的blog:http://blog.matrix.org.cn/page/jk88811)
原文:http://www.javaworld.com/javaworld/jw-11-2005/jw-1128-funandgames.html
译文:http://www.matrix.org.cn/resource/article/44/44259_the+knights+tour.html
关键字:knights;tour
本文展示了一个kt(knight’s tour)小程序， 用来演示一个限制版的骑士巡游问题。 骑士并不是从任何一个方格开始， 而是从角落上的四个方格之一开始。这个applet的界面如图1所示：
图1： kt的界面由一个棋盘， 一个选择开始方格的组合框和一个开始游历的按钮组成
在启动巡游之前， 先从组合框中选择骑士开始的角落。 程序响应会让骑士显示在正确的角落上(默认情况下骑士在最左上角)。 然后单击"take the tour"(开始巡游)按钮来开始整个巡游过程。 按钮和组合框在巡游过程中都将被禁止。
巡游过程是怎么样的呢? 图2展现了一系列的线段(轨迹)， 每一个线段都是随着骑士在棋盘的行动从上一个方格的中心到当前方格的中心。
图2： 巡游从左上角开始
现在你已经看到了这个小程序的界面和巡游过程， 让我们开始学习它的源代码吧。
清单1. kt.java
// kt.java
import java.applet.applet;
import java.awt.*;
import java.awt.event.*;
import java.net.url;
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);
lbltitle.setfont (new font ("arial", font.bold, 18));
// 把标签对象加到小程序的面板容器
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对象,用来选择骑士的开始位置（棋盘的四个角落）
//并把它添加到panel中.
final choice c = new choice ();
c.add ("upperleft corner");
c.add ("upperright corner");
//创建choice的item listener,这个监听器按选择结果来重设骑士的开始位置.
c.additemlistener (new itemlistener ()
{
public void itemstatechanged (itemevent e)
{
choice c = (choice) e.getsource ();
if (c.getselectedindex () == 0)
cb.moveknight (1);
else
cb.moveknight (8);
cb.reset ();
}
});
pnl.add (c);
//把panel加入到小程序的面板容器
add (pnl);
//创建一个按钮对象用来开始骑士巡游.
final button btn = new button ("take the tour");
//创建按钮的action listener(动作监听器),用来确定骑士巡游的位置.
//按照规则将骑士从一个位置移动到另一个位置.
actionlistener al;
al = new actionlistener ()
{
public void actionperformed (actionevent e)
{
runnable r;
r = new runnable ()
{
int [] boardpositions1 =
{
1, 18, 33, 50, 60, 54, 64, 47,
32, 15, 5, 11, 17, 34, 49, 59,
53, 63, 48, 31, 16, 6, 12, 2,
19, 25, 42, 57, 51, 61, 55, 40,
23, 8, 14, 4, 10, 27, 44, 38,
21, 36, 46, 29, 35, 41, 58, 52,
62, 56, 39, 24, 7, 13, 3, 9,
26, 43, 37, 22, 28, 45, 30, 20
};
int [] boardpositions2 =
{
8, 23, 40, 55, 61, 51, 57, 42,
25, 10, 4, 14, 24, 39, 56, 62,
52, 58, 41, 26, 9, 3, 13, 7,
22, 32, 47, 64, 54, 60, 50, 33,
18, 1, 11, 5, 15, 30, 45, 35,
20, 37, 43, 28, 38, 48, 63, 53,
59, 49, 34, 17, 2, 12, 6, 16,
31, 46, 36, 19, 29, 44, 27, 21
};
public void run ()
{
cb.reset ();
// thd用来检查用户离开小程序网页
// 以便停止小程序的运行.
for (int i = 0; i < boardpositions1.length &&
thd != null; i++)
{
if (c.getselectedindex () == 0)
cb.moveknight (boardpositions1 [i]);
else
cb.moveknight (boardpositions2 [i]);
try
{
thread.sleep (delay);
}
catch (interruptedexception e2)
{
}
}
c.setenabled (true);
btn.setenabled (true);
}
};
c.setenabled (false);
btn.setenabled (false);
thd = new thread (r);
thd.start ();
}
};
btn.addactionlistener (al);
//添加按钮到小程序面板容器
add (btn);
}
//停止小程序
public void stop ()
{
//用户离开网页时必须停止”骑士巡游”线程
thd = null;
}
}
final class chessboard extends canvas
{
//非白色方格的颜色
private final static color squarecolor = new color (195, 214, 242);
//棋盘方格的尺寸
private final static int squaredim = 40;
//棋盘方格的尺寸（包括黑边框）
private final static int boarddim = 8 * squaredim + 2;
//棋盘左上角的左坐标（x坐标）
private int boardx;
//棋盘左上角的顶坐标(y坐标)
private int boardy;
//棋盘长度
private int width;
// 棋盘宽度
private int height;
// 图像缓冲
private image imbuffer;
// graphics context associated with image buffer.
private graphics img;
// 骑士图像
private image imknight;
// 骑士图像的长度
private int knightwidth;
// 骑士图像的宽度
private int knightheight;
//骑士轨迹的坐标
private arraylist trail;
// left coordinate of knight rectangle origin (upper-left corner).
private int ox;
// top coordinate of knight rectangle origin (upper-left corner).
private int oy;
// 创建chessboard的applet--调用它的getimage()和getdocumentbase()方法,
// 并且我们将使用它作为drawimage()方法的image observer
applet a;
// 构造棋盘
chessboard (applet a)
{
// 确定部件的大小
width = boarddim+1;
height = boarddim+1;
// 初始化棋盘, 使它处于中央
boardx = (width - boarddim) / 2 + 1;
boardy = (height - boarddim) / 2 + 1;
//使用mediatracker来确保骑士图像在我们获取它的长和宽之前被完全导入
mediatracker mt = new mediatracker (this);
// 导入骑士图像
imknight = a.getimage (a.getdocumentbase (), "knight.gif");
mt.addimage (imknight, 0);
try
{
mt.waitforid (0);
}
catch (interruptedexception e) {}
//获得骑士的长度和宽度, 帮助骑士定位于方格中央
knightwidth = imknight.getwidth (a);
knightheight = imknight.getheight (a);
//初始化骑士图像, 使骑士定位于左上角方格的中央
ox = boardx + (squaredim - knightwidth) / 2 + 1;
oy = boardy + (squaredim - knightheight) / 2 + 1;
//创建一个数据结构, 用来保存骑士巡游时的轨迹
trail = new arraylist ();
//保存applet引用以便后面调用drawimage()时使用.
this.a = a;
}
// this method is called when the chessboard component's peer is created.
// the code in this method cannot be called in the chessboard constructor
// because the createimage() method returns null at that point. it doesn't
// return a meaningful value until the chessboard component has been added
// to its container. the addnotify() method is not called until the first
// time chessboard is added to a container.
public void addnotify ()
{
// given this object's canvas "layer" a chance to create a canvas peer.
super.addnotify ();
//创建图像缓冲
imbuffer = createimage (width, height);
//得到图像缓冲的内容。
img = imbuffer.getgraphics ();
}
//当小程序的布局管理器布置它的组件时，会调用这个方法。
//如果可能，组件会显示为首选大小。
public dimension getpreferredsize ()
{
return new dimension (width, height);
}
//移动骑士到指定的棋盘位置。如果位置小于1或大于64则抛出一个异常
public void moveknight (int boardposition)
{
if (boardposition < 1 boardposition > 64)
throw new illegalargumentexception ("invalid board position: " +
boardposition);
int rebasedboardposition = boardposition-1;
int col = rebasedboardposition % 8;
int row = rebasedboardposition / 8;
ox = boardx + col * squaredim + (squaredim - knightwidth) / 2 + 1;
oy = boardy + row * squaredim + (squaredim - knightheight) / 2 + 1;
trail.add (new point (ox + knightwidth / 2, oy + knightheight / 2));
repaint ();
}
//画出所有部件——先棋盘然后是骑士
public void paint (graphics g)
{
//画出棋盘
paintchessboard (img, boardx, boardy);
//画出骑士
paintknight (img, ox, oy);
//画出骑士的轨迹
painttrail (img);
//画出图像缓冲的内容
g.drawimage (imbuffer, 0, 0, this);
}
//画出棋盘——（x, y）是左上角坐标
void paintchessboard (graphics g, int x, int y)
{
// 画出棋盘的边框
g.setcolor (color.black);
g.drawrect (x, y, 8 * squaredim + 1, 8 * squaredim + 1);
//画出棋盘
for (int row = 0; row < 8; row++)
{
g.setcolor (((row & 1) != 0) ? squarecolor : color.white);
for (int col = 0; col < 8; col++)
{
g.fillrect (x + 1 + col * squaredim, y + 1 + row * squaredim,
squaredim, squaredim);
g.setcolor ((g.getcolor () == squarecolor) ? color.white :
squarecolor);
}
}
}
//画出骑士——（x, y）是图片左上角坐标
void paintknight (graphics g, int x, int y)
{
g.drawimage (imknight, x, y, a);
}
//画出骑士的轨迹
void painttrail (graphics g)
{
g.setcolor (color.black);
int len = trail.size ();
if (len == 0)
return;
point pt = (point) trail.get (0);
int ox = pt.x;
int oy = pt.y;
for (int i = 1; i < len; i++)
{
pt = (point) trail.get (i);
g.drawline (ox, oy, pt.x, pt.y);
ox = pt.x;
oy = pt.y;
}
}
//清空arraylist来重设棋盘
public void reset ()
{
trail.clear ();
}
// the awt invokes the update() method in response to the repaint() method
// call that is made as a knight is moved. the default implementation of
// this method, which is inherited from the container class, clears the
// applet's drawing area to the background color prior to calling paint().
// this clearing followed by drawing causes flicker. kt overrides
// update() to prevent the background from being cleared, which eliminates
// the flicker.
public void update (graphics g)
{
paint (g);
}
}
清单1展示了基于抽象窗口工具集(awt)的kt小程序。当然我并没有半点反对
swing的意思——我只是希望让kt集中于awt。
小程序的public void init()方法负责创建程序界面，包含一个chessboard类的实例用来描述一个棋盘。
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<applet code=kt.class width=345 height=435>
</applet>
在我们学习清单1的时候，你可能已经注意到了一个遗漏：你可以从左上角或右上角来开始一次巡游，但是却不能从左下角或右下角开始。我故意漏掉这两个角落来让你去实现它。因为每个巡游过程都反映了另一个，为剩下的巡游指出开始位置应该不会太难。
我还有另外一个练习留给你：在选择组件的item监听器中：为什么指定cb.reset();跟在moveknight()后面呢（参看init()方法）？
回顾国际象棋提供了许多有趣的娱乐，比如说骑士巡游。它要求骑士从任何方格开始，游历剩余的63个方格而不能重复同一个位置。
kt小程序选择了一个简单的实现，限制开始位置为左上角和右上角的方格。在你完成这个小程序之后，请研究一个通用的解决办法使骑士可以从任何方格开始巡游。
关于作者jeff friesen是一个自由作家、软件开发者和教育者。特别擅长于c，c++和
java技术。
相关资源：下载本文的源代码：
http://www.
javaworld.com/
javaworld/jw-11-2005/games/jw-1128-funandgames.zip
matrix-java开发者社区:http://www.matrix.org.cn
