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) {
            // Place the trominoes around the missing square.
            String trominoMarker = "UR"; // Default placement, adjust based on actual position of the missing tile.
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (x + i != xMissing || y + j != yMissing) {
                        if (xMissing == x && yMissing == y) trominoMarker = "LR"; // Lower Left
                        else if (xMissing == x + 1 && yMissing == y) trominoMarker = "LL"; // Lower Right
                        else if (xMissing == x && yMissing == y + 1) trominoMarker = "UR"; // Upper Left
                        else if (xMissing == x + 1 && yMissing == y + 1) trominoMarker = "UL"; // Upper Right
    
                        board[y + j][x + i] = trominoMarker;
                    }
                }
            }
            return;
        }
    
        int halfSize = size / 2;
        // Identify center for placing the tromino if the missing square is not in this quadrant.
        int centerX = x + halfSize - 1;
        int centerY = y + halfSize - 1;
    
        // Determine in which quadrant the missing square resides.
        boolean missingInLowerLeft = xMissing < x + halfSize && yMissing < y + halfSize;
        boolean missingInLowerRight = xMissing >= x + halfSize && yMissing < y + halfSize;
        boolean missingInUpperLeft = xMissing < x + halfSize && yMissing >= y + halfSize;
        boolean missingInUpperRight = xMissing >= x + halfSize && yMissing >= y + halfSize;
    
        // Place the center tromino based on the quadrant of the missing square.
        if (!missingInLowerLeft) board[centerY][centerX] = "MS"; // Bottom-Left
        if (!missingInLowerRight) board[centerY][centerX + 1] = "MS"; // Bottom-Right
        if (!missingInUpperLeft) board[centerY + 1][centerX] = "MS"; // Top-Left
        if (!missingInUpperRight) board[centerY + 1][centerX + 1] = "MS"; // Top-Right
    
        // Recursively solve for each quadrant.
        fillBoard(x, y, halfSize, missingInLowerLeft ? xMissing : centerX, missingInLowerLeft ? yMissing : centerY);
        fillBoard(x + halfSize, y, halfSize, missingInLowerRight ? xMissing : centerX + 1, missingInLowerRight ? yMissing : centerY);
        fillBoard(x, y + halfSize, halfSize, missingInUpperLeft ? xMissing : centerX, missingInUpperLeft ? yMissing : centerY + 1);
        fillBoard(x + halfSize, y + halfSize, halfSize, missingInUpperRight ? xMissing : centerX + 1, missingInUpperRight ? yMissing : centerY + 1);
    
        // Replace the "MS" used for simulations with correct tromino markers.
        if (!missingInLowerLeft) board[centerY][centerX] = "LR"; // Center tromino facing Lower Right
        if (!missingInLowerRight) board[centerY][centerX + 1] = "LL"; // Center tromino facing Lower Left
        if (!missingInUpperLeft) board[centerY + 1][centerX] = "UR"; // Center tromino facing Upper Right
        if (!missingInUpperRight) board[centerY + 1][centerX + 1] = "UL"; // Center tromino facing Upper Left
    }
    
    
} the output of this program is 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
LR      LR
MS      LR which is incorrect. The expected output is 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 In the first case there is a board with dimensions 2*2 with 4 squares inside it of 1*1 dimension. The first square is empty i.e. it is a missing square in the upper left corner, so the L-shaped arrangement for this case will be LR and it will be filled at the remaining coordinates as it has the corner for the L-shaped arrangement at the lower right. Similarly, In the second case a missing square is there in the upper right corner so the L-shaped arrangement for this case will be LL and it will be filled at the remaining coordinates as it has the corner for the L-shaped arrangement at the lower left, in the third case a missing square is there in the lower right corner so the L-shaped arrangement for this case will be UL and it will be filled at the remaining coordinates as it has the corner for the L-shaped arrangement at the upper left and in the fourth case a missing square is there in the lower left corner so the L-shaped arrangement for this case will be UR and it will be filled at the remaining coordinates as it has the corner for the L-shaped arrangement at the upper right

We will use x coordinate and y coordinate to record the location of the missing square. It is convenient to treat the origin (0, 0) as the lower left corner of the board. Similarly the output 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      UL      LR
UL      LR      LL      UR
UL      UL      UR      UR is incorrect. The correct 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