Prev: The FASCINATING Secret Relationship Between PROFLIGATE WHITES and MISLEADER JEWS
Next: Absulote Logic Is Equator Of Self-contradiction
From: Joshua Cranmer on 24 Jun 2010 18:28
On 06/24/2010 06:10 PM, cellocgw wrote:
> 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.

I covered that in the later part of my post:

> 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.

I can guarantee that there is a board which has only 6 mines which has
such an unguessable configuration. The upper limit strikes me as "all
but k of the squares are mines, where k is around 2."

Or, in short, such a starting point is not guaranteed to exist in all
but the most pathological cases.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
From: Tim Little on 25 Jun 2010 00:08
On 2010-06-24, cellocgw <cellocgw(a)gmail.com> wrote:
> 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.

Yes, that's the question that we were answering with "not always".

Though to be more precise, suppose a friend can see the board, and can
tell you where to start (but nothing else).


> I just want to know under what conditions -- mine density -- it's
> guaranteed that such a starting point exists, or doesn't exist.

If there are at most two mines, then it can always be solved without
guessing after the start point. If there are at least three mines,
then there are configurations that require guessing no matter where
you start.

> ____
> |??1
> |??1
> |11@
> |
>
> 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.

No, the displayed information is all you get. There are at least two
possible configurations of the displayed cells, both of which produce
exactly the information shown above:
___ ___
|@.. |.@.
|.@. or |@..
|..@ |..@

Some versions of minesweeper do not tell you how many bombs there are,
which would introduce a third possibility:
___
|...
|.@.
|..@

In the two (or three) possibilities, any of the hidden four cells may
contain a bomb and therefore a guess must be made.


- Tim
First  |  Prev  | 
Pages: 1 2
Prev: The FASCINATING Secret Relationship Between PROFLIGATE WHITES and MISLEADER JEWS
Next: Absulote Logic Is Equator Of Self-contradiction