Untitled

public class Solution {
  
    public static int[][] knightTour(int n, int m) {
       int[][] chessBoard = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				chessBoard[i][j] = -1;
			}
		}

		chessBoard[0][0] = 0;
		int[] rowArray = { 1, -1, 2, 2, -1, 1, -2, -2 };
		int[] colArray = { 2, 2, -1, 1, -2, -2, -1, 1 };

		knightTour2(chessBoard, rowArray, colArray, 1, 0, 0, n, m);

		return chessBoard;

	}

	public static boolean knightTour2(int[][] board, int[] rowA, int[] colA, int step, int currR, int currC, int n,
			int m) {
		if (step == n * m)
			return true;

		for (int i = 0; i < 8; i++) {
			int nextR = currR + rowA[i];
			int nextC = currC + colA[i];
			if (isValidMove(board, nextR, nextC,n,m)) {
				board[nextR][nextC] = step;
				boolean flag = knightTour2(board, rowA, colA, step + 1, nextR, nextC, n,m);
				if (flag)
					return true;
				else {
					board[nextR][nextC] = -1;
				}
			}
		}
		return false;

	}

	public static boolean isValidMove( int[][] board, int r, int c, int n, int m) {
		return (r >= 0 && c >= 0 && r<n && c<m && board[r][c] == -1);

	}

}