import java.io.*;
import java.text.DecimalFormat;

public class Lab26b100
{
	public static void main (String args[]) throws IOException
	{
		System.out.println("\nLab26b 90/100 Point Version\n");
		Knight knight = new Knight();
		knight.getStart();
		knight.solveTour();
		knight.displayBoard();
	}
}

class Knight
{
	boolean debug = false;
	private int board[][];		// stores the sequence of knight moves
	private boolean used[][];
	private int startRow;		// row location where the knight starts
	private int startCol;		// col location where the knight starts
	private int rowPos;			// current row position of the knight
	private int colPos;			// current col position of the knight
	private int moves;			// number of location visited by the knight
	BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
	DecimalFormat f = new DecimalFormat("00");
	private int low;
	private int coords[][];
	final private int ACCESS[][] = {{0,0,0,0,0,0,0,0,0,0,0,0},
 						 			{0,0,0,0,0,0,0,0,0,0,0,0},
 					 				{0,0,2,3,4,4,4,4,3,2,0,0},
 					 				{0,0,3,4,6,6,6,6,4,3,0,0},
 					 				{0,0,4,6,8,8,8,8,6,4,0,0},
 					 				{0,0,4,6,8,8,8,8,6,4,0,0},
 					 				{0,0,4,6,8,8,8,8,6,4,0,0},
 					 				{0,0,4,6,8,8,8,8,6,4,0,0},
 					 				{0,0,3,4,6,6,6,6,4,3,0,0},
 					 				{0,0,2,3,4,4,4,4,3,2,0,0},
 					 				{0,0,0,0,0,0,0,0,0,0,0,0},
 					 				{0,0,0,0,0,0,0,0,0,0,0,0}}; 

	public Knight()
	// constructor used to initializes the data attributes
	{   
		board = new int[8][8];
		used = new boolean [8][8];
		startRow = 0;
		startCol = 0;
		moves = 0;
	}
	
	public void getStart() throws IOException
	// input method to get starting row and col from keyboard entry
	{    
		boolean invalid = true;
		
		while(invalid)
		{
			System.out.print("Enter row start  ==>>  ");
			startRow = Integer.parseInt(b.readLine());
			if(startRow < 1 || startRow > 8)
				invalid = true;
			else
				invalid = false;
		}
		
		invalid = true;
		while(invalid)
		{
			System.out.print("Enter col start  ==>>  ");
			startCol = Integer.parseInt(b.readLine());
			if(startCol < 1 || startCol > 8)
				invalid = true;
			else 
				invalid = false;
		}
		
		rowPos = startRow-1;
		colPos = startCol-1;
		System.out.println();
	}
   
	public void displayBoard()
	// displays the chessboard after the tour is concluded
	{
		for(int r=0; r<8;r++)
			{
				for(int c=0; c<8;c++)
					System.out.print(f.format(board[c][r]) + "  ");
				System.out.println();
			}
		
		System.out.println("\nThe knight made " + moves + " moves");
	}

	private boolean getMove()
	// computes the next available knight's move.  Alters RowPos and ColPos and
	// returns true if move is possible, otherwise returns false
	{
		coords = new int[9][3];
		boolean moveAvail = false;
					
			if(colPos+2 < 8 && rowPos+1 < 8 && !used[colPos+2][rowPos+1]) // if the knight can go RIGHT and DOWN...return true
			{
				moveAvail = true;
				if(debug)
					System.out.println("R D");				
				coords[1][1] = colPos+2;
				coords[1][2] = rowPos+1;
			}
		 if(colPos+1 < 8 && rowPos+2 < 8 && !used[colPos+1][rowPos+2]) // if the knight can go DOWN and RIGHT...return true
			{
				moveAvail = true;
				if(debug)
					System.out.println("D R");
				coords[2][1] = colPos+1;
				coords[2][2] = rowPos+2;
			}
		 if(colPos-1 >= 0 && rowPos+2 < 8 && !used[colPos-1][rowPos+2]) // if the knight can go DOWN and LEFT...return true
			{
				moveAvail = true;
				if(debug)
					System.out.println("D L");
				coords[3][1] = colPos-1;
				coords[3][2] = rowPos+2;
			}
		 if(colPos-2 >= 0 && rowPos+1 < 8 && !used[colPos-2][rowPos+1]) // if the knight can go LEFT and DOWN...return true
			{
				moveAvail = true;
				if(debug)
					System.out.println("L D");
				coords[4][1] = colPos-2;
				coords[4][2] = rowPos+1;
			}		
		 if(colPos-2 >= 0 && rowPos-1 >= 0 && !used[colPos-2][rowPos-1]) // if the knight can go LEFT and UP...return true
			{
				moveAvail = true;
				if(debug)
					System.out.println("L U");
				coords[5][1] = colPos-2;
				coords[5][2] = rowPos-1;
			}		
		 if(colPos-1 >= 0 && rowPos-2 >= 0 && !used[colPos-1][rowPos-2]) // if the knight can go UP and LEFT...return true
			{
				moveAvail = true;
				if(debug)
					System.out.println("U L");
				coords[6][1] = colPos-1;
				coords[6][2] = rowPos-2;
			}	
		 if(colPos+1 < 8 && rowPos-2 >= 0 && !used[colPos+1][rowPos-2]) // if the knight can go UP and RIGHT...return true
			{
				moveAvail = true;
				if(debug)
					System.out.println("U R");
				coords[7][1] = colPos+1;
				coords[7][2] = rowPos-2;
			}
		 if(colPos+2 < 8 && rowPos-1 >= 0 && !used[colPos+2][rowPos-1]) // if the knight can go RIGHT and UP...return true
			{
				moveAvail = true;
				if(debug)
					System.out.println("R U");
				coords[8][1] = colPos+2;
				coords[8][2] = rowPos-1;
			}




		if(!moveAvail) return false;
		
		int low = 0;
		//while (coords[low][1] == 0) low++; 
		int a;
		int b;
		for(int k = 1; k<coords.length;k++)
			{
				a = ACCESS[coords[k][1]][coords[k][2]];
				b = ACCESS[coords[low][1]][coords[low][2]];
				if(a <= b && coords[k][1] > 0)
					low = k;
			}
		colPos = coords[low][1];
		rowPos = coords[low][2];
		used[colPos][rowPos] = true;
		
		return true; // default return
	}

	public void solveTour()
	// primary method that drives the knight's tour solution
	{
		do
		{
				moves++;
				board[colPos][rowPos] = moves;
		} while(getMove());
	}
}