/**  Knight.java      David Fourer
  * requires ChessSquare.java
  * Chess puzzle.
  * The Knight's tour requires a single knight to hit each square
  * of a chess board once and only once.
  * This program has been through a couple of versions.  This one
  * uses a thread and off-screen buffer for drawing images.
  * A 2-subscript array of 64 objects represents the board and has the
  * drawing methods.
  */
import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;

public class Knight extends Applet implements ActionListener, Runnable {

	Label title;
	Button start, faster, slower;
	Button pause, single;
	
	int millisec = 400;
	
	ChessSquare kk[ ][ ] = new ChessSquare[8][8];	//display objects/chessboard

	private Thread kt;
	private Image buffer;
	private Graphics gContext;
	
		// 8 basic moves for knight, relative to current position.  
	int moves[ ][ ] = {	{-2,  1}, {-2, -1}, { 2,  1}, { 2, -1},
							{-1,  2}, {-1, -2}, { 1,  2}, { 1, -2} };

		// false means knight has not yet landed on that square.
	boolean board[ ][ ] = new boolean [8][8];

	int pos[ ] = new int [4];		// x and y current position, last position.
	boolean success;					// false = game over.
	boolean running = true;
	boolean oneSpace = false;
//******************************************************** init( )
	public void init( ) {
		controllPanel( );

		buffer = createImage( 600, 400 );
		gContext = buffer.getGraphics( );
		
		for( int i=0; i<8; i++ )		// Instantiate each object
			for( int j=0; j<8; j++ )	// args tell size, location of board		
				kk[i][j] = new ChessSquare( 40, 20, 80, i, j );
	}
//*******************************************Applet start and stop
	public void start( ) {
		if( kt == null ) {
			kt = new Thread( this );
			kt.start( );
		}
	}
	public void stop( ) {
		if( kt != null ) {
			kt.stop( );
			kt = null;
		}
	}
//************************************************** ActionPerformed
	public void actionPerformed( ActionEvent e ) {
		if( e.getSource( ).equals( single ) ) {	//watch game one space at a time
			oneSpace = true;							//one-step mode of play
			if( kt.isAlive( ) == false ){			//if game not running, then start
				kt = new Thread( this );
				kt.start( );
			}
			kt.resume( );								//after each move, game suspends thread
			return;
		}
		oneSpace = false;								//continuous mode of play
		
		if( e.getSource( ).equals( pause ) ){	//suspends or resumes when clicked
			if( running ) {
				kt.suspend( );
				running = false;
			}
			else {
				kt.resume( );
				running = true;
			}
			return;
		}

		if( e.getSource( ).equals( start ) )		//set speed for continuous play
			millisec = 60;
		else if( e.getSource( ).equals( faster ) )
			millisec = 0;
		else if( e.getSource( ).equals( slower ) )
			millisec = 400;
			
		oneSpace = false;								//continuous mode of play
		kt.resume( );
		if( kt.isAlive( ) == false ) {
			kt = new Thread( this );
			kt.start( );
		}
	}
//**************************************************run( )
	public void run( ) {
		
		setUp( );			// initialize values to start game over
		gContext.setColor( Color.white );		
		gContext.fillRect( 0, 0, 600, 400 );
		
		gContext.setColor( Color.blue );
		gContext.setFont( new Font( "SansSerif", Font.PLAIN, 18 ) );
		gContext.drawString("A tour is hitting each square", 350, 250 );
		gContext.drawString("on the board only once", 350, 275 );
		
		for( int i=0; i<8; i++ )				// draw the board
			for( int j=0; j<8; j++ ) 
				kk[i][j].draw(gContext);		
		kk[pos[0]] [pos[1]].knightBeginEnd(gContext);	//mark starting square
		repaint( );
		while ( success )					// determines next move, updates pos[ ]
		{										// success = true untill last move.
			success = evaluate ( pos );
				
			board[pos[0]][pos[1]] = true;		// mark position true.
	
			kk[pos[0]] [pos[1]].knight(gContext);	// display new move on square.
			kk[pos[0]] [pos[1]].line( gContext, pos[2], pos[3] );
			repaint( );
			delay( );
		} 
		kk[pos[0]] [pos[1]].draw(gContext);					//mark last move
		kk[pos[0]] [pos[1]].knightBeginEnd(gContext);		
		kk[pos[0]] [pos[1]].line( gContext, pos[2], pos[3] );
		repaint( );
		
		gContext.setColor( Color.red );
		gContext.setFont( new Font( "SansSerif", Font.PLAIN, 30 ) );
		gContext.drawString( " Game over ", 380, 105 );
		if( testForWin( ) ) {
			gContext.setFont( new Font( "SansSerif", Font.PLAIN, 36 ) );
			gContext.drawString( "Congratulations ", 350, 145 );
			gContext.drawString( "You did it!"        , 350, 190 );
		repaint( );
		}else
			gContext.drawString( " Try again ", 380, 130 );
		repaint( );
	}
//************************************************** paint( )
	public void paint( Graphics g ) {
		g.drawImage( buffer, 0, 0, this );
	}
//************************************************** update( )
	public void update( Graphics g ) { paint( g ); }

//**************************************** methods supporting paint( )
	private void setUp( ) {
		for (int i=0; i<8; i++)			// initialize board to all squares false
			for (int j=0; j<8; j++)
				board[i][j] = false;
		success = true;						// initialize "game continues".
		pos[0] = 0; pos[1] = 7;				// initialize starting position.
		board[pos[0]][pos[1]] = true;		// Sets the starting square to true.
	}
//***********************************************testForWin( )
	private boolean testForWin( ) {
		for( int i=0; i<8; i++ )
			for( int j=0; j<8; j++ )
				if ( !board[i][j] )			//a square on the board not occupied
					return false;
		return true;
	}
//******************************************************delay( )
	private void delay( ) {
		if( oneSpace ) {
			kt.suspend( );
			return;
		}
		try {
			Thread.sleep( millisec );
		}catch( InterruptedException ex ) {
			System.err.println( ex.toString( ) );
		}
}	
//*****************************************************************
	public void controllPanel( ) {
		title = new Label( "Knight's Tour  " );
		title.setFont( new Font( "SansSerif", Font.BOLD+Font.ITALIC, 22 ) );
		add ( title );						//font SansSerif is Helvetica on IE

		setFont( new Font( "SansSerif", Font.PLAIN, 16 ) );

		start = new Button( "go" );	
		faster = new Button( "faster" );
		slower = new Button( "slower" );
		pause = new Button( "pause/resume" );
		single = new Button( "single space" );
		
		start.addActionListener( this );
		faster.addActionListener( this );
		slower.addActionListener( this );
		pause.addActionListener( this );
		single.addActionListener( this );

		add( start );
		add( faster );
		add( slower );
		add( pause );
		add( single );
	}
//**************************************** methods to find best move
/* how knight's moves are determined: moves[ ][ ] contains 8 sets of x
 * and y moves allowed for a knight, relative to current position.
 * First loop tests all 8 for validity--on the chess board and not on
 * a used square.  Qualifying moves call rateMove(int x, int y), which
 * repeats the operation to find all possible 2nd moves.  These are
 * counted up, and the number is the "rating".  Dead-end moves are
 * rated highest.  low( ) chooses to lowest rated move.  This is the
 * square least accessable from other squares, and it is the next move.
 * To improve: look ahead one more move for any dead-end moves, which
 * indicate that the game would be lost.
 */
	private boolean evaluate( int pos[ ] ) {
		int rating[ ] = new int[8];
		int x = 0, y = 0;
		
		for ( int i=0; i<8; i++ )			// 8 basic moves.
		{
			x = pos[0] + moves[i][0];		// calculate.
			y = pos[1] + moves[i][1];

			rating[i] = 10;					// off board, used space.
			if ( x >= 0 && x < 8 )			// validate.
				if ( y >= 0 && y < 8 )
					if ( !(board[x][y]) )
						rating[i] = rateMove( x, y );				

		}
		int best = low( rating );
		if ( rating[best] == 10 )					// end game.  No valid choices.
			return false;
		else										// set new pos[ ] values.
		{
			pos[2] = pos[0];					// save previous positions
			pos[3] = pos[1];
			pos[0] = pos[0] + moves[best][0];	// move the knight
			pos[1] = pos[1] + moves[best][1];
			return true;
		}

	}
	private int low( int rating[ ] ) {
		int sub = 0;							// hold subscript of lowest rated move.
		int lowest = 10;						// compare to high value.
		
		for ( int i=0; i<8; i++ )
		{
			if ( rating[i] < lowest ) {		// compare.
				sub = i;
				lowest = rating[i];
			}
			else if ( rating[i] == lowest )		// randomize equal choices.
				if ( Math.random( ) < .5 ) {
					sub = i;
					lowest = rating[i];
				}
		}
		return sub;
	}
	private int rateMove( int xx, int yy ) {
		int count = 0;
		for ( int i=0; i<8; i++ ) 
			if ( xx + moves[i][0] >= 0 && xx + moves[i][0] < 8 )
				if ( yy + moves[i][1] >= 0 && yy + moves[i][1] < 8 )
					if ( !( board[xx+moves[i][0]] [yy+moves[i][1]]) )
						count++;

		if ( count < 1 )			// can only move back where it came from.
			return 9;
		else 
			return count;
	}
}

