7

The object of this puzzle is to construct a Minesweeper grid with a special property. The grid can be any shape, but it must have four labeled squares around the outer edge. Like this:

enter image description here

The four labeled squares must be labeled A, B, C, D, in that order going around the outer edge.

The objective is for a Minesweeper player to be able to conclude that A and C are the same, and B and D are the same, but not be able to conclude anything else. To be specific:

Place numbers in the grid to get a Minesweeper puzzle. This puzzle must have the following properties:

  1. There are no safe clicks. That is, for any unnumbered square, there is a solution in which that square is a mine.
  2. In any valid solution, A=C and B=D. (A=C means that A has a mine if and only if C does.)
  3. A valid solution must satisfy every combination of A=C and B=D simultaneously.

Again, the grid can be any shape. The grid can even have holes in it, but understand that "outer edge" does not include the edge neighboring a hole. A, B, C, D can be placed anywhere along the outer edge, but must be in that order. Aim for the smallest grid!

Ian MacDonald
  • 12,806
  • 1
  • 33
  • 63
Lopsy
  • 7,964
  • 30
  • 54
  • When you say A=C .. do they count each other for determing number of mines next to ? So if there are 2 mines next to A. and 1 next to C .. does A show 2, or 3 ? does C show 1 or 3 ? – Ditto Mar 24 '15 at 15:59
  • @Ditto What it means is that either A and C both have mines, or neither one does. What number they would show if they didn't have mines is not part of the puzzle. – KSmarts Mar 24 '15 at 16:01
  • Ok, so they are different squares .. they just share a mine/no mine property .. got it :) – Ditto Mar 24 '15 at 16:01
  • 1
    You're asking this to get some help completing your P=NP Minesweeper proof, aren't you? ;-) – Kevin Mar 24 '15 at 20:10
  • Does the definition of the puzzle grid include the number of mines to look for (as in the minesweeper game), or can different solutions use different numbers of mines? – Blckknght Mar 25 '15 at 01:45
  • Also, do the labeled squares need to have an unambiguous ordering? A 1x4 board, for instance, could be labeled many ways, since each square is on both edges. For a concrete example, could either B or D be put one square above C in your sample grid? – Blckknght Mar 25 '15 at 01:59
  • @Lopsy I take it you know the answer and are just posing this as a puzzle an optimization challenge? If not, you should track down the NP-completeness proof for minesweeper consistency, which includes a crossover gadget, or construct one from the planar logic gates. – xnor Mar 25 '15 at 05:17
  • @Blckknght The puzzle grid includes the numbers, yes. Of course, the different solutions with A=C and B=D will have different mine placements. &xnor: Yup, I just think it's a fun challenge. – Lopsy Mar 25 '15 at 08:54

3 Answers3

3

I think I got it now. Using a minesweeper developer program found on here, you can create, evaluate and try your own board. I have uploaded an image of my solution, or else this would've been a LOT of typing:

enter image description here

And an explanation about what you see in the image:

I've put the 4 labels (A, B, C and D) beside each questionmark where it should be. The red flags mark the spots of pre-discovered bombs.
Every pair (A-C and B-D) have their own 'wire' as it is called. Then an intersection to let these signals cross eachother, and arive at the other side.
For the first rule: there are no safe clicks, in all possible solutions this setup has got, any unnumbered square has been a mine at least once.
In èvery solution of this setup: it covers the A=C and B=D requirement. So both the second and third rule are covered too.

Discarded answers (Just for comment-reference)

1) .A   2)  A  3) AB
    1 .    D2B    DC
  D1.1B     C
  . 1
    C.
JBSregath
  • 581
  • 4
  • 8
  • 1
    Maybe I made the rules unclear. Rule 2 says "In any valid solution, A=C and B=D." Your first option breaks this because there is a solution where A and D have mines and B and C don't. Your second option breaks this because anything is a solution. Is it clear how Rule 2 works now? – Lopsy Mar 24 '15 at 15:04
  • @Lopsy Ok, I think it is clear now, let me (and others) work on a possible solution – JBSregath Mar 24 '15 at 15:10
  • I don't think your new answer implies that A=C and B=D. For example, you could have A with a mine and the bottom-right dot has a mine, but C does not. – KSmarts Mar 24 '15 at 15:58
  • If A is a mine, the dot next to it is not (because of the 1). And there is a solution in which C is a mine and the dot next to it is not. This is typically that moment of the 'last guess' (here) – JBSregath Mar 24 '15 at 16:04
  • No, @KSmarts is right. Rule #2's statement of "in any valid solution" does not say "there is a combination that satisfies A=C, B=D", it says "the only possible combinations satisfy A=C, B=D". – Ian MacDonald Mar 24 '15 at 16:08
  • 1
    What I'm saying is that there is a valid solution where A is a mine and the dot next to C is a mine, so C is not a mine. So A$\neq$C. – KSmarts Mar 24 '15 at 16:10
  • @Lopsy I hope you have the solution to this problem and not just wondering if there is one. Because I do not see one valid solution that satisfies every combination of A=C and B=D simultaneously. But if you look at your comment "...all 4 mine-settings of A, B, C, D satisfying A=C and B=D extend to a solution", my puzzle is a possible solution. Therefor my question: do you know the answer? – JBSregath Mar 25 '15 at 08:42
  • I know a solution. But it was pretty dang hard for me to find one! And the solution I have is nowhere near optimal. – Lopsy Mar 25 '15 at 08:56
  • I don't think this is a valid board. It can't have any solution at the four unknowns just four squares to the left of B. Also if D is mine, C will also need to be a mine following the diagonal from D to C. Then A will also be safe. – justhalf Mar 27 '15 at 14:59
  • @justhalf Ah, yes indeed, I see what you mean. I have to place the ? correctly and put the right numbers in the blocks. I've forgotten a few. Look at this pdf explaining logic ports in minesweeper. The 'signal' from left to right is v -> r but I had the D on the v' (which is the opposite of the signal v). – JBSregath Mar 30 '15 at 14:56
  • Now it looks correct. +1 – justhalf Mar 30 '15 at 21:23
  • 1
    Btw can we adapt this to make ABCD on the outer edge of the board to fulfill all the requirements? – justhalf Mar 30 '15 at 21:26
  • @justhalf I think ABCD are just about on the edge of the board. But be my guest if you can optimize it even further, no problem. – JBSregath Apr 01 '15 at 09:45
