knightstour.java

这是一个骑士周游java编程问题三维效果

import java.awt.*;
import java.applet.*;
/*********************        
*                    *   Knight's Tour Problem
*                    *   Starting from any square on the chess board,
*                    *   the Knight has to cover all the 64 squares in
*                    *   exactly 64 moves.
*                    *   Author  Vasanth Desai
*                    *   Email [e-mail]
*                    *   (c) 1998 Vasanth Desai
**********************
*            History
*            I read about this problem sometime around late sixites 
*            in a Sunday magazine as a puzzle, and solved it, may be in
*            10 minutes and noted down the path.
*            Late I thougt I would write a general program to find the
*            path from any starting position if it exists.
*            I tried it sometime in late seventies On CDC CYBER 
*            (Erlangen University) and could not examine moves 
*            beyond 20-25 due to combinatorial explosion. (Since
*            it was obvious that there would be combinatorial explosion I
*            should not have tried it in the first place. Then I thougt I might
*            hit the  right path in the first few alternatives, and may not
*            have to store/examine all the alternatives. It did not work)
*            Such problems require heuristics to tackle.
*            Though I devised a heuristics I did not code it since it
*            was quite messy. I made another attempt in 1983 but abandoned.
*     
*            20/4/98
*            I decided to try to sove the problem using Java. Object oriented 
*            languages make it really easy to tackle real world complexities.
*            I could solve the entire problem in about 3 hours.
*            Full credits to Java
*
*/



/*
	  8 possible moves from X
	  for the knight
	____________________
	|   | 8 |   | 1 |   |
	|___|___|___|___|___|
	| 7 |   |   |   | 2 |
	|___|___|___|___|___|
	|   |   |   |   |   |
	|___|___|_X_|___|___|
	| 6 |   |   |   | 3 |
	|___|___|___|___|___|
	|   | 5 |   | 4 |   |
	|___|___|___|___|___|
*/
   
/*
   The class Square represents a square in a chess board. When we want to know
   who are are neighbours we should know about the container- the Chess Board.
	The class Board represents the chess board and each square knows about
	the board via the variable b which is set when 'squares' are created.
	There is sister class of Square, CSquare which handles visual aspects of
	the Square. The CSquare objects are embedded in an instance of MyFrame
	class. MyFrame is derived from Frame and hosts the chess board. The user
	can resize the window. The frame  is a popup window.
	
	The class KnightsTour is the 'main' class. It glues together all the
	objects. It is designed so that it works both as an Applet and Application.
*/	   
//
// The code is written in Java 1.0.2. It is straightforward to convert into
// later versions. The conversion which requires a little careful thougt is:
// When the user clicks on a square, the CSquare objects delivers an event to
// MyFrame conveying id of the CSquare.
//
// About the source code: The source code, alas, does not incorporate the best
// programming practices. For example accessibilty of variables and methods
// are not always defined. The methods of one class peek and poke data members
// other classes directly. One should have used get/set methods. Commenting is
// scarce. If you have not tackled similar problems, understanding code
// is not very easy.
// The point is, the project was to try the heuristics to solve
// the Knight's Tour problem,and to write best and efficient code
// to do so was secondary. 


	class Square {
		int id;
		Board b = null;
		boolean visited = false;
		Square(int n) { id = n;}
		Square(int n,Board b){ id =n; this.b = b;}
		int row(){ return id/8+ 1;}
		int col(){ return (id%8) + 1;}
		int getId(int r, int c) { return (r-1)*8+c-1;}
		// returns  legal moves from this square
		int[] next(){
			 int p[] = new int[8];
			 int m = 0,r,c;
			 for(int i=0; i < 8;i++){
			 	r = this.row(); c = this.col();
				switch(i){
				 case 0:  r -= 2; c += 1; break;
				 case 1:  r -= 1; c += 2; break;
				 case 2:  r += 1; c += 2; break;
				 case 3:   r += 2; c += 1 ; break;
				 case 4:  r += 2 ; c -= 1; break;
				 case 5:  r += 1; c -= 2; break;
				 case 6:  r -= 1; c -= 2; break;
				 case 7:  r -= 2; c -= 1; break;
				} 			 
			 	if(( r < 1) || ( r > 8) || ( c < 1) || (c > 8)) continue;
				p[m] = getId(r,c);
				m++;
			 }
			 int t[]= new int[m];
			 System.arraycopy(p,0,t,0,m);
			 return t;	 
		}
		// returns the number of moves from the next jump.
		// takes into account of visited squares 
		int escapes(int omit){
			int nxt[];
			nxt = next();
			int e=0;
			for(int i = 0; i < nxt.length; i++){
				if(b.sq[nxt[i]].visited || (nxt[i]== omit)) continue;
				e++;
			}
			return e;	
		}
		// this is the HEURISTICS
		// what is the best jump from the square ?
		// -1 if none. Note that you may get trapped into a hole and can not
		// come out since all possible escape squares are already visited
		int goodExit(){
			int nxt[];
			nxt = next();
			int k = 8;
			int idx = -1;
			int e = 0;
			for(int i = 0; i < nxt.length; i++) {
				if(b.sq[nxt[i]].visited) continue;
				e = b.sq[nxt[i]].escapes(nxt[i]);
				if((e > 0) && ( e < k)) { k = e; idx = i;}
			}
			if(idx == -1) return idx;
			else
			return nxt[idx];
		} 	
	}
	class Board  extends Thread{
		Square sq[];
		CSquare csq[];
		boolean running = false;  // set true while the knight is moving
		int delayInterval = 500;
		int stsq = 0;
		Board(){
			sq = new Square[64];
			for(int i = 0; i < 64; i++) sq[i] = new Square(i,this);
		}
		// Returns the path. The problem was first solved without 'visual'
		// encumberences. At that this method allowed me 'print' the
		// path on stdout and check the logic
		int[]findPath(int startSquare){
			int i  = 0;
			int path[];
			path = new int[64];
			for(i = 0; i < 64; i++) sq[i].visited = false;
			sq[startSquare-1].visited = true;
			int nxt[];
			int n = -1;
			int moves = 0;
			int currentSquare = startSquare-1;
			path[currentSquare] = moves+1;
			for( i = 0; i < 64; i++) {
				n = sq[currentSquare].goodExit();
				if( n < 0 ) break;
				sq[n].visited = true;
				moves++;
				currentSquare = n;
				// remember path path
				path[currentSquare] = moves+1;
			}
			// find out unvisited squares
			int nUnvisited = 0;
			int unvisited = -1;
			for(i = 0; i < 64; i++){
				if(!sq[i].visited){
					unvisited = i;
					nUnvisited++;
				}
			}
			if(nUnvisited == 1) {
				nxt = sq[currentSquare].next();
				for(i = 0;i < nxt.length; i++) {
					if(nxt[i] == unvisited) {
						path[unvisited]=moves+2;
						break;
					}	
				}
			} else {
				// System.out.println("Failed to find solution");
			 	// System.exit(1);
				return null;
			}
			return path;	 
		}
		// Engine
		public void run(){
			running = true;
		   showPath(stsq);
			running = false;
			stop();							
		}
		// Visually show the knignts moves on the chess board
		// Sleep a little after each so that user is not suspicious.
		void showPath(int startSquare){
			int i  = 0;
			int path[];
			path = new int[64];
			for(i = 0; i < 64; i++){
				 sq[i].visited = false;
				 csq[i].num = -1;
				 csq[i].hval = -1;
				 csq[i].update(csq[i].getGraphics());
			}	 
			sq[startSquare-1].visited = true;
			int nxt[];
			int n = -1;
			int moves = 0;
			int currentSquare = startSquare-1;
			path[currentSquare] = moves+1;
			csq[currentSquare].num = moves+1;
			csq[currentSquare].hval = 1;
         csq[currentSquare].update(csq[currentSquare].getGraphics());
			for( i = 0; i < 64; i++) {
				try {
					sleep(delayInterval);
				} catch(InterruptedException e){
				}
				n = sq[currentSquare].goodExit();
				if( n < 0 ) break;
				sq[n].visited = true;
				csq[currentSquare].hval = -1;
            csq[currentSquare].update(csq[currentSquare].getGraphics());				
				moves++;
				currentSquare = n;
				// remember path 
				path[currentSquare] = moves+1;
				csq[currentSquare].num = moves+1;
				csq[currentSquare].hval = 1;
            csq[currentSquare].update(csq[currentSquare].getGraphics());
			}
			// Find out unvisited squares
			// Since the goodExit always looks one ahead, if every thing
			// is OK when we arrive here theres should be exactly one
			// unvisited square and it should be reachale from the last visted
			// square
			int nUnvisited = 0;
			int unvisited = -1;
			for(i = 0; i < 64; i++){
				if(!sq[i].visited){
					unvisited = i;
					nUnvisited++;
				}
			}
			if(nUnvisited == 1) {
				nxt = sq[currentSquare].next();
				for(i = 0;i < nxt.length; i++) {
					if(nxt[i] == unvisited) {
						csq[currentSquare].hval = -1;