Filling a grid with unknown shapes

Question

As an input i am giving 2D grid of 0´s with few -1 positions indicating places that can not be filled and blueprint of some shapes (as in Tetris game)

 ex. of grid              ex. of shapes

 0  0  0  0  0  0  0        1 1 1     2 2 2     3 3
-1  0  0  0  0  0  0        1           2
-1  0  0  0  0  0  0        1
 0  0  0  0  0 -1  0
 0  0  0 -1  0  0  0

Algorithm should output the grid filled with given shapes always having to use all of them once I can rotate the shapes and i should always be given grid and shapes that is possible to fill. I looked into algorithms like flood fill algorithm but i do not really see a way of using it here. Is it possible to do it differently than brute forcing through?

Answer 1

This is my thought on how I go about solving this:

For each shape it seems there are 4 possible types ( including the original ) for example:

1 1 1          1    1 1 1    1
1       ->     1        1    1
1          1 1 1,       1,   1 1 1 

Now lets say there are s number of shapes, then there are 4s total shapes.

Take a combination out of 4s shapes and form a figure like:

  2
1 2 2
1 2 3 3
1 1 1 

or

1 1 1
1 2 3 3
1 2 2
  2 

or

1 1 1 3 3
1 2 2 2
1   2

or

any such figure out of (4s)^2 = 16s^2 possibilities.

Actually it is more than 16s^2, because it is not just concatenation of shapes, you need to greedily look for vacant spaces and try to fit in there. :(

Now you have a figure in your hand, look for the same shape in your grid.

So for example to look for

1 1 1
1 2 3 3
1 2 2
  2 

I would look for

0 0 0
0 0 0 0
0 0 0
  0 

in the original grid.

Then this seems to be a problem of finding that figure in the original matrix.

Also see this which is a similar question but not exactly the same, about finding shapes.