Divide and conquer trominos algorithm in C

Question

This is the classic divide and conquer problem. We have a 2^n * 2^n board and we want to fill it with L shaped cubes. We know there is one block on the board that we can't assign a cube. This problem is also known as tromino problem (somewhat).

Problem

My solution works for n = 1 and n = 2. But when I wan to further generalize the solution (n > 2), I don't get all the blocks filled and some of them consist of false L shaped cube parts.

Program structure

Inputs

The user enters n and the position of the missing cube t on the board.

Output

We print the board filled with "trominos". We assign a value to each one of them. The missing cude always get zero value and each "tromino" contains a integer value (1, 2, 3, ....).

Solution

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

void recursiveSolve(int m, int A[m][m], int A_row, int A_col, int t_row, int t_y, int currBlockNum, int boardSize);

int main(void) {
    int n, m;

    do {
        printf("Give n > 0: ");
        scanf("%d", &n);
    } while (n <= 0);

    m = pow(2, n);

    int A[m][m];

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            A[i][j] = -1;
        }
    }

    int t_row, t_col;

    do {
        printf("Give missing square row coordinate: ");
        scanf("%d", &t_row);
        printf("Give missing square column coordinate: ");
        scanf("%d", &t_col);
    } while (t_row >= m || t_col >= m);

    A[t_row][t_col] = 0;

    recursiveSolve(m, A, 0, 0, t_row, t_col, 1, m);

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
                printf("%2d ", A[i][j]);
        }
        printf("\n");
    }

    return 0;
}

void recursiveSolve(int m, int A[m][m], int A_row, int A_col, int t_row, int t_col, int currBlockNum, int boardSize) {
    if (boardSize == 2) { // fill with L shaped block the area that is blank (no block exist).

        // check first which part of our board if filled up with  a block
        // and then paint the other.
        if (A[A_row][A_col] != -1) { // block exist at the top-left corner
            A[A_row+1][A_col]  = currBlockNum; // paint the bottom-left corner
            A[A_row+1][A_col+1] = currBlockNum; // paint the bottom-right corner
            A[A_row][A_col+1] = currBlockNum; // paint the top-right corner

        } else if (A[A_row][A_col+1] != -1) { // block exist at the top-right corner
            A[A_row][A_col] = currBlockNum; // paint the top-left corner
            A[A_row+1][A_col] = currBlockNum; // paint the bottom-left corner
            A[A_row+1][A_col+1] = currBlockNum; // paint the bottom-right corner

        } else if (A[A_row+1][A_col] != -1) { // block exist at the bottom-left corner
            A[A_row][A_col] = currBlockNum;
            A[A_row][A_col+1] = currBlockNum;
            A[A_row+1][A_col+1] = currBlockNum;

        } else { // block exist at the bottom-right corner
            A[A_row][A_col] = currBlockNum;
            A[A_row][A_col+1] = currBlockNum;
            A[A_row+1][A_col] = currBlockNum;
        }

    } else {
        int A_halfSize = boardSize / 2;

        // the bellow calculations allow us to check which
        // sub-partition of our board includes the missing block,
        // as well as how we should paint the center L shaped block.
        int A_rowCenter = A_row + A_halfSize;
        int A_colCenter = A_col + A_halfSize;


        if (t_row < A_rowCenter) { // missing block in top half
            if (t_col < A_colCenter ) { // missing block is in top left half
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;
            } else { // missing block is in top right half
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter] = currBlockNum;
            }

        } else { // missing block in bottom half
            if (t_col < A_colCenter ) { // missing block is in bottom left half
                A[A_rowCenter][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
            } else { // missing block is in bottom right half
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;
            }
        }

        // solve each sub-partion recursively

        // top-right sub-partion
        recursiveSolve(m, A, A_row, A_colCenter, t_row, t_col, ++currBlockNum, A_halfSize);

        // bottom-right sub-partion
        recursiveSolve(m, A, A_rowCenter, A_colCenter, t_row, t_col, ++currBlockNum, A_halfSize);

        // bottom left sub-partition
        recursiveSolve(m, A, A_rowCenter, A_col, t_row, t_col, ++currBlockNum, A_halfSize);

        // top-left sub-partition
        recursiveSolve(m, A, A_row, A_col, t_row, t_col, ++currBlockNum, A_halfSize);
    }
}

Show source
| C   | algorithm   2016-12-28 13:12 1 Answers

