/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/**
 * knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. 
 * If the knight ends on a square that is one knight's move from the beginning square 
 * (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open.
 *
 * Knights tour problem : http://en.wikipedia.org/wiki/Knight%27s_tour
 */
class Ideone {
	public static void main(String[] args){
		int n = 8;
 
		//knight can move 3cells in L shape at a time
		//Prepare combinations of possible x&y direction moves of knight
 
		//below array represents possible moves in x&y directions with values (x[i],y[i]) and sum will be 3
		int[] x = {1, 2, -1, -2,  1, -2, -1,  2}; 		
		int[] y = {2, 1, -2, -1, -2,  1,  2, -1};
 
		//Initialize a matrix to hold the path solution
		int[][] solution = new int[n][n];
 
		//Initialise solution matrix to default values. default value is -1
		for(int i=0; i <n; i++){
			for(int j=0; j< n; j++){
				solution[i][j] = -1;
			}
		}
 
		//Start solving problem with move from (0,0) position
		solution[0][0] = 0;
 
		boolean solutionFound = trackKnightMoves(0, 0, x, y, solution, 1);
		if(solutionFound){
			printSolutions(solution);	
		}
	}
 
	private static void printSolutions(int[][] sol){
		for(int i=0; i< sol.length; i++){
			for(int j=0; j< sol.length; j++){
				System.out.println(" " + sol[i][j]+ " ");
			}
		}
	}
 
	/**
	* curX - to track current x position of knight
	* curY - to track current y position of knight
	* x    - possible x direction moves
	* y    - possible y direction moves
	* solution - to track path of knight
	* noOfMoves - count of moves in a solution(to track end of traversal)
	*/
	private static boolean trackKnightMoves(int curX, int curY, int[] x, int[] y, int[][] solution, int noOfMoves){
 
		if(noOfMoves == solution.length * solution.length){
			System.out.println("No of moves => "+ noOfMoves);
			return true;
		}		
 
		for(int k=0; k<solution.length; k++){
			int nextXMove = curX + x[k];
			int nextYMove = curY + y[k];
 
			//Check if next move is safe or not
			if(isSafeMove(nextXMove, nextYMove, solution)){
				solution[nextXMove][nextYMove] = noOfMoves;
				if(trackKnightMoves(nextXMove, nextYMove, x, y, solution, noOfMoves+1)){
					return true;
				}else{//back track
					solution[nextXMove][nextYMove] = -1;
				}
			}
		}	
		return false;
	}
 
	/*
	 * Before taking next step, check whether it is safe to move in that direction or not
	 */
	private static boolean isSafeMove(int x, int y, int[][] solution){
		if(x >=0 && x<solution.length && y >= 0 && y < solution.length && solution[x][y] == -1){
			return true;
		}else {
			return false;
		}	
	} 
}