## 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

## Answers ( 1 )

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:

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

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.

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:

## 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`

:In main do:

In the function change

allplace where you want to assign the value - likeand

every timeyou call the function recursively, do an increment first - like: