Java语言程序设计 基础篇进阶篇 所有的

/* * PKnightTour.java * * Created on August 24, 2007, 7:32 PM * */ import javax.swing.*; /** * * @author Tony Lucento * */ public class PKnightTour extends JApplet { public static final long serialVersionUID = 1L; private Integer[] solution; public PKnightTour(int startSquare) { Board board = new Board(8); Knight sirRobin = new Knight(board); solution = sirRobin.tour(startSquare); } /** * @param args the command line arguments */ public static void main(String[] args) { ChessboardJFrame frame = new ChessboardJFrame(); frame.setVisible(true); } public Integer[] getSolution(){ return solution; } public class Knight { Board board; SquareStack path; public Knight(Board board){ this.board = board; } public Integer[] tour(int startSquareId) { path = new SquareStack(); findPath(board.getSquare(startSquareId)); //outputPath(path); return getPathAsSquareIds(path); } private Integer[] getPathAsSquareIds(SquareStack path){ path = path.reverse(); java.util.ArrayList<Integer> ids = new java.util.ArrayList<Integer>(); while (!path.empty()) { ids.add(path.pop().getId()); } Integer a[] = new Integer[ids.size()]; a = ids.toArray(a); return a; } private void outputPath(SquareStack path){ path = path.reverse(); while (!path.empty()) { System.out.println("to " + path.pop().getId()); } } public void findPath(Square sq){ path.push(sq); if (!board.allVisited()) { java.util.ArrayList<Square> moves = sq.getPossibleMovesOrdered(); for (int i = 0; i < moves.size(); i++) { if (!board.allVisited()) findPath(moves.get(i)); } if (!board.allVisited()){ Square s = path.pop(); } } } } public class Board { int dim; java.util.ArrayList<Square> squares; public Board(int dimension) { dim = dimension; squares = new java.util.ArrayList<Square>(); int id = 1; for (id = 1; id <= dim*dim; id++) { Square square = new Square(this, id); squares.add(square); } } public int getDimension(){ return dim; } public int getSquareCount(){ return dim * dim; } public java.util.ArrayList<Square> getSquares() { return squares; } public Square getSquare(int id) { return squares.get(id - 1); } public boolean allVisited(){ boolean retVal = true; for (int i = 0; i < squares.size(); i++){ retVal &= squares.get(i).getVisited(); if (!retVal) return false; } return retVal; } } public class Square implements Comparable<Square> { int id; boolean visited; Board board; public Square(Board board, int id){ this.id = id; this.board = board; } public int compareTo(Square s){ //Square s = (Square)o; int sSize = s.getPossibleMoves().size(); int thisSize = this.getPossibleMoves().size(); if (thisSize > sSize){ return sSize == 0 ? -1 : 1; } else if (thisSize < sSize){ return thisSize == 0 ? 1 : -1; } else { //they have the same number of possible moves. //check the next sets of squares for this and o. int t2g = 0; int o2g = 0; for (Square this2g : this.getPossibleMoves()){ t2g += this2g.getPossibleMoves().size(); } for (Square other2g : s.getPossibleMoves()){ o2g += other2g.getPossibleMoves().size(); } if (t2g > o2g){ //return 1; return o2g == 0 ? -1 : 1; } else if (t2g < o2g){ return t2g == 0 ? 1 : -1; } else { return 0; } } } public int getId() { return id; } public int getRow(){ return id % board.getDimension() == 0 ? id / board.getDimension() : id / board.getDimension() + 1; } public int getColumn(){ return id % board.getDimension() == 0 ? board.getDimension() : id % board.getDimension(); } public boolean getVisited(){ return visited; } public void setVisited(boolean visited){ this.visited = visited; } public java.util.ArrayList<Square> getPossibleMovesOrdered(){ java.util.ArrayList<Square> moves = getPossibleMoves(); java.util.Collections.<Square>sort(moves); return moves; } public java.util.ArrayList<Square> getPossibleMoves(){ return getPossibleMoves(false); } public java.util.ArrayList<Square> getPossibleMoves(boolean includeVisited){ java.util.ArrayList<Square> moves = new java.util.ArrayList<Square>(); int dim = board.getDimension(); Square square; if (dim * getRow() >= id + 2) { //can move right 2 if (id + 2 + dim < dim * dim){ square = board.getSquare(id + 2 + dim); if (!square.getVisited() || includeVisited) moves.add(square); } if (id + 2 - dim > 0){ square = board.getSquare(id + 2 - dim); if (!square.getVisited() || includeVisited) moves.add(square); } } if (id - 2 > dim * (getRow() - 1)) { //can move left 2 if (id - 2 + dim < dim * dim){ square = board.getSquare(id - 2 + dim); if (!square.getVisited() || includeVisited) moves.add(square); }