programming

Question

programming

Manu · Accepted Answer

Step 1: Code Implementation and Explanation

Here is the complete C++ program with explanations for each part:

#include 
#include 

// Define the triomino identifier globally
int triominoId = 1;

// Function to print the checkerboard
void printBoard(const std::vector>& board) {
    for (const auto& row : board) {
        for (const auto& cell : row) {
            std::cout << cell << "	";
        }
        std::cout << "
";
    }
}

// Function to tile the board
void tile(std::vector>& board, int n, int topRow, int topCol, int missingRow, int missingCol) {
    // Base case: if the board size is 2x2
    if (n == 1) {
        // Fill the 2x2 board with the triomino
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                if (!(topRow + i == missingRow && topCol + j == missingCol)) {
                    board[topRow + i][topCol + j] = triominoId;
                }
            }
        }
        triominoId++;
        return;
    }

    // Size of the sub-board
    int size = 1 << (n - 1); // 2^(n-1)

    // Determine the position of the missing square in the four quadrants
    int missingQuadrant;
    if (missingRow < topRow + size) {
        if (missingCol < topCol + size) {
            missingQuadrant = 0; // Top-left
        } else {
            missingQuadrant = 1; // Top-right
        }
    } else {
        if (missingCol < topCol + size) {
            missingQuadrant = 2; // Bottom-left
        } else {
            missingQuadrant = 3; // Bottom-right
        }
    }

    // Place a triomino at the center of the board to cover the central part
    int centerRow = topRow + size - 1;
    int centerCol = topCol + size - 1;
    if (missingQuadrant != 0) board[centerRow][centerCol] = triominoId;
    if (missingQuadrant != 1) board[centerRow][centerCol + 1] = triominoId;
    if (missingQuadrant != 2) board[centerRow + 1][centerCol] = triominoId;
    if (missingQuadrant != 3) board[centerRow + 1][centerCol + 1] = triominoId;
    triominoId++;

    // Recursively tile the four quadrants
    tile(board, n - 1, topRow, topCol, 
         missingQuadrant == 0 ? missingRow : centerRow, 
         missingQuadrant == 0 ? missingCol : centerCol);

    tile(board, n - 1, topRow, topCol + size, 
         missingQuadrant == 1 ? missingRow : centerRow, 
         missingQuadrant == 1 ? missingCol : centerCol + 1);

    tile(board, n - 1, topRow + size, topCol, 
         missingQuadrant == 2 ? missingRow : centerRow + 1, 
         missingQuadrant == 2 ? missingCol : centerCol);

    tile(board, n - 1, topRow + size, topCol + size, 
         missingQuadrant == 3 ? missingRow : centerRow + 1, 
         missingQuadrant == 3 ? missingCol : centerCol + 1);
}

int main() {
    int n, missingRow, missingCol;
    std::cout << "Enter the value of n (≥ 3): ";
    std::cin >> n;
    std::cout << "Enter the position of the missing square (row and column): ";
    std::cin >> missingRow >> missingCol;

    // Initialize the board
    int size = 1 << n; // 2^n
    std::vector> board(size, std::vector(size, 0));

    // Start the tiling process
    tile(board, n, 0, 0, missingRow, missingCol);

    // Print the result
    std::cout << "Tiled board:
";
    printBoard(board);

    return 0;
}

Explanation of Code

Struct Point: Represents a point on the board with x and y coordinates.
Class Tiling:
- Constructor: Initializes the board, marks the missing square, and calls the tile Board to start the tiling process.
- printBoard(): Prints the board with tile numbers and the missing square marked as 'X'.
- tileBoard(): Recursive function to tile the board. It subdivides the board into quadrants and recursively calls itself on each quadrant.
- fillBaseCase(): Handles the base case where the board size is 2x2.
- determineMissingQuadrants(): Determines which quadrant contains the missing square and adjusts the missing quadrants accordingly.
- fillLShape(): Places an L-shaped triomino in the center to ensure proper tiling

Step 2: Example Output and Explanation

Let's run the program with the following input:

Computer science

Computer science

Manu

Answer

Extracted Transcript from Images