algorithm for tiling 2D array with polyminos
It is different from generating polyminos, but it is NP-hard problem too.
I'm given polyminos with size 4, 5, 6, as an array.
'F':{'num':0b011110010,'width':3} #will be mutated to polymino as
((0,1,1),(1,1,0),(0,1,0)) #as printed
(0,1,1)
(1,1,0)
(0,1,0)
And I have a 2D array which is known for having at least one way to tile it full with the given polymino set.
The problem is to find the ways of tiling the array.
To solve the problem I made algorithm as,
A1. reverse the binary of all the possible rotation of given chips and add to dictionary,
Solver.keyset[tupleall(reverse_binary(objs.rotate(rots).shape))] = [[objs.name, rots, (0,0)]]
A2. check if the given array is in the dictionary
A3a. divide the array to solve by x,y axis, and solve for the smaller ones
A3b. add arrays which has solution, from the dictionary and solve for it
It works very well for small arrays,
a = Solver(((0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0)))
a.chips(5,6) #chip sized for 5-6
a.solver()
a.info
[['6C', 3, (0, 0), '6D', 1, (0, 1)], ['6C', 1, (0, 1), '6D', 3, (0, 0)], ['6A', 2, (0, 0), '6A', 0, (1, 0)], ['6A', 3, (1, 0), '6A', 1, (0, 0)], ['6A', 0, (1, 0), '6A', 2, (0, 0)], ['6A', 1, (0, 0), '6A', 3, (1, 0)], ['6D', 3, (0, 0), '6C', 1, (0, 1)], ['6D', 1, (0, 1), '6C', 3, (0, 0)]]
(Well, I need to rip out some polyminos which has duplicated by rotation)
But for larger arrays, it costs excessive times.
1 - Does my algorithm worth to do it? - do I have alternative algorithms to solve it better? I tried for brute-force, adding all the possible ways, but it took too much time so that I still didn't get the answer for (8,6) array.
2 - Will allowing only one answers from each division would help? - It will numerously speed up to find few answers, but its diversity will lessens.
python algorithm tetris tiling
asked Nov 16 '18 at 2:40
ILoveG11ILoveG11
395
add a comment |
It is different from generating polyminos, but it is NP-hard problem too.
I'm given polyminos with size 4, 5, 6, as an array.
'F':{'num':0b011110010,'width':3} #will be mutated to polymino as
((0,1,1),(1,1,0),(0,1,0)) #as printed
(0,1,1)
(1,1,0)
(0,1,0)
And I have a 2D array which is known for having at least one way to tile it full with the given polymino set.
The problem is to find the ways of tiling the array.
To solve the problem I made algorithm as,
A1. reverse the binary of all the possible rotation of given chips and add to dictionary,
Solver.keyset[tupleall(reverse_binary(objs.rotate(rots).shape))] = [[objs.name, rots, (0,0)]]
A2. check if the given array is in the dictionary
A3a. divide the array to solve by x,y axis, and solve for the smaller ones
A3b. add arrays which has solution, from the dictionary and solve for it
It works very well for small arrays,
a = Solver(((0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0)))
a.chips(5,6) #chip sized for 5-6
a.solver()
a.info
[['6C', 3, (0, 0), '6D', 1, (0, 1)], ['6C', 1, (0, 1), '6D', 3, (0, 0)], ['6A', 2, (0, 0), '6A', 0, (1, 0)], ['6A', 3, (1, 0), '6A', 1, (0, 0)], ['6A', 0, (1, 0), '6A', 2, (0, 0)], ['6A', 1, (0, 0), '6A', 3, (1, 0)], ['6D', 3, (0, 0), '6C', 1, (0, 1)], ['6D', 1, (0, 1), '6C', 3, (0, 0)]]
(Well, I need to rip out some polyminos which has duplicated by rotation)
But for larger arrays, it costs excessive times.
1 - Does my algorithm worth to do it? - do I have alternative algorithms to solve it better? I tried for brute-force, adding all the possible ways, but it took too much time so that I still didn't get the answer for (8,6) array.
2 - Will allowing only one answers from each division would help? - It will numerously speed up to find few answers, but its diversity will lessens.
python algorithm tetris tiling
asked Nov 16 '18 at 2:40
ILoveG11ILoveG11
395
add a comment |
It is different from generating polyminos, but it is NP-hard problem too.
I'm given polyminos with size 4, 5, 6, as an array.
'F':{'num':0b011110010,'width':3} #will be mutated to polymino as
((0,1,1),(1,1,0),(0,1,0)) #as printed
(0,1,1)
(1,1,0)
(0,1,0)
And I have a 2D array which is known for having at least one way to tile it full with the given polymino set.
The problem is to find the ways of tiling the array.
To solve the problem I made algorithm as,
A1. reverse the binary of all the possible rotation of given chips and add to dictionary,
Solver.keyset[tupleall(reverse_binary(objs.rotate(rots).shape))] = [[objs.name, rots, (0,0)]]
A2. check if the given array is in the dictionary
A3a. divide the array to solve by x,y axis, and solve for the smaller ones
A3b. add arrays which has solution, from the dictionary and solve for it
It works very well for small arrays,
a = Solver(((0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0)))
a.chips(5,6) #chip sized for 5-6
a.solver()
a.info
[['6C', 3, (0, 0), '6D', 1, (0, 1)], ['6C', 1, (0, 1), '6D', 3, (0, 0)], ['6A', 2, (0, 0), '6A', 0, (1, 0)], ['6A', 3, (1, 0), '6A', 1, (0, 0)], ['6A', 0, (1, 0), '6A', 2, (0, 0)], ['6A', 1, (0, 0), '6A', 3, (1, 0)], ['6D', 3, (0, 0), '6C', 1, (0, 1)], ['6D', 1, (0, 1), '6C', 3, (0, 0)]]
(Well, I need to rip out some polyminos which has duplicated by rotation)
But for larger arrays, it costs excessive times.
1 - Does my algorithm worth to do it? - do I have alternative algorithms to solve it better? I tried for brute-force, adding all the possible ways, but it took too much time so that I still didn't get the answer for (8,6) array.
2 - Will allowing only one answers from each division would help? - It will numerously speed up to find few answers, but its diversity will lessens.
python algorithm tetris tiling
asked Nov 16 '18 at 2:40
ILoveG11ILoveG11
395
It is different from generating polyminos, but it is NP-hard problem too.
I'm given polyminos with size 4, 5, 6, as an array.
'F':{'num':0b011110010,'width':3} #will be mutated to polymino as
((0,1,1),(1,1,0),(0,1,0)) #as printed
(0,1,1)
(1,1,0)
(0,1,0)
And I have a 2D array which is known for having at least one way to tile it full with the given polymino set.
The problem is to find the ways of tiling the array.
To solve the problem I made algorithm as,
A1. reverse the binary of all the possible rotation of given chips and add to dictionary,
Solver.keyset[tupleall(reverse_binary(objs.rotate(rots).shape))] = [[objs.name, rots, (0,0)]]
A2. check if the given array is in the dictionary
A3a. divide the array to solve by x,y axis, and solve for the smaller ones
A3b. add arrays which has solution, from the dictionary and solve for it
It works very well for small arrays,
a = Solver(((0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0)))
a.chips(5,6) #chip sized for 5-6
a.solver()
a.info
[['6C', 3, (0, 0), '6D', 1, (0, 1)], ['6C', 1, (0, 1), '6D', 3, (0, 0)], ['6A', 2, (0, 0), '6A', 0, (1, 0)], ['6A', 3, (1, 0), '6A', 1, (0, 0)], ['6A', 0, (1, 0), '6A', 2, (0, 0)], ['6A', 1, (0, 0), '6A', 3, (1, 0)], ['6D', 3, (0, 0), '6C', 1, (0, 1)], ['6D', 1, (0, 1), '6C', 3, (0, 0)]]
(Well, I need to rip out some polyminos which has duplicated by rotation)
But for larger arrays, it costs excessive times.
1 - Does my algorithm worth to do it? - do I have alternative algorithms to solve it better? I tried for brute-force, adding all the possible ways, but it took too much time so that I still didn't get the answer for (8,6) array.
2 - Will allowing only one answers from each division would help? - It will numerously speed up to find few answers, but its diversity will lessens.
python algorithm tetris tiling
python algorithm tetris tiling
asked Nov 16 '18 at 2:40
ILoveG11ILoveG11
395
asked Nov 16 '18 at 2:40
ILoveG11ILoveG11
395
edited Nov 16 '18 at 4:10
ILoveG11
asked Nov 16 '18 at 2:40
ILoveG11ILoveG11
395
asked Nov 16 '18 at 2:40
ILoveG11ILoveG11
395
asked Nov 16 '18 at 2:40
ILoveG11ILoveG11
395
395
add a comment |
add a comment |
0
active
oldest
votes
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53330674%2falgorithm-for-tiling-2d-array-with-polyminos%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53330674%2falgorithm-for-tiling-2d-array-with-polyminos%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
