import java.util.Scanner;

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

    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): ");

        int boardSize = scanner.nextInt();
        if (boardSize == 0) {
            scanner.close();
            return;
        }

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

        // Initialize the board
        initializeBoard(boardSize);

        // Mark the initially missing square
        board[yMissing][xMissing] = "MS";

        // Fill the board with trominoes
        fillBoard(0, 0, boardSize, xMissing, yMissing);

        // Print the result
        for (int y = boardSize - 1; y >= 0; y--) { // Start from the top for display
            for (int x = 0; x < boardSize; x++) {
                System.out.print(board[y][x] + "\t");
            }
            System.out.println();
        }

        scanner.close();
    }

    private static void initializeBoard(int boardSize) {
        board = new String[boardSize][boardSize];
        for (int i = 0; i < boardSize; i++) {
            for (int j = 0; j < boardSize; j++) {
                board[i][j] = "  ";  // Initialize with spaces
            }
        }
    }

    private static void fillBoard(int x, int y, int size, int xMissing, int yMissing) {
        if (size == 2) {
            // Directly place the tromino markers, adjusting based on the position of the missing square.
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (x + i != xMissing || y + j != yMissing) {
                        // Determine direction based on the missing square to correctly place the "L" tromino.
                        if (xMissing == x && yMissing == y) board[y + j][x + i] = "LR"; // Lower Left
                        else if (xMissing == x + 1 && yMissing == y) board[y + j][x + i] = "LL"; // Lower Right
                        else if (xMissing == x && yMissing == y + 1) board[y + j][x + i] = "UR"; // Upper Left
                        else if (xMissing == x + 1 && yMissing == y + 1) board[y + j][x + i] = "UL"; // Upper Right
                    }
                }
            }
            return;
        }
    
        int halfSize = size / 2;
        int centerX = x + halfSize;
        int centerY = y + halfSize;
    
        // Determine center square filler based on where the missing square is
        if (xMissing < centerX && yMissing < centerY) { // Missing square in Lower Left quadrant
            fillBoard(x, y, halfSize, xMissing, yMissing);
            fillBoard(x, y + halfSize, halfSize, centerX - 1, centerY);
            fillBoard(x + halfSize, y, halfSize, centerX, centerY - 1);
            fillBoard(x + halfSize, y + halfSize, halfSize, centerX, centerY);
            board[centerY - 1][centerX] = "LL"; // marker for the top-right to bottom-left tromino
            board[centerY][centerX] = "LL";
            board[centerY][centerX - 1] = "LL";
        } else if (xMissing >= centerX && yMissing < centerY) { // Missing square in Lower Right quadrant
            fillBoard(x, y, halfSize, centerX - 1, centerY - 1);
            fillBoard(x, y + halfSize, halfSize, centerX - 1, centerY);
            fillBoard(x + halfSize, y, halfSize, xMissing, yMissing);
            fillBoard(x + halfSize, y + halfSize, halfSize, centerX, centerY);
            board[centerY - 1][centerX - 1] = "LR"; // marker for the top-left to bottom-right tromino
            board[centerY][centerX] = "LR";
            board[centerY][centerX - 1] = "LR";
        } else if (xMissing < centerX && yMissing >= centerY) { // Missing square in Upper Left quadrant
            fillBoard(x, y, halfSize, centerX - 1, centerY - 1);
            fillBoard(x, y + halfSize, halfSize, xMissing, yMissing);
            fillBoard(x + halfSize, y, halfSize, centerX, centerY - 1);
            fillBoard(x + halfSize, y + halfSize, halfSize, centerX, centerY);
            board[centerY - 1][centerX] = "UR"; // marker for the bottom-right to top-left tromino
            board[centerY - 1][centerX - 1] = "UR";
            board[centerY][centerX] = "UR";
        } else if (xMissing >= centerX && yMissing >= centerY) { // Missing square in Upper Right quadrant
            fillBoard(x, y, halfSize, centerX - 1, centerY - 1);
            fillBoard(x, y + halfSize, halfSize, centerX - 1, centerY);
            fillBoard(x + halfSize, y, halfSize, centerX, centerY - 1);
            fillBoard(x + halfSize, y + halfSize, halfSize, xMissing, yMissing);
            board[centerY - 1][centerX - 1] = "UL"; // marker for the bottom-left to top-right tromino
            board[centerY - 1][centerX] = "UL";
            board[centerY][centerX - 1] = "UL";
        }
    }
    
    
    
} the output that i got after running the program is 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
UL      MS      LR      LR
UL      UL      UR      LR
UL      UR      UR      UR
UL      UL      UR      UR but the expected output is 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