How to find the smallest square of tetramino figures?

Question

Algorithms

Hello! I bring to your attention a question on which I have not been able to sleep normally for 3 days.
We have a certain finite set of tetramino pieces. In the process, we are forbidden to rotate them and only rearrange them. They are represented in the file by blocks of 4x4 elements where tetramino is # and empty cell is . (Point)
Since the block is 4×4 and each line has a line break, the entire block will be (4 × 4) + 4 (line break) + 1 (mandatory end/line break. For example:
If
n is a line break
# tetramino element
Empty element
o end of file
Then the source file of 2 blocks will look like this:
. . . . n
. . . # n
.### n
. . . . n
n
# . . . n
# . . . n
# . . . n
# . . . n
o (end of line (file))
Empty cells are allowed in the square. If at least one cell goes beyond the square, consider the minimum square the one that you place and the protruding part.
The task is to make the smallest possible square from the available Tetriminos.
I can check the validity of a file, a block without any problems. I also determined the size of each of the tetramino figures in order to allocate memory for them and store them in an array of pointers. But I don't know what to do with them! I would be very grateful for even a deaf thought. Thanks a lot!

Answer 1

Bust. We fix the size of the square k, then recursively enumerate: we take the uppermost-left unfilled cell. Either we mark it empty in the answer, or we put any of the unplaced tetraminos (4 shift options, since there are no turns). Naturally, the new teramino should only fit into unmarked cells. You need to insert all sorts of clippings - like there are enough unmarked cells to accommodate all the remaining tetraminos.