Untitled

import java.util.Arrays;

public class KnightsTour {
    // Possible moves of a knight
    private static final int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
    private static final int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};

    public int[][] knightsTour(int m, int n, int r, int c) {
        int[][] board = new int[m][n];
        for (int[] row : board) {
            Arrays.fill(row, -1); // Initialize with -1 (unvisited)
        }

        // Start backtracking from the initial position
        if (backtrack(board, m, n, r, c, 0)) {
            return board;
        }
        return new int[][]{}; // Return empty if no solution
    }

    private boolean backtrack(int[][] board, int m, int n, int x, int y, int moveCount) {
        // Mark the current cell with the move count
        board[x][y] = moveCount;

        // Base case: All cells have been visited
        if (moveCount == m * n - 1) {
            return true;
        }

        // Explore all possible knight moves
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (isValidMove(board, m, n, nx, ny)) {
                if (backtrack(board, m, n, nx, ny, moveCount + 1)) {
                    return true; // Found a solution
                }
            }
        }

        // Undo the move (backtrack)
        board[x][y] = -1;
        return false; // No valid moves from this state
    }

    private boolean isValidMove(int[][] board, int m, int n, int x, int y) {
        return x >= 0 && y >= 0 && x < m && y < n && board[x][y] == -1;
    }

    public static void main(String[] args) {
        KnightsTour kt = new KnightsTour();

        // Example test cases
        int[][] result1 = kt.knightsTour(1, 1, 0, 0);
        printBoard(result1);

        int[][] result2 = kt.knightsTour(3, 4, 0, 0);
        printBoard(result2);
    }

    private static void printBoard(int[][] board) {
        for (int[] row : board) {
            System.out.println(Arrays.toString(row));
        }
        System.out.println();
    }
}