Is there an algorithm for breaking symmetries in polycube puzzles?
$begingroup$
Does there exist a general algorithm for dividing a polyomino/polycube packing problem into a set of subproblems which if solved will produce in aggregate all solutions to the original problem, but without the production of symmetric solutions?
When writing software to solve polyomino/polycube packing problems, it is customary to use one of several techniques to force the set of solutions generated to be unique under rotation and/or mirroring. For puzzles that have at least one uniquely shaped piece, one (or both) of these two techniques can sometimes be employed:
1) Rotationally constraining a single uniquely shaped piece. For the Tetris Cube puzzle, you can constrain one piece to have a single orientation to find all 9839 unique solutions and preclude the production of all rotational copies.
2) Translationally constraining a single uniquely shaped piece. For the pentominoes 10x6 packing problem, you can constrain the X piece to appear in one of 8 possible positions in the lower-left quadrant.
But if you don't have a uniquely shaped piece, or if no uniquely shaped piece has sufficient asymmetry, or if the dimensions of the puzzle and/or the shape of a piece limits your ability to unambiguously constrain a piece to a puzzle quadrant (or octant), then the above techniques may be unavailable or inadequate.
For problems where all pieces have the same shape, other techniques can sometimes be used. See for example the problem of packing 25 Y pentominoes into a 5x5x5 cube. For that problem, you can enumerate the 3 possible rotationally unique ways to fill the center square, and thereby eliminate the production of rotationally symmetric solutions, but you are still left with the production of mirrored solutions.
These various tricks can be of tremendous benefit to solver programs. If the puzzle has 48 symmetries, then breaking those symmetries through piece placement constraints will reduce the time to find all unique solutions by about a factor of 48. But each trick discussed here has limits as to where it can be applied. I've been scratching my head trying to come up with a general algorithm that can systematically divide any packing problem into a list of subproblems that together break the symmetries of the original problem. It seems like this should be possible, but it's overloading my tiny and glitchy brain. Surely someone has thought about such things before. I should think such an algorithm would be useful in other fields (organic chemestry, etc).
algorithms symmetry packing-problem
asked Dec 13 '18 at 3:58
Matthew BuscheMatthew Busche
864
$endgroup$
add a comment |
$begingroup$
Does there exist a general algorithm for dividing a polyomino/polycube packing problem into a set of subproblems which if solved will produce in aggregate all solutions to the original problem, but without the production of symmetric solutions?
When writing software to solve polyomino/polycube packing problems, it is customary to use one of several techniques to force the set of solutions generated to be unique under rotation and/or mirroring. For puzzles that have at least one uniquely shaped piece, one (or both) of these two techniques can sometimes be employed:
1) Rotationally constraining a single uniquely shaped piece. For the Tetris Cube puzzle, you can constrain one piece to have a single orientation to find all 9839 unique solutions and preclude the production of all rotational copies.
2) Translationally constraining a single uniquely shaped piece. For the pentominoes 10x6 packing problem, you can constrain the X piece to appear in one of 8 possible positions in the lower-left quadrant.
But if you don't have a uniquely shaped piece, or if no uniquely shaped piece has sufficient asymmetry, or if the dimensions of the puzzle and/or the shape of a piece limits your ability to unambiguously constrain a piece to a puzzle quadrant (or octant), then the above techniques may be unavailable or inadequate.
For problems where all pieces have the same shape, other techniques can sometimes be used. See for example the problem of packing 25 Y pentominoes into a 5x5x5 cube. For that problem, you can enumerate the 3 possible rotationally unique ways to fill the center square, and thereby eliminate the production of rotationally symmetric solutions, but you are still left with the production of mirrored solutions.
These various tricks can be of tremendous benefit to solver programs. If the puzzle has 48 symmetries, then breaking those symmetries through piece placement constraints will reduce the time to find all unique solutions by about a factor of 48. But each trick discussed here has limits as to where it can be applied. I've been scratching my head trying to come up with a general algorithm that can systematically divide any packing problem into a list of subproblems that together break the symmetries of the original problem. It seems like this should be possible, but it's overloading my tiny and glitchy brain. Surely someone has thought about such things before. I should think such an algorithm would be useful in other fields (organic chemestry, etc).
algorithms symmetry packing-problem
asked Dec 13 '18 at 3:58
Matthew BuscheMatthew Busche
864
$endgroup$
add a comment |
$begingroup$
Does there exist a general algorithm for dividing a polyomino/polycube packing problem into a set of subproblems which if solved will produce in aggregate all solutions to the original problem, but without the production of symmetric solutions?
When writing software to solve polyomino/polycube packing problems, it is customary to use one of several techniques to force the set of solutions generated to be unique under rotation and/or mirroring. For puzzles that have at least one uniquely shaped piece, one (or both) of these two techniques can sometimes be employed:
1) Rotationally constraining a single uniquely shaped piece. For the Tetris Cube puzzle, you can constrain one piece to have a single orientation to find all 9839 unique solutions and preclude the production of all rotational copies.
2) Translationally constraining a single uniquely shaped piece. For the pentominoes 10x6 packing problem, you can constrain the X piece to appear in one of 8 possible positions in the lower-left quadrant.
But if you don't have a uniquely shaped piece, or if no uniquely shaped piece has sufficient asymmetry, or if the dimensions of the puzzle and/or the shape of a piece limits your ability to unambiguously constrain a piece to a puzzle quadrant (or octant), then the above techniques may be unavailable or inadequate.
For problems where all pieces have the same shape, other techniques can sometimes be used. See for example the problem of packing 25 Y pentominoes into a 5x5x5 cube. For that problem, you can enumerate the 3 possible rotationally unique ways to fill the center square, and thereby eliminate the production of rotationally symmetric solutions, but you are still left with the production of mirrored solutions.
These various tricks can be of tremendous benefit to solver programs. If the puzzle has 48 symmetries, then breaking those symmetries through piece placement constraints will reduce the time to find all unique solutions by about a factor of 48. But each trick discussed here has limits as to where it can be applied. I've been scratching my head trying to come up with a general algorithm that can systematically divide any packing problem into a list of subproblems that together break the symmetries of the original problem. It seems like this should be possible, but it's overloading my tiny and glitchy brain. Surely someone has thought about such things before. I should think such an algorithm would be useful in other fields (organic chemestry, etc).
algorithms symmetry packing-problem
asked Dec 13 '18 at 3:58
Matthew BuscheMatthew Busche
864
$endgroup$
Does there exist a general algorithm for dividing a polyomino/polycube packing problem into a set of subproblems which if solved will produce in aggregate all solutions to the original problem, but without the production of symmetric solutions?
When writing software to solve polyomino/polycube packing problems, it is customary to use one of several techniques to force the set of solutions generated to be unique under rotation and/or mirroring. For puzzles that have at least one uniquely shaped piece, one (or both) of these two techniques can sometimes be employed:
1) Rotationally constraining a single uniquely shaped piece. For the Tetris Cube puzzle, you can constrain one piece to have a single orientation to find all 9839 unique solutions and preclude the production of all rotational copies.
2) Translationally constraining a single uniquely shaped piece. For the pentominoes 10x6 packing problem, you can constrain the X piece to appear in one of 8 possible positions in the lower-left quadrant.
But if you don't have a uniquely shaped piece, or if no uniquely shaped piece has sufficient asymmetry, or if the dimensions of the puzzle and/or the shape of a piece limits your ability to unambiguously constrain a piece to a puzzle quadrant (or octant), then the above techniques may be unavailable or inadequate.
For problems where all pieces have the same shape, other techniques can sometimes be used. See for example the problem of packing 25 Y pentominoes into a 5x5x5 cube. For that problem, you can enumerate the 3 possible rotationally unique ways to fill the center square, and thereby eliminate the production of rotationally symmetric solutions, but you are still left with the production of mirrored solutions.
These various tricks can be of tremendous benefit to solver programs. If the puzzle has 48 symmetries, then breaking those symmetries through piece placement constraints will reduce the time to find all unique solutions by about a factor of 48. But each trick discussed here has limits as to where it can be applied. I've been scratching my head trying to come up with a general algorithm that can systematically divide any packing problem into a list of subproblems that together break the symmetries of the original problem. It seems like this should be possible, but it's overloading my tiny and glitchy brain. Surely someone has thought about such things before. I should think such an algorithm would be useful in other fields (organic chemestry, etc).
algorithms symmetry packing-problem
algorithms symmetry packing-problem
asked Dec 13 '18 at 3:58
Matthew BuscheMatthew Busche
864
asked Dec 13 '18 at 3:58
Matthew BuscheMatthew Busche
864
asked Dec 13 '18 at 3:58
Matthew BuscheMatthew Busche
864
asked Dec 13 '18 at 3:58
Matthew BuscheMatthew Busche
864
asked Dec 13 '18 at 3:58
Matthew BuscheMatthew Busche
864
864
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3037576%2fis-there-an-algorithm-for-breaking-symmetries-in-polycube-puzzles%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 Mathematics Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fmath.stackexchange.com%2fquestions%2f3037576%2fis-there-an-algorithm-for-breaking-symmetries-in-polycube-puzzles%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
