Filling a grid with unknown shapes

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?

edited Nov 14 '18 at 16:57

Ali Kanat

8571617

asked Nov 14 '18 at 15:41

Michal Kopiar

There is no efficient solution for these problems with generic shapes. How big is the grid?

– juvian
Nov 14 '18 at 16:00

add a comment |

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

edited Nov 14 '18 at 16:57

Ali Kanat

8571617

asked Nov 14 '18 at 15:41

Michal Kopiar

There is no efficient solution for these problems with generic shapes. How big is the grid?

– juvian
Nov 14 '18 at 16:00

add a comment |

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

edited Nov 14 '18 at 16:57

Ali Kanat

8571617

asked Nov 14 '18 at 15:41

Michal Kopiar

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

arrays algorithm dictionary grid flood-fill

edited Nov 14 '18 at 16:57

Ali Kanat

8571617

asked Nov 14 '18 at 15:41

Michal Kopiar

edited Nov 14 '18 at 16:57

Ali Kanat

8571617

asked Nov 14 '18 at 15:41

Michal Kopiar

edited Nov 14 '18 at 16:57

Ali Kanat

8571617

edited Nov 14 '18 at 16:57

Ali Kanat

8571617

edited Nov 14 '18 at 16:57

Ali Kanat

8571617

asked Nov 14 '18 at 15:41

Michal Kopiar

asked Nov 14 '18 at 15:41

Michal Kopiar

asked Nov 14 '18 at 15:41

Michal Kopiar

There is no efficient solution for these problems with generic shapes. How big is the grid?

– juvian
Nov 14 '18 at 16:00

add a comment |

There is no efficient solution for these problems with generic shapes. How big is the grid?

– juvian
Nov 14 '18 at 16:00

There is no efficient solution for these problems with generic shapes. How big is the grid?

– juvian
Nov 14 '18 at 16:00

add a comment |

1 Answer
1

active

oldest

votes

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:

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

I would look for

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.

edited Nov 23 '18 at 16:40

answered Nov 14 '18 at 16:43

SomeDude

4,37531327

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53303844%2ffilling-a-grid-with-unknown-shapes%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

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:

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

I would look for

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.

edited Nov 23 '18 at 16:40

answered Nov 14 '18 at 16:43

SomeDude

4,37531327

add a comment |

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:

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

I would look for

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.

edited Nov 23 '18 at 16:40

answered Nov 14 '18 at 16:43

SomeDude

4,37531327

add a comment |

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:

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

I would look for

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.

edited Nov 23 '18 at 16:40

answered Nov 14 '18 at 16:43

SomeDude

4,37531327

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:

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

I would look for

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.

edited Nov 23 '18 at 16:40

answered Nov 14 '18 at 16:43

SomeDude

4,37531327

edited Nov 23 '18 at 16:40

answered Nov 14 '18 at 16:43

SomeDude

4,37531327

answered Nov 14 '18 at 16:43

SomeDude

4,37531327

answered Nov 14 '18 at 16:43

SomeDude

4,37531327

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Ndtyjky