Hello, I was solving the problem of Knight in a funky Chessboard.
The main thing about the problem was - Suppose the chessboard is not square, but instead has rows with variable numbers of columns, and with each row offset zero or more columns to the right of the row above it. The figure to the left illustrates one possible configuration. How many of the squares in such a modified chessboard can a knight, starting in the upper left square (marked with an asterisk), not reach in any number of moves without resting in any square more than once? Minimize this number.
The code I’ve written -
static int[] rowIndices = { -1, -2, -2, -1, +1, +2, +2, +2 };
static int[] colIndices = { -2, -1, +1, +2, +2, +1, -1, -2 };
static int minCount = 0;
static void funkyChessBoard(int[][] board, int row, int col, int count) {
minCount = Math.min(minCount, count);
for (int i = 0; i < rowIndices.length; i++) {
int nextRow = row + rowIndices[i];
int nextCol = col + colIndices[i];
if (canPlace(board, nextRow, nextCol)) {
board[nextRow][nextCol] = 2; // 2 = knight placed
funkyChessBoard(board, nextRow, nextCol, count - 1);
board[nextRow][nextCol] = 1; // 1 = knight removed
}
}
}
private static boolean canPlace(int[][] board, int i, int j) {
int N = board[0].length;
if (i < 0 || j < 0 || i >= N || j >= N || board[i][j] != 1)
return false;
return true;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[][] board = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int value = sc.nextInt();
if(value == 1) minCount++;
board[i][j] = value;
}
}
funkyChessBoard(board, 0, 0, minCount);
System.out.println(minCount);
}
Now, for the input
10
1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 1 1 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1
The actual ans is 17 but the code written above gives 19 as the answer.
Can someone suggest me what should be done for this? Since this is based on recursion and backtracking and also for the smaller inputs, the output is fine so debugging it is a little difficult.