*******************************
*******************************
*******************************

// ChessSquare.java      David Fourer
// for Knight.java, display graphics

import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;

public class ChessSquare {

	int size;				// pixals;
	int xx;					// top left corner of whole board
	int yy;
	int xPlace;				//	2 values from 0 to 7 = 64 squares
	int yPlace;
	
	//****************************************** constructor

	ChessSquare( int s, int x, int y, int xp, int yp ) {
		size = s;
		xx = x;
		yy = y;
		xPlace = xp;
		yPlace = yp;
	}
	//**************************************** public methods
	
	//____________________________________________________draw( )
												//draws blank squares of chess board
	public void draw( Graphics g ) {					
		if( (xPlace + yPlace) %2 == 0 )
			g.setColor( new Color( 60,40,100 ) );
		else
			g.setColor( new Color( 220,200,200 ) );
		g.fillRect( xx+xPlace*size, yy+yPlace*size, size-2, size-2 );
	}
	//________________________________________________________knight( )
												//marks each square hit with "K"
	public void knight( Graphics g ) {				
		g.setColor( new Color(255,50,100) );
		g.setFont( new Font( "Serif", Font.BOLD, 30 ) );
		g.drawString( "K", xx+xPlace*size+size/5, yy+yPlace*size+(size*3)/4 );
	}
	//______________________________________________________knightBeginEnd( )
				//mark starting square different than others, also finnish square
	public void knightBeginEnd( Graphics g ) {	
		g.setColor( new Color(255,50,100) );		//and last squares
		g.fillOval( xx+xPlace*size+size/4,
						yy+yPlace*size+size/4, size/2, size/2 );
	}
	//__________________________________________________________line( )	
			//draw thick line between calling object's square and previous square
	public void line( Graphics g, int newX, int newY ) {
		g.setColor( new Color(100,255,50) );		
		int a,b,c,d;
		a = xx+xPlace*size+size/2;			
		b = yy+yPlace*size+size/2;
		c = xx+  newX*size+size/2;
		d = yy+  newY*size+size/2;

		g.drawLine( a, b, c, d  );
		g.drawLine( a+1, b, c+1, d );
		g.drawLine( a, b+1, c, d+1 );
		g.drawLine( a-1, b, c-1, d );
		g.drawLine( a, b-1, c, d-1 );
	}
}