Untitled
unknown
plain_text
2 months ago
2.1 kB
4
Indexable
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(); } }
Editor is loading...
Leave a Comment