Split the matrix 8-ways PUZZLE
$begingroup$
I have a problem that has been bugging me for the last month, there is a matrix with 8x8 squares, so 64 squares, and with 8 balls placed randomly each in a square. I need to find the solution of how the matrix should be split in 8 parts such that each ball is in a different part and each part has exactly 8 squares.By the way, each "puzzle" can have multiple,one or no solutions. Please, i'll appreciate very much any kind of help, i'm very desperate!
Before: https://ibb.co/dWmsfp0
After: https://ibb.co/DLLTmWg
puzzle computational-mathematics
asked Jan 14 at 0:56
Manolache Gabriel IonutManolache Gabriel Ionut
111
$endgroup$
|
show 2 more comments
$begingroup$
I have a problem that has been bugging me for the last month, there is a matrix with 8x8 squares, so 64 squares, and with 8 balls placed randomly each in a square. I need to find the solution of how the matrix should be split in 8 parts such that each ball is in a different part and each part has exactly 8 squares.By the way, each "puzzle" can have multiple,one or no solutions. Please, i'll appreciate very much any kind of help, i'm very desperate!
Before: https://ibb.co/dWmsfp0
After: https://ibb.co/DLLTmWg
puzzle computational-mathematics
asked Jan 14 at 0:56
Manolache Gabriel IonutManolache Gabriel Ionut
111
$endgroup$
$begingroup$
Do the parts have to be connected?
$endgroup$
– Robert Israel
Jan 14 at 1:07
$begingroup$
I don't quite get what you mean, if you want, you can look on the after link in which is a solved puzzle and you can see that every part is distinguished by a different color.
$endgroup$
– Manolache Gabriel Ionut
Jan 14 at 1:12
2
$begingroup$
For example, is this a valid solution? If not, why not?
$endgroup$
– Robert Israel
Jan 14 at 3:35
1
$begingroup$
Now i get what you've meant, no it's not a valid solution. The parts need to be connected, and a square can be connected only with other one only from up down left or right
$endgroup$
– Manolache Gabriel Ionut
Jan 14 at 7:16
1
$begingroup$
The puzzle "Galaxies" from Simon Tatham's Portable Puzzle Collection appears to be related and might interest you.
$endgroup$
– Peter Kagey
Jan 14 at 23:33
|
show 2 more comments
$begingroup$
I have a problem that has been bugging me for the last month, there is a matrix with 8x8 squares, so 64 squares, and with 8 balls placed randomly each in a square. I need to find the solution of how the matrix should be split in 8 parts such that each ball is in a different part and each part has exactly 8 squares.By the way, each "puzzle" can have multiple,one or no solutions. Please, i'll appreciate very much any kind of help, i'm very desperate!
Before: https://ibb.co/dWmsfp0
After: https://ibb.co/DLLTmWg
puzzle computational-mathematics
asked Jan 14 at 0:56
Manolache Gabriel IonutManolache Gabriel Ionut
111
$endgroup$
I have a problem that has been bugging me for the last month, there is a matrix with 8x8 squares, so 64 squares, and with 8 balls placed randomly each in a square. I need to find the solution of how the matrix should be split in 8 parts such that each ball is in a different part and each part has exactly 8 squares.By the way, each "puzzle" can have multiple,one or no solutions. Please, i'll appreciate very much any kind of help, i'm very desperate!
Before: https://ibb.co/dWmsfp0
After: https://ibb.co/DLLTmWg
puzzle computational-mathematics
puzzle computational-mathematics
asked Jan 14 at 0:56
Manolache Gabriel IonutManolache Gabriel Ionut
111
asked Jan 14 at 0:56
Manolache Gabriel IonutManolache Gabriel Ionut
111
asked Jan 14 at 0:56
Manolache Gabriel IonutManolache Gabriel Ionut
111
asked Jan 14 at 0:56
Manolache Gabriel IonutManolache Gabriel Ionut
111
asked Jan 14 at 0:56
Manolache Gabriel IonutManolache Gabriel Ionut
111
111
$begingroup$
Do the parts have to be connected?
$endgroup$
– Robert Israel
Jan 14 at 1:07
$begingroup$
I don't quite get what you mean, if you want, you can look on the after link in which is a solved puzzle and you can see that every part is distinguished by a different color.
$endgroup$
– Manolache Gabriel Ionut
Jan 14 at 1:12
2
$begingroup$
For example, is this a valid solution? If not, why not?
$endgroup$
– Robert Israel
Jan 14 at 3:35
1
$begingroup$
Now i get what you've meant, no it's not a valid solution. The parts need to be connected, and a square can be connected only with other one only from up down left or right
$endgroup$
– Manolache Gabriel Ionut
Jan 14 at 7:16
1
$begingroup$
The puzzle "Galaxies" from Simon Tatham's Portable Puzzle Collection appears to be related and might interest you.
$endgroup$
– Peter Kagey
Jan 14 at 23:33
|
show 2 more comments
$begingroup$
Do the parts have to be connected?
$endgroup$
– Robert Israel
Jan 14 at 1:07
$begingroup$
I don't quite get what you mean, if you want, you can look on the after link in which is a solved puzzle and you can see that every part is distinguished by a different color.
$endgroup$
– Manolache Gabriel Ionut
Jan 14 at 1:12
2
$begingroup$
For example, is this a valid solution? If not, why not?
$endgroup$
– Robert Israel
Jan 14 at 3:35
1
$begingroup$
Now i get what you've meant, no it's not a valid solution. The parts need to be connected, and a square can be connected only with other one only from up down left or right
$endgroup$
– Manolache Gabriel Ionut
Jan 14 at 7:16
1
$begingroup$
The puzzle "Galaxies" from Simon Tatham's Portable Puzzle Collection appears to be related and might interest you.
$endgroup$
– Peter Kagey
Jan 14 at 23:33
$begingroup$
Do the parts have to be connected?
$endgroup$
– Robert Israel
Jan 14 at 1:07
$begingroup$
Do the parts have to be connected?
$endgroup$
– Robert Israel
Jan 14 at 1:07
$begingroup$
I don't quite get what you mean, if you want, you can look on the after link in which is a solved puzzle and you can see that every part is distinguished by a different color.
$endgroup$
– Manolache Gabriel Ionut
Jan 14 at 1:12
$begingroup$
I don't quite get what you mean, if you want, you can look on the after link in which is a solved puzzle and you can see that every part is distinguished by a different color.
$endgroup$
– Manolache Gabriel Ionut
Jan 14 at 1:12
2
2
$begingroup$
For example, is this a valid solution? If not, why not?
$endgroup$
– Robert Israel
Jan 14 at 3:35
$begingroup$
For example, is this a valid solution? If not, why not?
$endgroup$
– Robert Israel
Jan 14 at 3:35
1
1
$begingroup$
Now i get what you've meant, no it's not a valid solution. The parts need to be connected, and a square can be connected only with other one only from up down left or right
$endgroup$
– Manolache Gabriel Ionut
Jan 14 at 7:16
$begingroup$
Now i get what you've meant, no it's not a valid solution. The parts need to be connected, and a square can be connected only with other one only from up down left or right
$endgroup$
– Manolache Gabriel Ionut
Jan 14 at 7:16
1
1
$begingroup$
The puzzle "Galaxies" from Simon Tatham's Portable Puzzle Collection appears to be related and might interest you.
$endgroup$
– Peter Kagey
Jan 14 at 23:33
$begingroup$
The puzzle "Galaxies" from Simon Tatham's Portable Puzzle Collection appears to be related and might interest you.
$endgroup$
– Peter Kagey
Jan 14 at 23:33
|
show 2 more comments
1 Answer
1
active
oldest
votes
$begingroup$
I don't think there's an easy solution. In principle you could do this, but in practice I doubt that it is realistic: For each ball $b$, let $S_b$ be the set of all connected sets of cardinality $8$ containing $b$ and no other ball. Take binary variables $x_i$ for all members $i$ of all $S_b$. Then you want to satisfy the conditions
$$eqalign{sum_{i in S_b} x_i &= 1 text{for each $b$}cr
x_i + x_j &le 1 text{if $x_i in S_b$ and $x_j in S_{b'}$ with $b ne b'$ and $i cap j ne emptyset$}cr} $$
Use a SAT solver or integer linear programming.
In cases where a solution exists, you might find one using heuristic methods such as tabu search or simulated annealing.
answered Jan 14 at 17:11
Robert IsraelRobert Israel
328k23216469
$endgroup$
add a comment |
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%2f3072735%2fsplit-the-matrix-8-ways-puzzle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I don't think there's an easy solution. In principle you could do this, but in practice I doubt that it is realistic: For each ball $b$, let $S_b$ be the set of all connected sets of cardinality $8$ containing $b$ and no other ball. Take binary variables $x_i$ for all members $i$ of all $S_b$. Then you want to satisfy the conditions
$$eqalign{sum_{i in S_b} x_i &= 1 text{for each $b$}cr
x_i + x_j &le 1 text{if $x_i in S_b$ and $x_j in S_{b'}$ with $b ne b'$ and $i cap j ne emptyset$}cr} $$
Use a SAT solver or integer linear programming.
In cases where a solution exists, you might find one using heuristic methods such as tabu search or simulated annealing.
answered Jan 14 at 17:11
Robert IsraelRobert Israel
328k23216469
$endgroup$
add a comment |
$begingroup$
I don't think there's an easy solution. In principle you could do this, but in practice I doubt that it is realistic: For each ball $b$, let $S_b$ be the set of all connected sets of cardinality $8$ containing $b$ and no other ball. Take binary variables $x_i$ for all members $i$ of all $S_b$. Then you want to satisfy the conditions
$$eqalign{sum_{i in S_b} x_i &= 1 text{for each $b$}cr
x_i + x_j &le 1 text{if $x_i in S_b$ and $x_j in S_{b'}$ with $b ne b'$ and $i cap j ne emptyset$}cr} $$
Use a SAT solver or integer linear programming.
In cases where a solution exists, you might find one using heuristic methods such as tabu search or simulated annealing.
answered Jan 14 at 17:11
Robert IsraelRobert Israel
328k23216469
$endgroup$
add a comment |
$begingroup$
I don't think there's an easy solution. In principle you could do this, but in practice I doubt that it is realistic: For each ball $b$, let $S_b$ be the set of all connected sets of cardinality $8$ containing $b$ and no other ball. Take binary variables $x_i$ for all members $i$ of all $S_b$. Then you want to satisfy the conditions
$$eqalign{sum_{i in S_b} x_i &= 1 text{for each $b$}cr
x_i + x_j &le 1 text{if $x_i in S_b$ and $x_j in S_{b'}$ with $b ne b'$ and $i cap j ne emptyset$}cr} $$
Use a SAT solver or integer linear programming.
In cases where a solution exists, you might find one using heuristic methods such as tabu search or simulated annealing.
answered Jan 14 at 17:11
Robert IsraelRobert Israel
328k23216469
$endgroup$
I don't think there's an easy solution. In principle you could do this, but in practice I doubt that it is realistic: For each ball $b$, let $S_b$ be the set of all connected sets of cardinality $8$ containing $b$ and no other ball. Take binary variables $x_i$ for all members $i$ of all $S_b$. Then you want to satisfy the conditions
$$eqalign{sum_{i in S_b} x_i &= 1 text{for each $b$}cr
x_i + x_j &le 1 text{if $x_i in S_b$ and $x_j in S_{b'}$ with $b ne b'$ and $i cap j ne emptyset$}cr} $$
Use a SAT solver or integer linear programming.
In cases where a solution exists, you might find one using heuristic methods such as tabu search or simulated annealing.
answered Jan 14 at 17:11
Robert IsraelRobert Israel
328k23216469
answered Jan 14 at 17:11
Robert IsraelRobert Israel
328k23216469
answered Jan 14 at 17:11
Robert IsraelRobert Israel
328k23216469
answered Jan 14 at 17:11
Robert IsraelRobert Israel
328k23216469
328k23216469
add a comment |
add a comment |
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%2f3072735%2fsplit-the-matrix-8-ways-puzzle%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
$begingroup$
Do the parts have to be connected?
$endgroup$
– Robert Israel
Jan 14 at 1:07
$begingroup$
I don't quite get what you mean, if you want, you can look on the after link in which is a solved puzzle and you can see that every part is distinguished by a different color.
$endgroup$
– Manolache Gabriel Ionut
Jan 14 at 1:12
2
$begingroup$
For example, is this a valid solution? If not, why not?
$endgroup$
– Robert Israel
Jan 14 at 3:35
1
$begingroup$
Now i get what you've meant, no it's not a valid solution. The parts need to be connected, and a square can be connected only with other one only from up down left or right
$endgroup$
– Manolache Gabriel Ionut
Jan 14 at 7:16
1
$begingroup$
The puzzle "Galaxies" from Simon Tatham's Portable Puzzle Collection appears to be related and might interest you.
$endgroup$
– Peter Kagey
Jan 14 at 23:33