//Garth Bruen
//Septemeber, 2002
//Interactive and command line args version

//import utils.SavitchIn;
//import utils.OutFmt;

/**************************
*This original code is free
*to copy modify and resuse
***************************/


/***********************************************
*
*	To solve this I used Warnsdorf's approach
*	which says the best move is the one that
*	has has the least number of possible moves
*	following that move. 
*
**************************************************/



class KnightMoves
{

        public static void main(String[] args)
        {
	int size = 0, posX = 0, posY = 0, mode;
	

	try{

		size = Integer.parseInt(args[0]);
		posX = Integer.parseInt(args[1]);
		posY = Integer.parseInt(args[2]);
		mode = 0;	//Set mode to command line args
	}

	catch(Exception e){
		// If no initial agrs are given, default values are set	
				
			size = 8;
			posX = 2; posY = 2;
			mode = 1;	//Interactive mode, promts user for input
	}


	//System.out.println("mode is: "+mode);
	char k = 'k'; 
	int moveCount = 1; //Initialize the move counter
	int lastSq = size*size; //Determine what the 
	char board[][] = new char[size][size];	//Array of live board
	int storeMoves[][] = new int[size][size]; //a seperate array to store all the moves
	
			
	board[posX][posY] = k;
	storeMoves[posX][posY] = moveCount;
	int nextMove = 0;

	if(mode == 1){
		printBoard(board, size);
	}
	//Only print if we are in interactive mode

	nextMove = bestMove(storeMoves, size, posX, posY);
	
	int menuOp = -1;

	/*
	*while conditions
	*
	*	-move count should be less than the board size
	*	-user can quit with 12	
	*	-a zero value for menuOp or 
	*		nextMove indicates that no moves are left
	*
	*/

	while((moveCount<(size*size))&(menuOp != 12)&(menuOp != 0)&(nextMove!=0)){

	
		if(mode == 1){
			System.out.println("The next move is "+nextMove);
			printMenu();
			System.out.print("> ");
			menuOp = SavitchIn.readInt();
			nextMove = menuOp;
		}//Only print if in interactive mode
		
				
		switch(nextMove){
			case 0:
				break;

			case 1:
				if(isLegalMove(storeMoves, size, (posX-2), (posY-1)) == true){
					moveCount++;
					move(size, board, posX, posY, (posX-2), (posY-1)); 
					if(mode == 1){
					printBoard(board, size);}
					posX = findXpos(board, size);
					posY = findYpos(board, size);
					storeMoves[posX][posY] = moveCount;
					nextMove = bestMove(storeMoves, size, posX, posY);
				}
				else
				{
					
					System.out.print("Illegal move: X="+(posX-2)+", Y="+(posY-1));
					printBoard(board, size);	
					
				}
				break;
			case 2:
				if(isLegalMove(storeMoves, size, (posX-2), (posY+1)) == true){
					moveCount++;
					move(size, board, posX, posY, (posX-2), (posY+1)); 
					if(mode == 1){
						printBoard(board, size);}
					posX = findXpos(board, size);
					posY = findYpos(board, size);
					storeMoves[posX][posY] = moveCount;
					nextMove = bestMove(storeMoves, size, posX, posY);
				}
				else
				{
					
					System.out.print("Illegal move: X="+(posX-2)+", Y="+(posY+1));
					printBoard(board, size);
					
				}
				break;
			case 3:
				if(isLegalMove(storeMoves, size, (posX-1), (posY-2)) == true){
					moveCount++;
					move(size, board, posX, posY, (posX-1), (posY-2)); 
					if(mode == 1){
						printBoard(board, size);}
					posX = findXpos(board, size);
					posY = findYpos(board, size);
					storeMoves[posX][posY] = moveCount;
					nextMove = bestMove(storeMoves, size, posX, posY);
				}
				else
				{
					System.out.print("Illegal move: X="+(posX-1)+", Y="+(posY-2));
					printBoard(board, size);
					
				}
				break;
			case 4:
				if(isLegalMove(storeMoves, size, (posX-1), (posY+2)) == true){
					moveCount++;
					move(size, board, posX, posY, (posX-1), (posY+2)); 
					if(mode == 1){
						printBoard(board, size);}
					posX = findXpos(board, size);
					posY = findYpos(board, size);
					storeMoves[posX][posY] = moveCount;
					nextMove = bestMove(storeMoves, size, posX, posY);
				}
				else
				{
					
					System.out.print("Illegal move: X="+(posX-1)+", Y="+(posY+2));
					printBoard(board, size);
					
				}

				break;
			case 5:
				if(isLegalMove(storeMoves, size, (posX+1), (posY-2)) == true){
					moveCount++;
					move(size, board, posX, posY, (posX+1), (posY-2)); 
					if(mode == 1){
						printBoard(board, size);}
					posX = findXpos(board, size);
					posY = findYpos(board, size);
					storeMoves[posX][posY] = moveCount;
					nextMove = bestMove(storeMoves, size, posX, posY);
				}
				else
				{
					
					System.out.print("Illegal move: X="+(posX+1)+", Y="+(posY-2));
					printBoard(board, size);
				}
				break;
			case 6:
				if(isLegalMove(storeMoves, size, (posX+1), (posY+2)) == true){
					moveCount++;
					move(size, board, posX, posY, (posX+1), (posY+2)); 
					if(mode == 1){
						printBoard(board, size);}
					posX = findXpos(board, size);
					posY = findYpos(board, size);
					storeMoves[posX][posY] = moveCount;
					nextMove = bestMove(storeMoves, size, posX, posY);
				}
				else
				{
					
					System.out.print("Illegal move: X="+(posX+1)+", Y="+(posY+2));
					printBoard(board, size);
				}
				break;
			case 7:
				if(isLegalMove(storeMoves, size, (posX+2), (posY-1)) == true){
					moveCount++;
					move(size, board, posX, posY, (posX+2), (posY-1)); 
					if(mode == 1){
						printBoard(board, size);}
					posX = findXpos(board, size);
					posY = findYpos(board, size);
					storeMoves[posX][posY] = moveCount;
					nextMove = bestMove(storeMoves, size, posX, posY);
				}
				else
				{
					if(mode == 1){
					System.out.print("Illegal move: X="+(posX+2)+", Y="+(posY-1));
					printBoard(board, size);}
				}
				break;
			case 8:
				if(isLegalMove(storeMoves, size, (posX+2), (posY+1)) == true){
					moveCount++;
					move(size, board, posX, posY, (posX+2), (posY+1)); 
					if(mode == 1){
						printBoard(board, size);}
					posX = findXpos(board, size);
					posY = findYpos(board, size);
					storeMoves[posX][posY] = moveCount;
					nextMove = bestMove(storeMoves, size, posX, posY);
					
				}
				else
				{
					
					System.out.print("Illegal move: X="+(posX+2)+", Y="+(posY+1));
					printBoard(board, size);
				}

				break;
			case 9:
				resetBoard(board, size);
				resetRecord(storeMoves, size);
				posX = findXpos(board, size);
				posY = findYpos(board, size);
				moveCount = 1;
				printBoard(board, size);
				break;
			case 10:
				printRecord(storeMoves, size);break;
			case 11: 
				help(); break;
			case 12: 
				System.out.println("Ok...");break;
			default: 
				System.out.println(nextMove + "is not an option");break;
		}

	}
	
	/* End Sequence 
	*
	*	Special section to handle the last move,
	*	determine if the solution is found and
	*	print out the results
	*/

	if((moveCount==(size*size))&&(nextMove==0)){
		System.out.println("Done!");
		printRecord(storeMoves, size);
	}else{
		System.out.println("Problem unsolved");
		printRecord(storeMoves, size);		
	}

	/*If there are no moves left and the
	* move count matches the size of the board
	* then we have success!
	*/


        }//end main


/***********************************************************************/
/***********************************************************************/

/*	METHODS		
*
*	printMenu() holds the list of options
*	bestMove() tests the 8 differnt moves
*	exploreMove() explores an individual move option
*	move() actually "moves" the pieces by updating the board arrays
*	resetBoard() changes the live board back to starting point
*	resetRecord() changes the move record back to starting point
*	findXpos() works with findYpos() to locate the live piece on the board
*	findYpos() works with findXpos() to locate the live piece on the board
*	printRecord() prints the record of moves
*	printBoard() prints the live board
*	isLegalMove() tests to see if each move is not off the board or occupied
*	help() information about the program
*
*
*
*/

/*	
* Method prints the menu of options  	
* if in interactive mode
*/

