public class KnightTour {
static int N = 8;
static boolean solveNT() {
int[][] board = new int[N][N];
for(int[] arr:board){
Arrays.fill(arr,-1);
}
int[] xMove = { 2, 1, -1, -2, -2, -1, 1, 2 };
int[] yMove = { 1, 2, 2, 1, -1, -2, -2, -1 };
board[0][0] = 10;
if(!solveKTUtil(0,0, board[0][0]+1, board, xMove, yMove)){
System.out.println("Solution Dsnt exist");
return false;
}
return true;
}
private static void printBoard(int[][] board) {
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
int num = board[i][j];
if(num<10){
System.out.print(num+" ");
}else{
System.out.print(num+" ");
}
}
System.out.println();
}
}
private static boolean solveKTUtil(int x, int y, int moveI,
int[][] board, int[] xMove, int[] yMove) {
int nextX, nextY;
if(N*N+board[0][0] == moveI){
printBoard(board);
return true;
}
for(int i=0;i<N; i++){
nextX = x + xMove[i];
nextY = y + yMove[i];
if(isSafe(nextX, nextY, board)){
board[nextX][nextY] = moveI;
if(solveKTUtil(nextX, nextY, moveI+1, board, xMove, yMove)){
return true;
}else{
board[nextX][nextY] = -1;
}
}
}
return false;
}
private static boolean isSafe(int nextX, int nextY, int[][] board) {
return nextX >=0 && nextX <N && nextY>=0 &&
nextY <N && board[nextX][nextY] == -1;
}
public static void main(String[] args) {
solveNT();
}
}