Question

Given a 2n × 2 n checkerboard with one square missing, construct a tiling of this checkerboard using right triominoes. Write a C or C++ program to solve this problem. The input is an integer n ≥ 3 and the position of the missing square. The output is a tiling of the 2n × 2 n checkerboard with one square missing (the position of the missing square is part of the input).

Answer 1

example
Input : size = 4 and mark coordinates = (0, 0)
Output :
-1      3       2       2
3       3       1       2
4       1       1       5
4       4       5       5

#include <bits/stdc++.h>

using namespace std;

int size_of_grid, b, a, cnt = 0;

int arr[128][128];

// Placing tile at the given coordinates

void place(int x1, int y1, int x2, int y2, int x3, int y3)

{

    cnt++;

    arr[x1][y1] = cnt;

    arr[x2][y2] = cnt;

    arr[x3][y3] = cnt;

}

// Function based on divide and conquer

int tile(int n, int x, int y)

{

    int r, c;

    if (n == 2) {

        cnt++;

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                if (arr[x + i][y + j] == 0) {

                    arr[x + i][y + j] = cnt;

                }

            }

        }

        return 0;

    }

    for (int i = x; i < n; i++) // finding hole location

    {

        for (int j = y; j < n; j++) {

            if (arr[i][j] != 0)

                r = i, c = j;

        }

    }

    // If missing tile is in first quadrant

    if (r < x + n / 2 && c < y + n / 2)

        place(x + n / 2, y + (n / 2) - 1, x + n / 2,

              y + n / 2, x + n / 2 - 1, y + n / 2);

    // If missing Tile is in 2st quadrant

    else if (r >= x + n / 2 && c < y + n / 2)

        place(x + n / 2, y + (n / 2) - 1, x + n / 2,

              y + n / 2, x + n / 2 - 1, y + n / 2 - 1);

    // If missing Tile is in 3st quadrant

    else if (r < x + n / 2 && c >= y + n / 2)

        place(x + (n / 2) - 1, y + (n / 2), x + (n / 2),

              y + n / 2, x + (n / 2) - 1, y + (n / 2) - 1);

    // If missing Tile is in 4st quadrant

    else if (r >= x + n / 2 && c >= y + n / 2)

        place(x + (n / 2) - 1, y + (n / 2), x + (n / 2),

              y + (n / 2) - 1, x + (n / 2) - 1, y + (n / 2) - 1);

    // diving it again in 4 quadrants

    tile(n / 2, x, y + n / 2);

    tile(n / 2, x, y);

    tile(n / 2, x + n / 2, y);

    tile(n / 2, x + n / 2, y + n / 2);

    return 0;

}

// Driver program to test above function

int main()

{

    // size of box

    size_of_grid = 4;

    memset(arr, 0, sizeof(arr));

    // Coordinates which will be marked

    a = 0, b = 0;

    // Here tile can not be placed

    arr[a][b] = -1;

    tile(size_of_grid, 0, 0);

    // The grid is

    for (int i = 0; i < size_of_grid; i++) {

        for (int j = 0; j < size_of_grid; j++)

            cout << arr[i][j] << " \t";

        cout << "\n";

    }

}