	public static void printMenu(){
		System.out.println("Menu Options:");
		System.out.println();
		System.out.print("1 - Move 1 up 2, left 1\t\t");
		System.out.println("2 - Move 2 up 2, right 1");
		System.out.print("3 - Move 3 up 1, left 2\t\t");
		System.out.println("4 - Move 4 up 1, right 2");
		System.out.print("5 - Move 5 down 1, left 2\t");
		System.out.println("6 - Move 6 down 1, right 2");
		System.out.print("7 - Move 7 down 2, left 1\t");
		System.out.println("8 - Move 8 down 2, right 1");
		System.out.print("9 - Reset Board\t\t");
		System.out.println("10 - View moves");
		System.out.print("11 - Help\t\t");
		System.out.println("12 - Quit");

	}//end print menu

/*
* 	Tests various moves recursively. If a move is a legal move,
*	that position is resubmitted to find the next move(s) from
*	there. It continues recursively until the various moves have
*	been checked.
*
*	the board size and move are passed to isLegalMove()
*	If it's legal the move is passed to exploreMove() to 
*		see how many moves are possible from there
*	The lowest moves are compared with others in the nex if statement
*
*
*
*
*/

	public static int bestMove(int recBoard[][], int size, int posX, int posY){
		int posMoves = 0, lowestMoves = 8, bestMove = 0; boolean lastMove = false;

		if(isLegalMove(recBoard, size, (posX-2), (posY-1))==true){
			posMoves = exploreMove(recBoard, size, (posX-2), (posY-1), lastMove);
			if((posMoves != 0)&&(posMoves < lowestMoves)){
				lowestMoves = posMoves;
				bestMove = 1;
			}
		}	
		if(isLegalMove(recBoard, size, (posX-2), (posY+1))==true){
			posMoves = exploreMove(recBoard, size, (posX-2), (posY+1), lastMove);
			if((posMoves != 0)&&(posMoves < lowestMoves)){
				lowestMoves = posMoves;
				bestMove = 2;
			}
		}	
		if(isLegalMove(recBoard, size, (posX-1), (posY-2))==true){
			posMoves = exploreMove(recBoard, size, (posX-1), (posY-2), lastMove);
			if((posMoves != 0)&&(posMoves < lowestMoves)){
				lowestMoves = posMoves;
				bestMove = 3;
			}
		}	
		if(isLegalMove(recBoard, size, (posX-1), (posY+2))==true){
			posMoves = exploreMove(recBoard, size, (posX-1), (posY+2), lastMove);
			if((posMoves != 0)&&(posMoves < lowestMoves)){
				lowestMoves = posMoves;
				bestMove = 4;
			}
		}	
		if(isLegalMove(recBoard, size, (posX+1), (posY-2))==true){
			posMoves = exploreMove(recBoard, size, (posX+1), (posY-2), lastMove);
			if((posMoves != 0)&&(posMoves < lowestMoves)){
				lowestMoves = posMoves;
				bestMove = 5;
			}
		}	
		if(isLegalMove(recBoard, size, (posX+1), (posY+2))==true){
			posMoves = exploreMove(recBoard, size, (posX+1), (posY+2), lastMove);
			if((posMoves != 0)&&(posMoves < lowestMoves)){
				lowestMoves = posMoves;
				bestMove = 6;
			}
		}	
		if(isLegalMove(recBoard, size, (posX+2), (posY-1))==true){
			posMoves = exploreMove(recBoard, size, (posX+2), (posY-1), lastMove);
			if((posMoves != 0)&&(posMoves < lowestMoves)){
				lowestMoves = posMoves;
				bestMove = 7;
			}
		}	
		if(isLegalMove(recBoard, size, (posX+2), (posY+1))==true){
			posMoves = exploreMove(recBoard, size, (posX+2), (posY+1), lastMove);
			if((posMoves != 0)&&(posMoves < lowestMoves)){
				lowestMoves = posMoves;
				bestMove = 8;
			}
		}	
		
		/*Get the last legal move and check for end of game*/
		if(bestMove == 0){
			lastMove = true;
			
			bestMove = exploreMove(recBoard, size, posX, posY, lastMove);
			//if(bestMove != 0){
			//	System.out.println("This is the last legal move.");
			//}
		}

		return bestMove;
	}//end bestMove()


/*
*	Explores various moves to see how many possible
*	moves there are from a given position.
*	The "best" move is the one that has the least options
*
*
*
*/



