doc.html

设计一个软件的启动过程界面

<LI>
<A HREF="tree.html">JavaDoc class tree</A></LI>

<LI>
<A HREF="AllNames.html">JavaDoc index of names</A></LI>

<H5>
<A NAME="2.3.1"></A>2.3.1 KnightsTour</H5>

<BLOCKQUOTE>This is the main class, a subclass of <I>java.applet.Applet</I>.
It instantiates a <A HREF="#2.3.3">GraphicalBoard</A> and a <A HREF="#2.3.2">KnightThread,</A>
and passes the board to the newly created thread. It takes care of handling
user actions, receiving events from the AWT as well as the <A HREF="#2.3.3">GraphicalBoard</A>
by implementing the <A HREF="#2.3.4">BoardListener</A> interface. A new
board and thread are created every time the board is cleared.
<BR>&nbsp;
<LI>
<A HREF="KnightsTour.html">JavaDoc documentation</A></LI>

<LI>
<A HREF="../KnightsTour.java">Source code</A></LI>
</BLOCKQUOTE>

<H5>
<A NAME="2.3.2"></A>2.3.2 KnightThread</H5>

<BLOCKQUOTE>A KnightThread does the actual searching. After it is instantiated,
it must be given a start square and then started. At the core is the recursive
function <A HREF="KnightThread.html#solution">solution()</A> that is called
for each new knight position. Moves are made in <A HREF="KnightThread.html#solution">solution()</A>
using <A HREF="#2.3.5">KnightBoard</A> services. The thread also takes
care of having pauses between steps and refreshing the display if animation
is enabled.
<BR>&nbsp;
<LI>
<A HREF="KnightThread.html">JavaDoc documentation</A></LI>

<LI>
<A HREF="../KnightThread.java">Source code</A></LI>
</BLOCKQUOTE>

<H5>
<A NAME="2.3.3"></A>2.3.3 GraphicalBoard</H5>

<BLOCKQUOTE>Adds a graphical representation to <A HREF="#2.3.5">KnightBoard</A>,
which it subclasses. It is also a subclass of <I>java.awt.Canvas</I> via
<A HREF="#2.3.5">KnightBoard</A>.
The <A HREF="GraphicalBoard.html#update">update()</A> method draws the
board on screen, adjusting to the amount of screen space available. Subsequently,
it re-draws only the squares whose content has changed. The class also
handles its own mouse events, calling a <A HREF="#2.3.4">BoardListener</A>
when the user clicks or drags the board.
<BR>&nbsp;
<LI>
<A HREF="GraphicalBoard.html">JavaDoc documentation</A></LI>

<LI>
<A HREF="../GraphicalBoard.java">Source code</A></LI>
</BLOCKQUOTE>

<H5>
<A NAME="2.3.4"></A>2.3.4 BoardListener</H5>

<BLOCKQUOTE>Interface for receiving <A HREF="BoardListener.html#boardClicked">boardClicked()</A>
and <A HREF="BoardListener.html#boardResized">boardResized()</A> events
from <A HREF="#2.3.3">GraphicalBoard</A>.
<BR>&nbsp;
<LI>
<A HREF="BoardListener.html">JavaDoc documentation</A></LI>

<LI>
<A HREF="../BoardListener.java">Source code</A></LI>
</BLOCKQUOTE>

<H5>
<A NAME="2.3.5"></A>2.3.5 KnightBoard</H5>

<BLOCKQUOTE>Provides a rectangular chess board of freely chosen size with
services for finding a knight's tour. Though it appears to subclass <I>java.awt.Canvas</I>,
it does not use any <I>Canvas</I> services and is not a graphical object.
Because Java does not support multiple inheritance, this is a kludge to
allow <A HREF="#2.3.3">GraphicalBoard</A> to subclass <I>Canvas</I>. The
board keeps track of the values of the squares, of the moves made, and
provides adjacency lists for the squares. The values are updated automatically
when moves are made using <A HREF="KnightBoard.html#moveKnight">moveKnight()</A>
and undone using <A HREF="KnightBoard.html#undoMove">undoMove()</A>.
<P>The adjacency lists are stored in a four-dimensional array. The first
two dimensions specify the x- and y-indices of the squares, as usual. The
third enumerates the adjacent (reachable) squares, of which there can be
at most eight. The fourth gives the x- and y-indices of the adjacent squares
in indices 0 and 1, respectively. This is faster and uses less memory than
a linked list, since the number of elements is bounded and small. The public
method <A HREF="KnightBoard.html#getAdjacencyList">getAdjacencyList()</A>
gives the list for a specified square.
<P><A HREF="KnightBoard.html#Invariant">Invariant()</A> is a quite complete
test for the validity of the board state. Because of its completeness,
it is too slow to be called each time a move is made except when debugging.
However, it is used to verify the validity of the board before starting
and after finding a solution. If it returns <I>false</I>, which should
never be the case, the program terminates immediately on an exception.
<P>Specifically, <A HREF="KnightBoard.html#Invariant">Invariant()</A>&nbsp;
first checks that the class variables of the board object are non-<I>null</I>.
It then proceeds to check that there is exactly one start square, count
the number of moves on the board, calculate the values of all squares,
and compare them to the ones stored in the class variables. If the tour
is finished, it also makes sure that the moves are legal and in correct
order.
<BR>&nbsp;
<LI>
<A HREF="KnightBoard.html">JavaDoc documentation</A></LI>

