Divide and subdue the Tromin algorithm in C

Question

This is a classic problem to share and win . We have a 2 ^ n * 2 ^ n board, and we want to fill it with L-shaped cubes. We know that there is one block on the board that cannot be assigned to a cube. This issue is also known as the tromino (multiple) issue.

Problem

My solution works for n = 1 and n = 2. But when I want to generalize the solution even more (n> 2), I will not get all the filled blocks, and some of them consist of false parts of the L-shape cube.

Program structure

Inputs

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

Output

We print a board filled with throminos. We assign meaning to each of them. The missing cude always gets a null value, and each "tromino" contains an integer value (1, 2, 3, ....).

Decision

 #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); } } 

Answer 1

As far as I can see, the strategy is to place L so that it occupies exactly one cube in three squares, which does not contain an already occupied cube.

In other words:

• you split the input square into 4 squares.
• One of them already has a busy cube.
• You place L so that the 3 other squares end with exactly one occupied cube.

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

Now you can process each of the 4 squares independently, since each square has exactly one occupied cube.

What is the problem with your code?

The problem is that you are not updating the position of the occupied cube, but simply maintaining 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 out of 4 calls, you need to update the position of the occupied square.

This 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 currBlockNum , you should instead pass a pointer to currBlockNum .

Change the prototype - pay attention to 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); 

Basically do:

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

In the change all function, the place where you want to assign a value - for example

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

and each time you call the function recursively, first increment it - for example:

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