Algorithms. Block wall

Question:

There is an unbounded MxN field. It contains rectangular blocks 1х1 , 1х2 , 1х3 , 2х2 , etc. up to 8х8 . The quantity is limited. Blocks can be placed either side by side or with spaces.
An example of the permissible arrangement of blocks on the field.
An example of an invalid block layout.
The field is entered in the form of 0 and 1. An example of an input for a field with a valid location:

101101
111111
111111

The task is to determine whether it is possible to build a given wall based on these blocks.

Tell me in which direction to dig in general to solve the problem, or with the help of which algorithm it is possible to achieve it.
I decided for each cell of the field to set the probability that it belongs to one of the blocks. I calculated with what probability which block could be located where, I began to substitute the blocks in turn, but some kind of garbage turns out …

Answer:

Resembles a dynamic programming problem. Try to think like this:

  1. take the upper left corner of the wall and see which of the remaining blocks can be placed so that their edge is in this corner. If there are no such blocks, then the answer is "NO" (no solution).

  2. If such blocks are found, then for each of them we solve the same problem with a "trimmed wall" (the one that remains after removing this block from it, take into account the block rotations) and with a smaller number of remaining blocks. If the "cut wall" turned into a void (all zeros in the MxN field), then we managed to build a wall and the answer is "YES". Otherwise, recursion along the "cut wall" + "rest of blocks" (for each block from item 1).

Scroll to Top
AllEscort