request for pointers: existence proof for minesweeper
in [Math]
|
Prev: The FASCINATING Secret Relationship Between PROFLIGATE WHITES and MISLEADER JEWS
Next: Absulote Logic Is Equator Of Self-contradiction
From: cellocgw on 22 Jun 2010 18:12 Hi, please let me know if there's a more appropriate ng to ask this problem. Thanks. As we all know, a typical Minesweeper game will require several "Guesses" during play. My question is: has anyone done some analysis to determine whether, for a given board size and/or mine density, there in fact exists a starting point such that an "intelligent player" (one who understands the logic of determining all miones/not mines from the current known field) can start at that designated square and complete the game without any further Guesses? I'm tempted to try an Entropy-based analysis (given that extremely low densities and extremely high densities of mines both are pretty much guaranteed to have such a starting point), viewing the board sort of like a collection of magnetic spin domains. anyway, thanks for any help Carl
From: Robert Israel on 22 Jun 2010 19:56 cellocgw <carl(a)witthoft.com> writes: > Hi, please let me know if there's a more appropriate ng to ask this > problem. Thanks. > As we all know, a typical Minesweeper game will require several > "Guesses" during play. > My question is: has anyone done some analysis to determine whether, > for a given board size and/or mine density, there in fact exists a > starting point such that an "intelligent player" (one who understands > the logic of determining all miones/not mines from the current known > field) can start at that designated square and complete the game > without any further Guesses? > I'm tempted to try an Entropy-based analysis (given that extremely low > densities and extremely high densities of mines both are pretty much > guaranteed to have such a starting point), viewing the board sort of > like a collection of magnetic spin domains. Suppose the board contains the following configuration (X = mine, ? = possible mine) X X X X X ? ? X X X X X where exactly one of the two ?'s has a mine. There is no way to distinguish between the two possibilities without a guess, clicking on one of the ?'s. On the other hand, starting by guessing one of the ?'s gives you not enough information to complete the rest of the board without further guesses. Situations similar to this do arise fairly often in real Minesweeper games. -- Robert Israel israel(a)math.MyUniversitysInitials.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada
From: Tim Little on 22 Jun 2010 21:02 On 2010-06-22, cellocgw <carl(a)witthoft.com> wrote: > My question is: has anyone done some analysis to determine whether, > for a given board size and/or mine density, there in fact exists a > starting point such that an "intelligent player" (one who > understands the logic of determining all miones/not mines from the > current known field) can start at that designated square and > complete the game without any further Guesses? There usually isn't. For example, the following common patterns cannot be resolved without guessing: ____ ______ |??1 1??1 |??1 or 1??1 |11@ @11@ | (Fixed-width font, where @ represents a bomb and | and _ represent edges of the board) If any of the unknown squares in these patterns are selected as a starting square, the result is either a bomb (instant loss) or a 2 or 3 (which requires further guessing). So the presence of either of these patterns anywhere around the edges of the board forces more than the initial guess. There are also numerous other patterns that force guessing. - Tim
From: Joshua Cranmer on 22 Jun 2010 22:20 On 06/22/2010 06:12 PM, cellocgw wrote: > My question is: has anyone done some analysis to determine whether, > for a given board size and/or mine density, there in fact exists a > starting point such that an "intelligent player" (one who understands > the logic of determining all miones/not mines from the current known > field) can start at that designated square and complete the game > without any further Guesses? I'm not quite sure how you intended your question to be interpreted. As long as a game of Minesweeper has at least 1 mine and at least 1 non-mine square, it is impossible to pick a square as definitively a mine or definitively not a mine. If I assume that you are shown a start square known to not be a mine, any grid with at least 3 mines in it has a possibility to force a guess: 0000| 0122| 01##| 013?| 001?| ----+ (# is a mine, the | and - walls, and ? an unknown square) If you assume that the shown start square is picked by an omniscient observer to guarantee the possibility of no guessing, then two of these structures and hence 6 mines is sufficient to create a grid where guessing is required no matter which square is revealed at first. In either case, the answer is that there does not exist such a starting point except in pathological cases. If you want to determine whether or not a given grid can be determined without guessing if a certain square is revealed... I know that determining whether or not a particular assignment of mines is consistent is NP-Complete, so determining guessability is probably at least as hard; it's striking me as EXPTIME right now. -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
From: cellocgw on 24 Jun 2010 18:10
On Jun 22, 10:20 pm, Joshua Cranmer <Pidgeo...(a)verizon.invalid> wrote: > On 06/22/2010 06:12 PM, cellocgw wrote: > > > My question is: has anyone done some analysis to determine whether, > > for a given board size and/or mine density, there in fact exists a > > starting point such that an "intelligent player" (one who understands > > the logic of determining all miones/not mines from the current known > > field) can start at that designated square and complete the game > > without any further Guesses? > > I'm not quite sure how you intended your question to be interpreted. > > As long as a game of Minesweeper has at least 1 mine and at least 1 > non-mine square, it is impossible to pick a square as definitively a > mine or definitively not a mine. That wasn't exactly it. I'm saying: Let the entire board be revealed before you start. Can you find a starting point (for now, assume an empty cell) such that from there onward, the board can be solved by the usual methods w/o any guessing. I just want to know under what conditions -- mine density -- it's guaranteed that such a starting point exists, or doesn't exist. Another poster submitted these sample configs: There usually isn't. For example, the following common patterns cannot be resolved without guessing: ____ ______ |??1 1??1 |??1 or 1??1 |11@ @11@ | (Fixed-width font, where @ represents a bomb and | and _ represent edges of the board) But my question is not "what happens if you select any of the ? cells" but rather "can you pick a starting point that will allow completion" . So in the left-hand example, If I choose to start somewhere else such that the bomb (@) is revealed, then I will "see" the two neighboring "1" cells, which will then reveal the numbers in all but the upper left ? cell, which would then be known. |