<LI>
<A HREF="../KnightBoard.java">Source code</A></LI>
</BLOCKQUOTE>
The <A HREF="../Makefile">Makefile</A> of the program supports generating
JavaDoc documentation with the command '<B><TT>make doc</TT></B>'.</BLOCKQUOTE>

<H4>
<A NAME="2.4"></A>2.4 Possible Improvements</H4>

<BLOCKQUOTE>An obvious area for improvement is the algorithm. Although
the average-case running time is excellent, measured experimentally to
be linear in the number of squares, the worst case is exponential. In contrast,
there is a simple divide-and-conquer algorithm that can be used on symmetrical
boards of dimensions greater than five, whose worst-case running time has
an upper bound linear in the number of squares.
<P>An useful improvement would be to be able to save intermediate steps
and the final tour to disk for analysis and storage. Also interesting might
be to be able to time the process and change some parameters of the algorithm
on the fly to see how it affects performance.</BLOCKQUOTE>

<H3>
<A NAME="3"></A>3 Testing</H3>

<H4>
<A NAME="3.1"></A>3.1 Testing Tool</H4>

<BLOCKQUOTE>To aid in testing, a short, independent Java program imaginatively
called 'Test' has been written. To use it, JDK 1.1 or later must be properly
installed. It can be compiled with the command '<B><TT>make test</TT></B>'
and run with '<B><TT>java Test</TT></B>'. Optionally, the dimensions of
the board may be given as parameters, as in '<B><TT>java Test 6 8</TT></B>',
which uses a 6x8 board. The default dimensions are 8x8. Note that there
is no upper bound on the board dimensions.
<P>The test program runs <A HREF="#2.3.2">KnightThread</A> using each square
on the board in turn as the starting square, and prints the number of steps
that were needed to find a solution in each case to the console. If all
is well, either a solution will be found for all starting squares or, for
odd-sized boards, none will be found for any of them. Verifying the latter
case usually takes too much time (except on a 5x5 board), since the algorithm
does not give up until all knight positions have been tried.
<P>The test program itself is not fool-proof or user-friendly, since it
is only intended for development. Test results are given in <A HREF="#3.3">section
3.3</A>.
<BR>&nbsp;
<LI>
<A HREF="../Test.java">Source code</A></LI>
</BLOCKQUOTE>

<H4>
<A NAME="3.2"></A>3.2 Verifying Individual Classes</H4>

<BLOCKQUOTE>At the core of the program is the <A HREF="#2.3.5">KnightBoard</A>
class. Because its correctness is vital, a complete <A HREF="doc/KnightBoard.html#Invariant">invariant
test</A> has been incorporated into the class, as described in <A HREF="#2.3.5">section
2.3.5</A>. The program has been extensively tested using the Test program
with the invariant check done after each move; no failures occurred (see
<A HREF="#3.3">section 3.3</A>).
<P>The correctness of the algorithm in <A HREF="#2.3.2">KnightThread</A>
is more difficult to prove. It can be argued that since it is a depth-first
search that checks all possibilities, it will always find a tour if one
exists or stop after an exhaustive search. According to the tests this
indeed seems to be the case. All tours produced by the program were correct,
as verified by the invariant in <A HREF="#2.3.5">KnightBoard</A> and some
even checked by hand.
<P>The remaining classes provide the user interface. Besides being intuitive,
the graphical interface also makes it impossible for the user to enter
invalid values. It has been thoroughly tested in practice by the author
and some of his friends on a <A HREF="http://www.linux.org">Linux</A>-based
<A HREF="http://www.blackdown.org">JDK 1.1.7</A> platform as well as on
<A HREF="http://www.netscape.com/download">Netscape Navigator</A> 4.08.
Since these classes are also structurally simple, they can, on the basis
of these tests, be considered fault-free.</BLOCKQUOTE>