Answers to Divide and conquer trominos algorithm in C ( 1 )

  1. 2016-12-28 13:12

    As far as I can see, the strategy is to place the L in such a way that it occupies exactly one cube in the 3 squares that doesn't contain an already occupied cube.

    In other words:

    • you split the input square into 4 squares.
    • One of these already have an occupied cube.
    • You place the L so that the 3 other squares also ends up with exactly one occupied cube.

    Consequently you now have 4 squares - all with exactly one occupied cube. So now you can run the function on these four squares.

    enter image description here

    Now you can handle each of the 4 squares independently as each square has exactly one occupied cube.

    So what is the problem with your code?

    The problem is that you don't update the position of the occupied cube but simply keeps the original position.

        // top-right sub-partion
        recursiveSolve(m, A, A_row, A_colCenter, t_row, t_col, ++currBlockNum, A_halfSize);
                                                 ^^^^^^^^^^^^
                                                 May need update before calling
    
        // bottom-right sub-partion
        recursiveSolve(m, A, A_rowCenter, A_colCenter, t_row, t_col, ++currBlockNum, A_halfSize);
                                                        ^^^^^^^^^^^^
                                                        May need update before calling
    
        // bottom left sub-partition
        recursiveSolve(m, A, A_rowCenter, A_col, t_row, t_col, ++currBlockNum, A_halfSize);
                                                 ^^^^^^^^^^^^
                                                 May need update before calling
    
        // top-left sub-partition
        recursiveSolve(m, A, A_row, A_col, t_row, t_col, ++currBlockNum, A_halfSize);
                                            ^^^^^^^^^^^^
                                            May need update before calling
    

    For 3 of the 4 calls, you need to update the position of the occupied square.

    That can be achieved in many ways. Here is one approach:

    void recursiveSolve(int m, int A[m][m], int A_row, int A_col, int t_row, int t_col, int currBlockNum, int boardSize) {
        if (boardSize == 2) {
    
            // Keep your existing code unchanged here
    
        } else {
            int A_halfSize = boardSize / 2;
    
            // the bellow calculations allow us to check which
            // sub-partition of our board includes the missing block,
            // as well as how we should paint the center L shaped block.
            int A_rowCenter = A_row + A_halfSize;
            int A_colCenter = A_col + A_halfSize;
    
            // Calculate the position of the center cubes
            // as these will be the new occupied cub for
            // 3 of the 4 squares
            int TR_t_row = A_rowCenter - 1;
            int TR_t_col = A_colCenter;
    
            int BR_t_row = A_rowCenter;
            int BR_t_col = A_colCenter - 1;
    
            int BL_t_row = A_rowCenter - 1;
            int BL_t_col = A_colCenter;
    
            int TL_t_row = A_rowCenter - 1;
            int TL_t_col = A_colCenter - 1;
    
    
    
            if (t_row < A_rowCenter) { // missing block in top half
                if (t_col < A_colCenter ) { // missing block is in top left half
                    A[A_rowCenter][A_colCenter-1] = currBlockNum;
                    A[A_rowCenter][A_colCenter] = currBlockNum;
                    A[A_rowCenter-1][A_colCenter] = currBlockNum;
    
                    TL_t_row = t_row;  // Roll back to 
                    TL_t_col = t_col;  // original occupied cube
    
                } else { // missing block is in top right half
                    A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
                    A[A_rowCenter][A_colCenter-1] = currBlockNum;
                    A[A_rowCenter][A_colCenter] = currBlockNum;
    
                    TR_t_row = t_row;  // Roll back
                    TR_t_col = t_col;
    
                }
    
            } else { // missing block in bottom half
                if (t_col < A_colCenter ) { // missing block is in bottom left half
                    A[A_rowCenter][A_colCenter] = currBlockNum;
                    A[A_rowCenter-1][A_colCenter] = currBlockNum;
                    A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
    
                    BL_t_row = t_row;  // Roll back
                    BL_t_col = t_col;
    
                } else { // missing block is in bottom right half
                    A[A_rowCenter][A_colCenter-1] = currBlockNum;
                    A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
                    A[A_rowCenter-1][A_colCenter] = currBlockNum;
    
                    BR_t_row = t_row;  // Roll back
                    BR_t_col = t_col;
    
                }
            }
    
            // solve each sub-partion recursively
    
            // Use the 8 new variables for the recursive calls
    
            // top-right sub-partion
            recursiveSolve(m, A, A_row, A_colCenter, TR_t_row, TR_t_col, ++currBlockNum, A_halfSize);
                                                 //  ^^^^^^^^^^^^^^^^^^
    
            // bottom-right sub-partion
            recursiveSolve(m, A, A_rowCenter, A_colCenter, BR_t_row, BR_t_col, ++currBlockNum, A_halfSize);
                                                       //  ^^^^^^^^^^^^^^^^^^
    
            // bottom left sub-partition
            recursiveSolve(m, A, A_rowCenter, A_col, BL_t_row, BL_t_col, ++currBlockNum, A_halfSize);
                                                 //  ^^^^^^^^^^^^^^^^^^
    
            // top-left sub-partition
            recursiveSolve(m, A, A_row, A_col, TL_t_row, TL_t_col, ++currBlockNum, A_halfSize);
                                           //  ^^^^^^^^^^^^^^^^^^
        }
    }
    

    Update

    If you want to avoid using the same number for multiple L, you should pass a pointer to currBlockNum instead.

    Change the prototype - notice the int* currBlockNum:

    void recursiveSolve(int m, int A[m][m], int A_row, int A_col, int t_row, int t_y, int* currBlockNum, int boardSize);
    

    In main do:

    int currBlockNum = 1;
    recursiveSolve(m, A, 0, 0, t_row, t_col, &currBlockNum, m);
                                            ^^^
                                            Notice
    

    In the function change all place where you want to assign the value - like

    A[A_row+1][A_col]  = *currBlockNum;
                        ^^^
                        Notice
    

    and every time you call the function recursively, do an increment first - like:

        ++(*currBlockNum);
        recursiveSolve(m, A, A_row, A_colCenter, TR_t_row, TR_t_col, currBlockNum, A_halfSize);
    

Leave a reply to - Divide and conquer trominos algorithm in C

◀ Go back