0

I'm probably twisting the rules a bit, but here goes. "The grid can be any shape". Well, my grid is a torus! (And it kinda looks like a swastika, but let's ignore that.)

C+A D
  1 +
D1+1B
+ 1
B C+A

The labels are shown twice to indicate where the grid "wraps around". The grid itself uses 11 squares.

I realize that this probably isn't what is intended, but I thought of this and decided to post it while working on a "real" answer.

Pre-edit answer:
How about this:

1A1
D B
1C1

The space in the middle is a "hole". If A has a mine, then B and D do not, which means that C does. Similarly, if A does not have a mine, then B and D do, so C does not. Thus, this satisfies all three conditions.

It uses a 3x3 grid, with a total of 8 squares.

KSmarts
  • 1,977
  • 12
  • 18
  • @Ian Macdonald and KSmarts: I think Lopsy means that for évery combination a solution has to exist. Both AC and BD have mines, AC have mines and BD are clear, AC are clear and BD have mines, both AC and BD are clear – JBSregath Mar 24 '15 at 15:23
  • @JBSregath: no, not quite. The reason why he claimed your answer did not follow rule 2 was that there existed a valid combination of ABCD that did not satisfy rule 2. No such rule-breaking combination exists in this answer (or mine). – Ian MacDonald Mar 24 '15 at 15:28
  • @Ian Macdonald: And rule #3: For any mine-setting of A, B, C, and D that satisfies A=C and B=D, this setting extends to a solution of the whole grid. This means a valid solution has to exist for each of these settings: both AC and BD mines, AC mines and BD clear, AC clear and BD mines, both AC and BD clear – JBSregath Mar 24 '15 at 15:32
  • @JBSregath I can see how it might mean that. I'll wait to hear from Lopsy, though, because that makes it a lot harder. – KSmarts Mar 24 '15 at 15:34
  • Yes, JBSregath is correct. Feel free to edit the puzzle (I am on a phone which makes editing very annoying.) – Lopsy Mar 24 '15 at 15:37
  • @Lopsy, so you're saying that a valid solution must exist simultaneously for all combinations of A=C, B=D? – Ian MacDonald Mar 24 '15 at 15:38
  • Yes Ian that's right. Of course the solutions will be different for each of the four combinations with A=C and B=D. – Lopsy Mar 24 '15 at 16:17
  • 3-dimensional minesweeper?! :O – Ian MacDonald Mar 24 '15 at 16:31
  • @IanMacDonald Nope. A torus, in the sense that I'm using it, is a 2-dimensional surface. It is often represented by an embedding in 3-space, the shape of which is also called a torus, and is probably what you are thinking of. – KSmarts Mar 24 '15 at 16:41
0

I think you might need to clarify what a "hole" is.

  A
D   B
  C

This satisfies the puzzle's requirements.

There are no safe spaces; all of the spaces are mines. Because none of the spaces are adjacent to each other, none of them can be a "numbered square"; the value of this number would be 0, making it an empty (or safe) space.

Ian MacDonald
  • 12,806
  • 1
  • 33
  • 63
  • This could be a solution indeed, but there might be a possibility this is not allowed because none of the sides are touching, thus not a minesweeper puzzle. I'll leave it up to Lopsy – JBSregath Mar 24 '15 at 15:27
  • It follows the rules laid out in the challenge and it follows the rules of Minesweeper as they are modified to include holes. It's really just a question of what makes a "smaller grid". 4 non-hole squares is smaller than 8 non-hole squares, but they take up more space if you include the holes in the calculation. – Ian MacDonald Mar 24 '15 at 15:31
  • How does this not have the "anything is a solution" problem that @JBSregath's second answer does? – KSmarts Mar 24 '15 at 15:33
  • @KSmarts: See the second spoiler block. – Ian MacDonald Mar 24 '15 at 15:34
  • The intention of rule 3 is that there should be a solution where (for example) A and C are both mines and B and D are both safe. That is, all 4 mine-settings of A, B, C, D satisfying A=C and B=D extend to a solution. I see now that I phrased this rule badly, sorry to the solvers so far. – Lopsy Mar 24 '15 at 15:42
  • The status of ABCD is unknown at the start of the game (by how minesweeper works). The possibility of the "all mines" solution means that none of the squares are "safe," regardless of whether they actually have mines or not. – KSmarts Mar 24 '15 at 15:49