<H4>
<A NAME="3.3"></A>3.3 Test Results</H4>

<BLOCKQUOTE>The test program was completed for the following board sizes:
5x5 (no solutions), 5x6, 5x8 (*), 5x10 (*), 6x6, 6x8, 7x8, 8x8, 8x10, 10x10.
On all boards except 5x5 a solution was found for every starting square.
The tests were also run with the <A HREF="#2.3.5">KnightBoard</A> invariant
check done after each move except for the boards marked with an asterisk
(*), which took exceptionally long to complete. No problems arose in any
of the tests.
<P>Some verbatim logs of timed tests are below. Times are wall clock times
measured on a dedicated Pentium II-300 MHz running <A HREF="http://www.blackdown.org">JDK
1.1.7</A> with <A HREF="http://www.dragon1.net/software/tya">Tya 1.2v4</A>
just-in-time compiler on <A HREF="http://www.linux.org">Linux</A> <A HREF="http://www.linuxhq.com">2.2.5</A>.
The invariant check was not done between moves. The coordinates on the
left mark the x and y coordinates of the starting square, so that (0, 0)
corresponds to <B>a1</B>.
<BLOCKQUOTE><TT><FONT SIZE=-1>Starting test on a board of size 5x5...</FONT></TT>
<BR><TT><FONT SIZE=-1>(0, 0): No solution found; 23251 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(0, 1): No solution found; 40777 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(0, 2): No solution found; 36367 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(0, 3): No solution found; 40777 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(0, 4): No solution found; 23251 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(1, 0): No solution found; 40777 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(1, 1): No solution found; 36563 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(1, 2): No solution found; 15459 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(1, 3): No solution found; 36563 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(1, 4): No solution found; 40777 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(2, 0): No solution found; 36367 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(2, 1): No solution found; 15459 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(2, 2): No solution found; 19601 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(2, 3): No solution found; 15459 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(2, 4): No solution found; 36367 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(3, 0): No solution found; 40777 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(3, 1): No solution found; 36563 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(3, 2): No solution found; 15459 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(3, 3): No solution found; 36563 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(3, 4): No solution found; 40777 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(4, 0): No solution found; 23251 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(4, 1): No solution found; 40777 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(4, 2): No solution found; 36367 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(4, 3): No solution found; 40777 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(4, 4): No solution found; 23251 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>Test finished.</FONT></TT>
<BR><I>Elapsed time: 34 seconds.</I>
<P><TT><FONT SIZE=-1>Starting test on a board of size 6x6...</FONT></TT>
<BR><TT><FONT SIZE=-1>(0, 0): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(0, 1): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(0, 2): Solution found; 525 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(0, 3): Solution found; 525 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(0, 4): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(0, 5): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(1, 0): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(1, 1): Solution found; 40 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(1, 2): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(1, 3): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(1, 4): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(1, 5): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(2, 0): Solution found; 41 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(2, 1): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(2, 2): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(2, 3): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(2, 4): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(2, 5): Solution found; 41 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(3, 0): Solution found; 41 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(3, 1): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(3, 2): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(3, 3): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(3, 4): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(3, 5): Solution found; 41 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(4, 0): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(4, 1): Solution found; 40 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(4, 2): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(4, 3): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(4, 4): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(4, 5): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(5, 0): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(5, 1): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(5, 2): Solution found; 525 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(5, 3): Solution found; 525 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(5, 4): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>(5, 5): Solution found; 36 positions tried.</FONT></TT>
<BR><TT><FONT SIZE=-1>Test finished.</FONT></TT>
<BR><I>Elapsed time: 1 second.</I></BLOCKQUOTE>
Running the test for a standard 8x8 chess board takes about 1.5 seconds,
and a solution is found for all but two squares in 64 steps - the two take
117 steps. A 10x10 board takes 4 seconds to complete. For the largest one
tried, 150x150, finding one solution from <B>a1</B> takes 20 seconds and
22 500 steps. As can be seen from these figures, average-case performance
is nearly optimal. Generally, for boards with dimensions of at least eight
solutions are found very quickly. Some small asymmetrical boards present
problems to our algorithm: from some starting squares tens of millions
of steps may be needed before a tour is found.
<P>On the test system the program examines about 10 000 to 20 000 positions
per second on small boards. If we estimate the branching factor for a 7x7
board to be at least 1.6, the number of all possible knight positions exceeds
1.6^49, about ten billion. This rules out the possibility of experimentally
verifying the absence of tours for (odd-sized) boards larger than 5x5.</BLOCKQUOTE>
</BLOCKQUOTE>

</BODY>
</HTML>