	public static int exploreMove(int recBoard[][], int size, int posX, int posY, boolean lastMove){
		int possMoves= 0; int moveNum = 0;
		
		if(isLegalMove(recBoard, size, (posX-2), (posY-1))==true){ possMoves++;
		moveNum = 1;}
		if(isLegalMove(recBoard, size, (posX-2), (posY+1))==true){ possMoves++;
		moveNum = 2;}
		if(isLegalMove(recBoard, size, (posX-1), (posY-2))==true){ possMoves++;
		moveNum = 3;}
		if(isLegalMove(recBoard, size, (posX-1), (posY+2))==true){ possMoves++;
		moveNum = 4;}
		if(isLegalMove(recBoard, size, (posX+1), (posY-2))==true){ possMoves++;
		moveNum = 5;}
		if(isLegalMove(recBoard, size, (posX+1), (posY+2))==true){ possMoves++;
		moveNum = 6;}
		if(isLegalMove(recBoard, size, (posX+2), (posY-1))==true){ possMoves++;
		moveNum = 7;}
		if(isLegalMove(recBoard, size, (posX+2), (posY+1))==true){ possMoves++;
		moveNum = 8;}

		if(lastMove==true){
			possMoves = moveNum;
		}
		return possMoves;

	}//end exploreMove()


/* 	
*  This method actaully executes the move, updating the live board
*
*  
*/


