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 == 1) {
            return;
        }

        int halfSize = size / 2;
        int xCenter = x + halfSize;
        int yCenter = y + halfSize;

        // Identify the quadrant with the missing square
        int missingQuadrant = (xMissing < xCenter ? 0 : 1) + (yMissing < yCenter ? 0 : 2);

        // Based on the missing quadrant, decide the central tromino placement
        for (int quadrant = 0; quadrant < 4; quadrant++) {
            if (quadrant == missingQuadrant) {
                // Recursively fill the quadrant with the actual missing square
                fillBoard(
                        x + (quadrant % 2) * halfSize,
                        y + (quadrant / 2) * halfSize,
                        halfSize,
                        xMissing,
                        yMissing);
            } else {
                // Place a temporary missing square for tromino placement
                int tmpXMissing = x + (quadrant % 2) * (halfSize - 1);
                int tmpYMissing = y + (quadrant / 2) * (halfSize - 1);
                board[tmpYMissing][tmpXMissing] = "MS";
                fillBoard(x + (quadrant % 2) * halfSize,
                          y + (quadrant / 2) * halfSize,
                          halfSize,
                          tmpXMissing,
                          tmpYMissing);
            }
        }

        board[yCenter - 1][xCenter] = board[yCenter][xCenter - 1] = board[yCenter][xCenter] = "  ";

        if (missingQuadrant == 0) { // Lower left
            board[yCenter][xCenter - 1] = "UR";
            board[yCenter][xCenter] = "UL";
            board[yCenter - 1][xCenter] = "LL";
        } else if (missingQuadrant == 1) { // Lower right
            board[yCenter][xCenter - 1] = "UR";
            board[yCenter - 1][xCenter] = "LL";
            board[yCenter][xCenter] = "LR";
        } else if (missingQuadrant == 2) { // Upper left
            board[yCenter][xCenter - 1] = "UR";
            board[yCenter][xCenter] = "UL";
            board[yCenter - 1][xCenter] = "LL";
        } else if (missingQuadrant == 3) { // Upper right
            board[yCenter][xCenter - 1] = "UL";
            board[yCenter - 1][xCenter] = "LL";
            board[yCenter][xCenter] = "LR";
        }

        // Reset the temporary missing square marker (‘MS’) for necessary quadrant
        if (size == 2) { // Base case size, directly mark ‘MS’ location
            board[yMissing][xMissing] = "MS";
        }
    }
} The output that I got after running the code 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
UR      UL
MS      LL which is incorrect.  The missing square is placed at the correct location but the other notations are wrong. According to the L-shaped arrangement that I had explained the correct 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 where MS is the missing square and UR is the notation for the Upper right L-shaped arrangement as it has a corner in the upper right of board in the L-shaped arrangement. Similarly consider the expected output for 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 where MS is the missing square at the 1 3 position considering (0, 0) as the origin at the lower left corner. The LL notation stands for the Lower left L-shaped arrangement as it has corner at the lower left in the board, UR is the notation for the Upper right L-shaped arrangement as it has corner at the Upper right in the board and LR is the notation for the Lower right L-shaped arrangement as it has corner at the Lower right in the board. There should be only one missing square in the board at the position specified in the input coordinates and the other squares around the missing square MS should be filled with LL,LR,UL,UR according to the L-shaped arrangement. Take the reference for your better understanding. Consider 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. Your program should use x coordinate and y coordinate to record the location of the missing square. The origin (0, 0) as the lower left corner of the board. After recording the missing square (MS) the program should fill the remaining squares with Lower Left(LL), Lower right(LR), Upper left(UL) and Upper right(UR) considering the L-shaped arrangement as I had explained in the above expected output.