Mixing
Possible number of bombs in minesweeper game
$begingroup$
This question is about the minesweeper game, and I really don't know how to think about this.
Suppose that we are playing the game and we have already opened some number of cells. Then the closed cells which are adjacent to certain set of open cells form a group of cells, which I call clusters. Here are some examples of clusters (closed cells inside the black borders):
For each cluster $C$ we can consider the set $M(C)$ of possible number of mines it can contain. For example, on the image above, for the cluster adjacent to cells with numbers 2 and 3, this set is ${3, 4, 5}$.
Suppose that we have some cluster $C$ and $a,b$ are respectively the possible minimum and maximum number of mines it can contain, and moreover $bgeq a+2$. Is it true that for every integer $cin(a,b)$ it can contain exactly $c$ mines?
combinatorics
edited Jun 12 '17 at 9:03
N. F. Taussig
45.3k103358
asked Jun 12 '17 at 8:16
C_MC_M
41939
$endgroup$
add a comment |
$begingroup$
This question is about the minesweeper game, and I really don't know how to think about this.
Suppose that we are playing the game and we have already opened some number of cells. Then the closed cells which are adjacent to certain set of open cells form a group of cells, which I call clusters. Here are some examples of clusters (closed cells inside the black borders):
For each cluster $C$ we can consider the set $M(C)$ of possible number of mines it can contain. For example, on the image above, for the cluster adjacent to cells with numbers 2 and 3, this set is ${3, 4, 5}$.
Suppose that we have some cluster $C$ and $a,b$ are respectively the possible minimum and maximum number of mines it can contain, and moreover $bgeq a+2$. Is it true that for every integer $cin(a,b)$ it can contain exactly $c$ mines?
combinatorics
edited Jun 12 '17 at 9:03
N. F. Taussig
45.3k103358
asked Jun 12 '17 at 8:16
C_MC_M
41939
$endgroup$
2
$begingroup$
Do a search for "minesweeper is NP-complete"; that might give some ideas for how to construct a counterexample. (just guessing here)
$endgroup$
– Greg Martin
Jun 12 '17 at 8:41
add a comment |
$begingroup$
This question is about the minesweeper game, and I really don't know how to think about this.
Suppose that we are playing the game and we have already opened some number of cells. Then the closed cells which are adjacent to certain set of open cells form a group of cells, which I call clusters. Here are some examples of clusters (closed cells inside the black borders):
For each cluster $C$ we can consider the set $M(C)$ of possible number of mines it can contain. For example, on the image above, for the cluster adjacent to cells with numbers 2 and 3, this set is ${3, 4, 5}$.
Suppose that we have some cluster $C$ and $a,b$ are respectively the possible minimum and maximum number of mines it can contain, and moreover $bgeq a+2$. Is it true that for every integer $cin(a,b)$ it can contain exactly $c$ mines?
combinatorics
edited Jun 12 '17 at 9:03
N. F. Taussig
45.3k103358
asked Jun 12 '17 at 8:16
C_MC_M
41939
$endgroup$
This question is about the minesweeper game, and I really don't know how to think about this.
Suppose that we are playing the game and we have already opened some number of cells. Then the closed cells which are adjacent to certain set of open cells form a group of cells, which I call clusters. Here are some examples of clusters (closed cells inside the black borders):
For each cluster $C$ we can consider the set $M(C)$ of possible number of mines it can contain. For example, on the image above, for the cluster adjacent to cells with numbers 2 and 3, this set is ${3, 4, 5}$.
Suppose that we have some cluster $C$ and $a,b$ are respectively the possible minimum and maximum number of mines it can contain, and moreover $bgeq a+2$. Is it true that for every integer $cin(a,b)$ it can contain exactly $c$ mines?
combinatorics
combinatorics
edited Jun 12 '17 at 9:03
N. F. Taussig
45.3k103358
asked Jun 12 '17 at 8:16
C_MC_M
41939
edited Jun 12 '17 at 9:03
N. F. Taussig
45.3k103358
asked Jun 12 '17 at 8:16
C_MC_M
41939
edited Jun 12 '17 at 9:03
N. F. Taussig
45.3k103358
edited Jun 12 '17 at 9:03
N. F. Taussig
45.3k103358
edited Jun 12 '17 at 9:03
N. F. Taussig
45.3k103358
45.3k103358
asked Jun 12 '17 at 8:16
C_MC_M
41939
asked Jun 12 '17 at 8:16
C_MC_M
41939
asked Jun 12 '17 at 8:16
C_MC_M
41939
41939
2
$begingroup$
Do a search for "minesweeper is NP-complete"; that might give some ideas for how to construct a counterexample. (just guessing here)
$endgroup$
– Greg Martin
Jun 12 '17 at 8:41
add a comment |
2
$begingroup$
Do a search for "minesweeper is NP-complete"; that might give some ideas for how to construct a counterexample. (just guessing here)
$endgroup$
– Greg Martin
Jun 12 '17 at 8:41
2
2
$begingroup$
Do a search for "minesweeper is NP-complete"; that might give some ideas for how to construct a counterexample. (just guessing here)
$endgroup$
– Greg Martin
Jun 12 '17 at 8:41
$begingroup$
Do a search for "minesweeper is NP-complete"; that might give some ideas for how to construct a counterexample. (just guessing here)
$endgroup$
– Greg Martin
Jun 12 '17 at 8:41
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
By counterexample, consider the following cluster:
Since it is impossible for only two of the three lowest flags to share a common mine, either a mine is placed in between the three flags, or one mine is placed for every flag. As such, this cluster can hold either $a = 13$ mines, or $b = 15 geq a+2$ mines.
answered Jun 12 '17 at 9:30
jvdhooftjvdhooft
5,65961641
$endgroup$
$begingroup$
Beautiful example. Thank you!
$endgroup$
– C_M
Jun 12 '17 at 10:10
add a comment |
Your Answer
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%2f2319421%2fpossible-number-of-bombs-in-minesweeper-game%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$
By counterexample, consider the following cluster:
Since it is impossible for only two of the three lowest flags to share a common mine, either a mine is placed in between the three flags, or one mine is placed for every flag. As such, this cluster can hold either $a = 13$ mines, or $b = 15 geq a+2$ mines.
answered Jun 12 '17 at 9:30
jvdhooftjvdhooft
5,65961641
$endgroup$
$begingroup$
Beautiful example. Thank you!
$endgroup$
– C_M
Jun 12 '17 at 10:10
add a comment |
$begingroup$
By counterexample, consider the following cluster:
Since it is impossible for only two of the three lowest flags to share a common mine, either a mine is placed in between the three flags, or one mine is placed for every flag. As such, this cluster can hold either $a = 13$ mines, or $b = 15 geq a+2$ mines.
answered Jun 12 '17 at 9:30
jvdhooftjvdhooft
5,65961641
$endgroup$
$begingroup$
Beautiful example. Thank you!
$endgroup$
– C_M
Jun 12 '17 at 10:10
add a comment |
$begingroup$
By counterexample, consider the following cluster:
Since it is impossible for only two of the three lowest flags to share a common mine, either a mine is placed in between the three flags, or one mine is placed for every flag. As such, this cluster can hold either $a = 13$ mines, or $b = 15 geq a+2$ mines.
answered Jun 12 '17 at 9:30
jvdhooftjvdhooft
5,65961641
$endgroup$
By counterexample, consider the following cluster:
Since it is impossible for only two of the three lowest flags to share a common mine, either a mine is placed in between the three flags, or one mine is placed for every flag. As such, this cluster can hold either $a = 13$ mines, or $b = 15 geq a+2$ mines.
answered Jun 12 '17 at 9:30
jvdhooftjvdhooft
5,65961641
edited Feb 2 at 20:41
answered Jun 12 '17 at 9:30
jvdhooftjvdhooft
5,65961641
answered Jun 12 '17 at 9:30
jvdhooftjvdhooft
5,65961641
answered Jun 12 '17 at 9:30
jvdhooftjvdhooft
5,65961641
5,65961641
$begingroup$
Beautiful example. Thank you!
$endgroup$
– C_M
Jun 12 '17 at 10:10
add a comment |
$begingroup$
Beautiful example. Thank you!
$endgroup$
– C_M
Jun 12 '17 at 10:10
$begingroup$
Beautiful example. Thank you!
$endgroup$
– C_M
Jun 12 '17 at 10:10
$begingroup$
Beautiful example. Thank you!
$endgroup$
– C_M
Jun 12 '17 at 10:10
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%2f2319421%2fpossible-number-of-bombs-in-minesweeper-game%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
2
$begingroup$
Do a search for "minesweeper is NP-complete"; that might give some ideas for how to construct a counterexample. (just guessing here)
$endgroup$
– Greg Martin
Jun 12 '17 at 8:41