import java.util.Scanner;

public class TrominoTiling {
private static String[][] board;
private static int size;

private static void fillBoard(int boardSize, int x, int y, int missingX, int missingY) {
// Base case for 2x2 board
if (boardSize == 2) {
String label = “T”; // Default label for tromino
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
if (x + j == missingX && y + i == missingY) continue; // Skip the missing square
board[y + i][x + j] = label;
}
}
return;
}

int halfSize = boardSize / 2;
int hx = x + halfSize / 2;
int hy = y + halfSize / 2;

// Determine the missing tile quadrant
if (missingX < hx && missingY < hy) { // Lower left quadrant
fillBoard(halfSize, x, y, missingX, missingY);
} else if (missingX >= hx && missingY < hy) { // Lower right quadrant
fillBoard(halfSize, hx, y, missingX, missingY);
} else if (missingX < hx && missingY >= hy) { // Upper left quadrant
fillBoard(halfSize, x, hy, missingX, missingY);
} else if (missingX >= hx && missingY >= hy) { // Upper right quadrant
fillBoard(halfSize, hx, hy, missingX, missingY);
}

// Place the tromino in the center to cover the hole made by the recursive quarter processing
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
if (board[y + hy / 2 + i][x + hx / 2 + j] == null) {
board[y + hy / 2 + i][x + hx / 2 + j] = “T”;
}
}
}
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Please enter size of board (need to be 2^n and 0 to quit): ");
size = scanner.nextInt();

// Quit if size is 0
if (size == 0) return;

// Validation for board size being a power of 2
if ((size & (size - 1)) != 0) {
System.out.println(“The entered size is not a power of 2. Exiting…”);
return;
}

System.out.print("Please enter coordinates of missing square (separated by a space): ");
int missingX = scanner.nextInt();
int missingY = scanner.nextInt();

// Check if the missing coordinates are within the board
if (missingX >= size || missingY >= size || missingX < 0 || missingY < 0) {
System.out.println(“Invalid coordinates. Exiting…”);
return;
}

board = new String[size][size]; // Initialize the board array
board[missingY][missingX] = “MS”; // Mark the missing square

fillBoard(size, 0, 0, missingX, missingY);

for (int y = size - 1; y >= 0; y–) {
for (int x = 0; x < size; x++) {
System.out.print(board[y][x] + " ");
}
System.out.println();
}
}
}
Please enter size of board (need to be 2^n and 0 to quit): 2
Please enter coordinates of missing square (separated by a space): 0 0
T T
MS T

Please enter size of board (need to be 2^n and 0 to quit): 4
Please enter coordinates of missing square (separated by a space): 1 3
null MS null null
null T T null
T T T null
T T null null this is the output that i had got. I expect the output as Please enter size of board (need to be 2^n and 0 to quit): 2
Please enter coordinates of missing square (seperated by a space): 0 0
UR UR
MS UR
Please enter size of board (need to be 2^n and 0 to quit): 4
Please enter coordinates of missing square (seperated by a space): 1 3
LL MS UR UR
LL LL LR UR
LL LR LR LR
LL LL LR LR . Replace the T in the output that i had got with the suitable values as in the expected ouptut