	public static char[][] move(int size, char board[][], int posX, int posY, int newX, int newY){
		char k = board[posX][posY];
		
		//System.out.println("X="+newX+", Y="+newY);	
		board[posX][posY] = ' ';			//reset old position
		board[newX][newY] = k;				//set new position
		return board;
		
	}


/* 
*   These two methods will reset the board and the move record
*/

	public static char[][] resetBoard(char board[][], int size){
		for(int i = 0; i<size; i++){
			for(int j = 0; j<size; j++){
				board[i][j] =' ';			
			}
		}
		board[0][0] = 'k';

		return board;
	}
	public static int[][] resetRecord(int board[][], int size){
		for(int i = 0; i<size; i++){
			for(int j = 0; j<size; j++){
				board[i][j] =0;			
			}
		}
		board[0][0] = 1;

		return board;
	}


/* 
* These two methods locate the current position of the knight
* on the live board
*/

	public static int findXpos(char board[][], int size){
		int posX = -1;
		for(int i = 0; i < size; i++){
			for(int j = 0; j < size; j++){
				if(board[i][j] == 'k'){
					posX = i;
				}
			}
		}		
		return posX;
	}//end findXpos

	public static int findYpos(char board[][], int size){
		int posY = -1;
		for(int i = 0; i < size; i++){
			for(int j = 0; j < size; j++){
				if(board[i][j] == 'k'){
					posY = j;
				}
			}
		}		
		return posY;
	}//end findYpos

/* These two methods print the live board after each move 
*  the record of moves on demand and the final board positions
*  at the end
*/

	public static void printRecord(int board[][], int size){
		
		System.out.println("Move Record");
		System.out.print("  ");
		for(int h = 0; h < size; h++){
			System.out.print(h+" ");
		}
		System.out.println();
		for(int i = 0; i < size; i++){
			System.out.print(i+" ");
			for(int j = 0; j < size; j++){
				System.out.print(board[i][j]+" ");
			}
			System.out.println();
		}
	}//end printRecord()

	public static void printBoard(char board[][], int size){
		
		System.out.println();
		System.out.print("  ");
		for(int h = 0; h < size; h++){
			System.out.print(h+" ");
		}
		System.out.println();
		for(int i = 0; i < size; i++){
			System.out.print(i+" ");
			for(int j = 0; j < size; j++){
				System.out.print(board[i][j]+" ");
			}
			System.out.println();
		}		
	}//end printBoard()


/* This method checks to see if a move is legal.
*	There are two ways a move can be illegal:
*		1. It is off the board
*		2. The space has already been visited
*/


	public static boolean isLegalMove(int recBoard[][], int size, int posX, int posY){
		boolean isLegal = false;
		
		if(((posX>=0)&&(posX<size))&&((posY>=0)&&(posY<size))){
			if(recBoard[posX][posY] == 0){
				isLegal = true;
			}
			else{
				isLegal = false;
			}
		}
		else{
			isLegal = false;
		}	

			
	return isLegal;
	}//end isLegalMove()



/* 
* Help method. Tells the user the point
* of the game and how to make moves
*
* 
*/

	public static void help(){
		System.out.print("The point of this is to move a knight onto all of the ");
		System.out.print("spaces on chess board only once. Kights move in an L ");
		System.out.print("type fashion. They move 1 or 2 spaces in one direction ");
		System.out.print("and then 1 or 2 spaces in perpendicular direction for a total of three spaces.");
		System.out.println();
		System.out.println("Example: ");
		System.out.println("  0 1 2 3");
		System.out.println("0   k");
		System.out.println("1   |");
		System.out.println("2   |-k");
		System.out.println("3");
		System.out.print("You see that the knight was in 0 1 and moved to 2 2. It could have also been moved to 3 1 or 2 0.");
		System.out.print("You may select the moves by number from the menu. After each move you will be given a move suggestion for the next move.");
	}


}//end class