Java Code

import java.util.*;

class Main {
  private static final String UPPER_LEFT = "UL";
  private static final String UPPER_RIGHT = "UR";
  private static final String LOWER_LEFT = "LL";
  private static final String LOWER_RIGHT = "LR";
  private static final String MISSING_SQUARE = "MS";

  private static void tromino(String[][] board, int x_board, int y_board, int x_missing, int y_missing, int board_size) {
      if (board_size == 1) {
          return;
      }

      int half_size = board_size / 2;
      int x_center = x_board + half_size;
      int y_center = y_board + half_size;

      // Upper left subboard
      if (x_missing < x_center && y_missing >= y_center) {
          board[x_center - 1][y_center] = LOWER_RIGHT;
          board[x_center][y_center] = UPPER_RIGHT;
          board[x_center][y_center - 1] = LOWER_LEFT;
          tromino(board, x_board, y_board + half_size, x_missing, y_missing, half_size);
          tromino(board, x_board, y_board, x_center - 1, y_center, half_size);
          tromino(board, x_board + half_size, y_board + half_size, x_center, y_center, half_size);
          tromino(board, x_board + half_size, y_board, x_center, y_center - 1, half_size);
      }
      // Upper right subboard
      else if (x_missing < x_center && y_missing < y_center) {
          board[x_center - 1][y_center - 1] = LOWER_LEFT;
          board[x_center][y_center] = UPPER_LEFT;
          board[x_center][y_center - 1] = LOWER_RIGHT;
          tromino(board, x_board, y_board + half_size, x_center - 1, y_center, half_size);
          tromino(board, x_board, y_board, x_missing, y_missing, half_size);
          tromino(board, x_board + half_size, y_board + half_size, x_center, y_center, half_size);
          tromino(board, x_board + half_size, y_board, x_center, y_center - 1, half_size);
      }
      // Lower left subboard
      else if (x_missing >= x_center && y_missing >= y_center) {
          board[x_center - 1][y_center - 1] = UPPER_RIGHT;
          board[x_center][y_center] = LOWER_LEFT;
          board[x_center - 1][y_center] = UPPER_LEFT;
          tromino(board, x_board, y_board + half_size, x_center - 1, y_center, half_size);
          tromino(board, x_board + half_size, y_board + half_size, x_missing, y_missing, half_size);
          tromino(board, x_board, y_board, x_center, y_center - 1, half_size);
          tromino(board, x_board + half_size, y_board, x_center, y_center, half_size);
      }
      // Lower right subboard
      else {
          board[x_center - 1][y_center - 1] = UPPER_LEFT;
          board[x_center][y_center - 1] = LOWER_RIGHT;
          board[x_center - 1][y_center] = LOWER_LEFT;
          tromino(board, x_board, y_board + half_size, x_center - 1, y_center, half_size);
          tromino(board, x_board, y_board, x_center, y_center - 1, half_size);
          tromino(board, x_board + half_size, y_board + half_size, x_missing, y_missing, half_size);
          tromino(board, x_board + half_size, y_board, x_center, y_center, half_size);
      }
  }
  public static void main(String[] args) {
      int board_size = 8;
      String[][] board = new String[board_size][board_size];
      int x_missing = 2;
      int y_missing = 2;
      for (int i = 0; i < board_size; i++) {
          for (int j = 0; j < board_size; j++) {
              if (i == x_missing && j == y_missing) {
                  board[i][j] = MISSING_SQUARE;
              } else {
                  board[i][j] = "";
              }
          }
      }
      tromino(board, 0, 0, x_missing, y_missing, board_size);
      for (int i = 0; i < board_size; i++) {
          System.out.println("\n");
          for (int j = 0; j < board_size; j++) {
              System.out.print(board[j][i] + "\t");
          }
      }
  }
}