3
$\begingroup$

In this game of minesweeper, what is the number of unclicked squares whose state you are guaranteed to be able to determine without losing?

A square can have one of two states: Mine or Not Mine

enter image description here

Edit: I stress that I am looking for a number, and hence your answer should be a single number, with explanation.

Edit: I am not interested in what the state of each square is, just if you will be able to determine it.

$\endgroup$
7
$\begingroup$

I can get this much:

enter image description here

which is to say,

25 cells.

Here's how it goes.

The green and red cells are, respectively, mine-free and mined. We begin by counting cells near the 3 in the 321 configuration to the northeast: exactly one to S+SW, at most one to W+N, hence one to NE (and exactly one to W+N, which gives us a bunch of mine-free cells around the 1). I think the inferences that give us the other red and green cells are straightforward.

Then

the purple cells are ones whose states we can definitely determine, though I can't tell you what the answer will be. For instance,look at the one "in the corner" at the top. We get that because the green cell to its southwest has only one neighbour; therefore, when we look at it (safe because it's green) we will discover that neighbour's state. Continuing with this sort of reasoning gives us the other purple cells at the top, and the upper of the two purples next to the 5 at the right. The other one next to the 5 is because we know how many mines are around the 5 and there's only one cell left.

After this

there will be some other cells we can expand -- e.g., one of those two next to the 5 must be un-mined -- but how many new cells this tells us the state of is not determinable so far as I can tell, and I think the number could be zero.

[EDITED to add:] Here's a sketch of how to prove that

after these we need not be able to determine any further cell-states.

Note that I am writing this after reading other people's solutions :-) but I haven't read them in much depth and am not deliberately copying anything.

So, first of all,

it's obvious that we can't, or at least mightn't be able to, do anything in the lower half. E.g., right at the bottom we need one mine but it could go in either of the two available cells; provided the two lower purple cells haven't given us anything extra (which clearly they needn't) the six cells above could be (top to bottom) any of X--X-X, -X--X-, or --X--X, which between them allow each of those cells to be in either state.

What about the top region? Well,

if all the upper purple cells turn out to contain mines (which they could) then we plainly learn nothing "beyond" them at the very top.

So the only question is

whether then the five known-clear cells next to the 1 near the top right have to tell us anything about the seven unknown-and-not-purple cells next to them. The answer is no. Let's suppose the upper of the two lower purple cells is mined and the lower unmined. Now, reading clockwise from the cell two above that 1, if we have X-X-X-- then those five cells say 3313; if we have -XXX--X then they say the same; and likewise if we have -X-X--X; and between them these possibilities put each of those cells into both possible states.

I conclude that

indeed it is possible that no other cell's state can be determined after finding those 25.

$\endgroup$
  • $\begingroup$ This is also what I could get. $\endgroup$ – Improve Apr 13 '17 at 21:48
  • $\begingroup$ Aha, clever. Putting this together with my answer (showing the unsolvability of the bottom half) shows that 25 is the most we can guarantee being able to determine (it could be more, depending on what happens in those purple cells). $\endgroup$ – Rand al'Thor Apr 13 '17 at 21:54
  • $\begingroup$ A complete answer would be to give enough example continuations such that each unclicked square take each form in at least one continuation. This is a bit tedious, but maybe made simpler by giving an example where each purple square is a mine, except for one adjacent to the 5. $\endgroup$ – Improve Apr 13 '17 at 21:57
  • $\begingroup$ I think it's tedious enough that I'm not going to do it just for the sake of a pretty green checkmark: it seems fairly obvious (unless I've missed something) that the rest of the cells are up for grabs. (What's not quite so clear is whether it turns out that every possible continuation determines at least one other cell's state, even if we can't tell which cells. If not, the least painful proof probably does go via a configuration in which almost every unknown cell is mined, but it's still going to be pretty painful.) $\endgroup$ – Gareth McCaughan Apr 13 '17 at 22:37
  • $\begingroup$ For the avoidance of doubt, if someone else is interested enough in the details to do all the work, I have no objection at all to their (1) doing it and (2) having their answer accepted :-). $\endgroup$ – Gareth McCaughan Apr 13 '17 at 22:38
3
$\begingroup$

Note: I'm using the notation mine for a square that contains a mine and yours for a square that doesn't.

I've found a bunch of squares which CAN'T be determined using the given information:

Board with some lines

The cells in the bottom two rows, linked by a blue line, must be one mine and one yours, from both the 1 and the 3. We can't say any more than that.

Now hop up a bit. The three cells linked by a red line (3rd, 4th, and 5th from the bottom) must be one mine and two yours; so must the three linked by a green line (4th, 5th, and 6th from the bottom); and so must the three linked by a purple line (6th, 7th, and 8th from the bottom). Again, we can't say any more than that.

Now each of Hellion's and Laurel's answers determines the state of the same 17 cells, and Gareth's shows that we can determine the state of a full 25 cells. Those 25 cover pretty much all but the ones I've marked here, which I've shown to be indeterminate. So the optimal answer should be 25.

$\endgroup$
  • $\begingroup$ What about the green and dark blue line at the top? Are they relevant? $\endgroup$ – boboquack Apr 13 '17 at 22:33
  • $\begingroup$ @boboquack You want to know why they're relevant? Think of it as a puzzle ;-) (No, seriously: I drew them because I was going to try to make some deductions up there, but then saw the other answers already had it covered.) $\endgroup$ – Rand al'Thor Apr 14 '17 at 0:24
2
$\begingroup$

I know what 17 of the unmarked squares are.

Red squares are mines and blacks aren't in this picture:

Explanation:

The blue arrow points to two squares, the two on the left below:

1 ? ? ?
? 3 2 1
? ? 2 ? 
3 3 3 ?

The three and the two to its right share 3 ?s, which must contain 2 mines. The rest of the mines near the two, but not the three must not be mines. The two below this first two is only adjacent to two unmarked squares, which must be mines.

At this point it's just basic minesweeper.

$\endgroup$
1
$\begingroup$

I can get 17 squares:enter image description here

explanation:

! Starting with the 2 purple squares, those are one mine and one not-mine. Then the three other squares around the three must be 2-and-1; but two of those are part of the 1-and-4 around the one, so the two brown squares are 1-and-1, leaving the red square to be a mine.
Then the rest of the squares around the one to the lower right are definitely not-mines, which leaves two squares next to the two (the rightmost purple one and the bottommost marked red one) as mines; which means the other purple is a not-mine, so the lower brown one is a mine and the upper brown is a not-mine; the brown mine completes the column of three twos, so finally the three marked squares in the top three rows can be determined.

$\endgroup$
  • $\begingroup$ This is not optimal, and you have not really answered the question. $\endgroup$ – Improve Apr 13 '17 at 21:11
  • $\begingroup$ Dammit, I don't have the spoiler tag format correct either. feh. $\endgroup$ – Hellion Apr 13 '17 at 21:16
  • $\begingroup$ This is still not optimal. $\endgroup$ – Improve Apr 13 '17 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.