knightthread.java

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

import java.awt.*;

/** This class is responsible for actually solving the Knight's Tour problem
    of finding a Hamiltonian cycle for the knight on a chess board. The tour
    goes through each square on the board once, returning finally to the
    first square. The tour is only possible on boards with an even number
    of squares. <P>

    The class must first be instantiated with a GraphicalBoard object, the
    start square then set with setStartSquare(), and the actual calculation
    finally started with Thread.start() or by invoking run(). <P>

    Graphical animation is off by default; it can be turned on using
    setAnimation(). The thread also displays a help text on the specified
    label depending on its internal state: running, animated, or completed.

    @see GraphicalBoard
*/

public class KnightThread extends Thread {
    private static final int DELAY = 300; // milliseconds

    private final GraphicalBoard board;
    private final Label label;
    private final int squares;
    private boolean anim = false;

    private int startx, starty;
    private int steps;

    /** Creates a new thread.

        @param board a properly initialized board.
        @param statuslabel label for displaying status text.
    */

    public KnightThread(GraphicalBoard board, Label statuslabel) {
        if (!board.Invariant())
            throw new RuntimeException("board not valid");

        if (statuslabel == null)
            throw new RuntimeException("statuslabel == null");

        this.board = board;
        this.label = statuslabel;
        squares = board.width * board.height;

        label.setText("Choose the starting square:");
        label.repaint();

        setPriority(Thread.MIN_PRIORITY);
    }

    /** Sets the start square.

        @param x x-index of start square.
        @param y y-index of start square.
        @return true if OK, false if start square is already set.
        @see KnightBoard#setStartSquare
    */

    public boolean setStartSquare(int x, int y) {
        return (board.setStartSquare(startx = x, starty = y));
    }

    /** Solves the Knight's Tour problem. The board must be properly
        initialized and the start square set. A RuntimeException is
        thrown if the board is not valid. The thread dies when either
        a solution has been found or all possible combinations have
        been tried.
    */

    public void run() {
        if (!board.Invariant())
            throw new RuntimeException("board not valid");

        update();

        if (solution(startx, starty))
            label.setText("Solution found; " + (steps+1) + " positions tried.");
        else
            label.setText("No solution found; " + (steps+1) + " positions tried.");
        label.repaint();

        board.repaint();
        board.setResizable(true);

        if (!board.Invariant())
            throw new RuntimeException("board not valid");
    }

    /** Sets animation on or off. By default, animation is disabled.

        @param anim true enables animation, false disables.
    */

    public void setAnimation(boolean anim) {
        this.anim = anim;
    }

    /** Updates the board and the help text. In animated mode, the number
        of positions checked thus far is displayed; otherwise, the label
        reads simply 'Running'.
    */

    public void update() {
        if (isAlive()) {
            if (anim)
                label.setText("Running... Positions tried: " + steps);
            else
                label.setText("Running...");
            label.repaint();
        }

        board.repaint();
    }

    /** A recursive function called for each new knight position tried.
        This implements a depth-first search that always chooses the 
        unvisited square with the lowest value, ie. least exits first.
        If there are many, the one with the greatest distance from the
        start square is tried first, unless the board is smaller than
        36 squares. <P>

        Positions leading to unreachable squares are not pursued further.
        This prunes the search tree to something like 1/20th of its original
        size. Arrays and insertion sort are used for maximum speed.

        @param x x-index of knight position.
        @param y y-index of knight position.
        @return true if a solution was found beginning from the specified
        position.
        @see KnightBoard
    */

    private boolean solution(int x, int y) {
        /*
          // FOR DEBUGGING. Too slow for ordinary use...
          if (!board.Invariant())
              throw new RuntimeException("board not valid");
        */

        int[][] adjlist = board.getAdjacencyList(x, y);
        int[][] al = new int[8][3]; // x, y, value
        int n = 0;

        // List all adjacent, unvisited, non-start squares to al[][].

        for (int i = 0; adjlist[i][0] >= 0; ++i) {
            int ax = adjlist[i][0], ay = adjlist[i][1];
            if (board.getMove(ax, ay) > 0)
                continue;

            int v = board.getValue(ax, ay);
            if (v == board.STARTSQUARE)
                continue;

            int d = distance(ax, ay);

            // Insertion sort first by value, then by distance from start square.
            // Efficient, since we have to copy the list anyway.

            int j;
            for (j = n; j > 0; --j) {
                if (v < al[j-1][2] || (v == al[j-1][2] && d > distance(al[j-1][0], al[j-1][1]))) {
                    al[j][0] = al[j-1][0];
                    al[j][1] = al[j-1][1];
                    al[j][2] = al[j-1][2];
                } else
                    break;
            }

            al[j][0] = adjlist[i][0];
            al[j][1] = adjlist[i][1];
            al[j][2] = v;
            ++n;
        }

        // Try all possibilities in order

        for (int i = 0; i < n; ++i) {
            int ax = al[i][0], ay = al[i][1];

            if (!board.moveKnight(ax, ay)) {
                // Bad idea: unreachable squares. Skip.
                board.undoMove(ax, ay);
                continue;
            }

            ++steps;
            pause();
            
            // Are we finished?
            if (board.getWaysBack() == 0) {
                board.moveKnight(startx, starty);
                return true;
            }
            
            // Recursively call ourselves to find a solution...
            if (solution(ax, ay))
                return true;
            else {
                board.undoMove(ax, ay);
                pause();
            }
        }

        // All possibilities checked.
        return false;
    }

    /** Calculates the Pythagorean (x^2 + y^2) distance of the specified
        square from the start square, unless the board is smaller than
        36 squares.

        @param x x-index of square.
        @param y y-index of square.
        @return distance from start square, or zero if the board is small.
    */

    private int distance(int x, int y) {
        if (squares < 36)
            return 0;

        int dx = startx - x, dy = starty - y;
        return (dx*dx + dy*dy);
    }

    /** In animated mode, updates the board on screen and pauses for a while. */

    private void pause() {
        if (anim) {
            update();
            try {
                sleep(DELAY);
            } catch (InterruptedException e) { }
        }
    }
 }