?? doc.html
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"><HTML><HEAD> <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1"> <META NAME="Author" CONTENT="Markku V鋒鋋ho"> <META NAME="GENERATOR" CONTENT="Mozilla/4.08 [en] (X11; I; Linux 2.2.5 i686) [Netscape]"> <TITLE>Knight's Tour: Documentation</TITLE></HEAD><BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000EF" VLINK="#51188E" ALINK="#FF0000"> <BR> <CENTER><P><IMG SRC="images/knight.gif" ALT="" HSPACE=10 VSPACE=10 NOSAVE HEIGHT=78 WIDTH=78></CENTER><P><BR><BR><P><BR><BR><BR><BR><CENTER><H1>Knight's Tour (TK94KV1)</H1></CENTER><CENTER><H2><A HREF="http://www.helsinki.fi/~vahaaho">Markku Vähäaho</A></H2></CENTER><BLOCKQUOTE> <P><BR><BR><BR> <BR> <BR> <BR> <P>Helsinki, April 19, 1999<BR><A HREF="http://www.cs.helsinki.fi/kurssit/cum_laude/58161-5/tiralab/index.en.html">DataStructures Project</A><BR><A HREF="http://www.helsinki.fi">University of Helsinki</A><BR><A HREF="http://www.cs.helsinki.fi">Department of Computer Science</A><BR>Tutor: Timo Patrikka<BR> <P><HR NOSHADE WIDTH="100%"><H3>Contents</H3><H4><A HREF="#1">1 Instructions for Use</A></H4> <A HREF="#1.1">1.1 Introduction</A><BR> <A HREF="#1.2">1.2 Installation and Compilation</A><BR> <A HREF="#1.3">1.3 Using the Program</A><BR> <A HREF="#1.4"> 1.4 Limitations</A><H4><A HREF="#2">2 Program Structure</A></H4> <A HREF="#2.1">2.1 About the Knight's Tour Quandary</A><BR> <A HREF="#2.2"> 2.2 The Algorithm</A><BR> <A HREF="#2.3">2.3 Class Structure</A><BR> <A HREF="#2.3.1">2.3.1 KnightsTour</A><BR> <A HREF="#2.3.2">2.3.2 KnightThread</A><BR> <A HREF="#2.3.3">2.3.3 GraphicalBoard</A><BR> <A HREF="#2.3.4">2.3.4 BoardListener</A><BR> <A HREF="#2.3.5">2.3.5 KnightBoard</A><BR> <A HREF="#2.4">2.4 Possible improvements</A><H4><A HREF="#3">3 Testing</A></H4> <A HREF="#3.1">3.1 Testing Tool</A><BR> <A HREF="#3.2">3.2 Verifying Individual Classes</A><BR> <A HREF="#3.3">3.3 Test Results</A><P><HR NOSHADE WIDTH="100%"><H2><A NAME="1"></A>1 Instructions for Use</H2></BLOCKQUOTE><BLOCKQUOTE><H4><A NAME="1.1"></A>1.1 Introduction</H4><BLOCKQUOTE>The knight's tour is a puzzle that has amused chess playersthroughout the ages. The goal of the knight is to traverse around the board,landing on each square but once, and finally return to the square it startedfrom. If the board is thought of as a graph, this kind of closed path iscalled a Hamiltonian cycle. It can be proven that there is a closed knight'stour on all boards with an even number of squares and dimensions greaterthan four.<P>The Knight's Tour Applet demonstrates a simple algorithm for findinga knight's tour. The idea is to always jump to the square with least exits,unless that makes some unvisited squares unreachable. This algorithm workssurprisingly well: in the majority of cases the program chooses the rightmoves on first try, without having to back up once. If this fails, allpossibilities are eventually tried in a depth-first manner.<P>The program is implemented as a Java applet that can be run with anybrowser that supports Java 1.1. The board is represented graphically, andcan be resized by dragging the borders with the mouse to any dimensionsbetween five and ten. The starting square can be chosen freely, and theactual search process can be viewed as an animation or skipped to justsee the final solution.</BLOCKQUOTE><H4><A NAME="1.2"></A>1.2 Installation and Compilation</H4><BLOCKQUOTE>The program is an applet that can be run with either a Java1.1-capable browser, such as <A HREF="http://www.netscape.com/download">NetscapeNavigator</A> 4.06 or newer, or the applet viewer that comes with Sun Microsystem's<A HREF="http://www.java.sun.com/products/OV_jdkProduct.html">JavaDevelopment Kit</A> (JDK). The easiest way to try the program is to enableJava in the browser settings and point it to the following URL: <A HREF="http://www.helsinki.fi/~vahaaho/KnightsTour/tour.html">http://www.helsinki.fi/~vahaaho/KnightsTour/tour.html</A>.<P>If you have JDK 1.1 or later installed, you may also download the programalong with the source code as a gzip'd tar package from <A HREF="http://www.helsinki.fi/~vahaaho/KnightsTour/knightstour.tar.gz">http://www.helsinki.fi/~vahaaho/KnightsTour/knightstour.tar.gz</A>.The package contains the following files:<P><TT><A HREF="../../KnightsTour">KnightsTour/</A></TT><BR><TT> <A HREF="../README">README</A></TT><P><TT> <A HREF="../Makefile">Makefile</A></TT><BR><TT> <A HREF="../BoardListener.java">BoardListener.java</A></TT><BR><TT> <A HREF="../GraphicalBoard.java">GraphicalBoard.java</A></TT><BR><TT> <A HREF="../KnightBoard.java">KnightBoard.java</A></TT><BR><TT> <A HREF="../KnightThread.java">KnightThread.java</A></TT><BR><TT> <A HREF="../KnightsTour.java">KnightsTour.java</A></TT><BR><TT> <A HREF="../Test.java">Test.java</A></TT><P><TT> <A HREF="../tour.html">tour.html</A></TT><BR><TT> <A HREF="../knight.gif">knight.gif</A></TT><P><TT> <A HREF=".">doc/</A></TT><BR><TT> <A HREF="doc.html">doc.html</A></TT><BR><TT> <A HREF="overview.html">overview.html</A></TT><BR><TT> ...</TT><BR><TT> <A HREF="images/">images/</A></TT><BR><TT> ...</TT><P>Details of how to install and compile vary, but on Linux and other Unixsystems the following shell commands will do the job:<BLOCKQUOTE><TT>tar -xzvf knightstour.tar.gz</TT><BR><TT>cd KnightsTour</TT><BR><TT>make</TT><BR><TT>appletviewer tour.html</TT></BLOCKQUOTE>The program and documentation are freely distributable and modifiable aslong as credit is given to the original author.</BLOCKQUOTE><H4><A NAME="1.3"></A>1.3 Using the Program</H4><BLOCKQUOTE>The applet presents a friendly graphical user interface thatshould be very easy to use. First, the program asks to choose the startingsquare. Use the mouse to click on a square of your choice. The programthen starts to look for a solution:<CENTER><P><IMG SRC="images/screenshot.gif" ALT="" HSPACE=10 VSPACE=5 NOSAVE HEIGHT=396 WIDTH=278><BR><I>Figure 1. </I>Program running.</CENTER><BR> <P><BR><P>The starting square is shown with a filled blue circle. The currentposition of the knight has a knight image in it, and already visited squareshave yellow circles containing the number of the move. Unvisited squareshave a number printed in red that tells how many exits the square has left;the program chooses the square with least exits first. If the search comesto a dead end, the knight backs up one move at a time. When the searchis completed, the total number of positions tried is shown.<P>The process can be paused with the 'Pause' button and resumed by selectingthe same button again. Animation can be switched on and off using the checkbox,and the board cleared with the 'Clear' button. If the search process islengthy or not of interest, it is a good idea to switch off animation.<P>When searching is not going on, the board can be resized. Moving thecursor over the right or bottom borders changes its shape, meaning thatthe borders may be dragged by pressing and holding the mouse button andmoving the mouse. During dragging, the number of squares in the board isshown in the upper left corner. If the number is odd, it is printed inred, because there are no solutions for such boards. After the drag, theboard is automatically cleared.<P>The program has been tested to find solutions for all even-sized boardsfrom all starting squares, as should be the case. On symmetrical even-sizedboards the number of positions tried is usually small, but on a 5x6 board,for example, tens of thousands may be needed. On odd-sized boards the numberof positions the program has to go through before quitting is very large,except for the 5x5 board, where it lies between 15 000 and 40 000. By switchingoff animation, this can be verified even on slower computers. For moredetailed figures, see <A HREF="#3.3">section 3.3</A>.</BLOCKQUOTE><H4><A NAME="1.4"></A>1.4 Limitations</H4><BLOCKQUOTE>Currently, the dimensions of the board can only be betweenfive and ten. There are solutions for some boards three squares wide, butnot for one, two, or four wide. The upper bound of ten is to always leavesufficient space for the user to resize the board without making the individualsquares too small. It is possible to change these bounds by changing constantsin the classes <A HREF="#2.3.5">KnightBoard</A> and<A HREF="#2.3.3">GraphicalBoard</A>.<P>There is no way to save or print the intermediate or final results.</BLOCKQUOTE><H2><A NAME="2"></A>2 Program Structure</H2><H4><A NAME="2.1"></A>2.1 About the Knight's Tour Quandary</H4><BLOCKQUOTE>From Ted Feller's <A HREF="http://home.earthlink.net/~tfiller/knight.htm">Knight'sTour page</A> (after <I>Scientific American</I>, May 1997):<P>Mathematically, the knight's tour quandary reduces to finding a "Hamiltoniancycle" in a graph. A graph is a collection of dots, called nodes, joinedby lines, called edges. A Hamiltonian cycle is a closed path that visitseach node exactly once. The graph of a chessboard is obtained by placinga node at the center of each square and then drawing edges between nodesthat are separated by one knight's move. It helps to color the nodes darkand light, corresponding to the usual pattern on a chessboard. Notice thatwhen the knight moves, it hops from a node of one color to one of the oppositecolor, so the nodes must be alternately dark and light around any Hamiltoniancycle. This pattern implies that the total number of nodes must be even.If the chessboard were 3 x 5, with 15 nodes (an odd number), we have provedthat no knight's tour is possible on such a chessboard. The same is truefor any rectangular board of size <I>m</I> x <I>n</I> where <I>m</I> and<I>n</I>are both odd.<BR> <CENTER><TABLE NOSAVE ><TR NOSAVE><TD NOSAVE><IMG SRC="images/board.gif" ALT="" HSPACE=50 NOSAVE BORDER=1 HEIGHT=186 WIDTH=186></TD><TD><IMG SRC="images/graph.gif" ALT="" HSPACE=50 NOSAVE BORDER=1 HEIGHT=227 WIDTH=226></TD></TR><TR><TD><CENTER><I>Figure 2.</I> Knight's moves.</CENTER></TD><TD><CENTER><I>Figure 3.</I> Knight's graph.</CENTER></TD></TR></TABLE></CENTER><P>This kind of argument is known as a parity proof. A more subtle parityproof, invented by Louis Posa, demonstrates that there is no closed knight'stour on any 4 x <I>n</I> board. Allen Schwenk provided a characterizationof those rectangular boards that support a knight's tour. He found thatan <I>m</I> x <I>n</I> chessboard (when <I>m</I> is less than or equalto <I>n</I>) supports a knight's tour unless:<BLOCKQUOTE><LI><I>m</I> and <I>n</I> are both odd</LI><LI><I>m</I> = 1, 2 or 4</LI><LI><I>m</I> = 3 and <I>n</I> = 4, 6 or 8</LI></BLOCKQUOTE>The key idea is that a tour on an <I>m</I> x <I>n</I> board can alwaysbe extended to one on an <I>m</I> x (<I>n</I> + 4) rectangle. By symmetry,a tour on an <I>m</I> x <I>n</I> board can be extended to any (<I>m</I>+ 4) x <I>n</I> rectangle.</BLOCKQUOTE><H4><A NAME="2.2"></A>2.2 The Algorithm</H4><BLOCKQUOTE>The algorithm used is very simple. When a new board is created,a value is calculated for each square. This value represents the numberof exits, ie. the number of unvisited squares reachable in one move. Anadjacency list is created for each square, which contains indices to thesquares reachable directly from it.<P>The tour is looked for using a recursive function that implements adepth-first search. Possible moves are tried in order of increasing value,so the squares with the least number of exits come first. This is knownas Warnsdorff's rule. If there are many squares with the same value, theyare tried in order of decreasing distance from the starting square.<P>After each move, the values for all affected squares are updated, andthe square is marked visited. The starting square is not actually visiteduntil last, so special care is taken of the squares adjacent to it in thegraph. No move that is not next-to-last may use the last unvisited one.This way, the program ensures there is always at least one way back tothe starting square. Also, each time values are updated, orphaned (unreachable)squares are checked for. If a move would result in unreachable squares,it is skipped. This decreases the total size of the search tree considerably.</BLOCKQUOTE><H4><A NAME="2.3"></A>2.3 Class Structure</H4><BLOCKQUOTE>The class structure of the program is as follows:<CENTER><P><IMG SRC="images/diagram.gif" ALT="" HSPACE=10 VSPACE=5 NOSAVE BORDER=1 HEIGHT=1070 WIDTH=802><BR><I>Figure 4.</I> UML class diagram.</CENTER><BR> <P>Only a single object of each class exists at a time. Description ofthe classes follows.<BR> ?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -