[Coco] Minesweeper

[Arthur Flexser]

On Mon, 6 Feb 2006, Robert Gault wrote:
> 
> 4) In theory, the assignment of mines could be improved. The current 
> method is analogous to throwing darts at a map divided into 338 squares. 
> Darts are thrown until there are 45 darts on the map, each in a 
> different square. This could take a very long time if the darts keep 
> hitting the same squares, which is possible.
>   Another analogy is a bag of 338 marbles each labeled with a different 
> number. Pull out 45 marbles and the mines go on the squares 
> corresponding to the marbles. There can't be any multiple hits of the 
> same squares.
>   The question is can the second routine be programmed in as simple a 
> fashion as the first. I have not been able to write a Basic program 
> using method 2 that is even close to method 1 in speed, even though 
> method 2 is the better method. It is a good example of complexity 
> overwhelming speed.
>   Care to guess how the speed of method 1 will be affected by increasing 
> the percentage of the mined area?

I thought it would be an interesting mathematical problem to figure out just
exactly how the speed of method 1 is affected by the percentage of mined area.

Using Robert's dart analogy as a convenient explanatory framework, I took the
approach of figuring out how many dart throws, on average, it would take to land
a dart in an empty square, for a given degree of board occupancy.  For example,
suppose 1/4 of the squares are empty.  In this case, it will require an average
of 4 throws to get a dart onto an empty square.  (The reasoning for this depends
on the fact that if a dart hits a filled square, the situation is unchanged in
that 1/4 of the squares remain empty.)  In general, if a fraction F of the
squares are empty, it will take an average of 1/F attempts to land a dart in an
empty square.

Taking Diego's example of 45 darts and 338 squares:  To occupy the first empty
square will take one throw, since all squares are empty.  After that, 337/338 of
the squares are empty, so it will take an average of 338/337 additional throws
to acquire the second empty square.  Similarly, the third empty square will
require an additional 338/336 throws, etc, and we wind up with an additional
338/294 throws (294=338-45+1) being required, on average, to acquire the 45th
and last required empty square.  Summing up the expected numbers of throws to
acquire all 45 empty squares gives a result of 48.2 throws altogether--not too
much greater than the 45 attempts it would take if no dart ever hit an occupied
square.  That is, the method is highly efficient if the percentage of mined area
(ratio of darts to squares) is fairly small.

What happens as the percentage of mined area increases?  Here's some sample
numbers:

Darts    Squares      Expected number of throws
-----    -------      -------------------------

 45        338                  48.2

 45        100                  59.4

 45         60                  81.7

 45         50                 110.8

 45         45                 197.8

The last case, where the number of darts and squares are equal, corresponds to
using this method (which clearly becomes much less efficient as the two
quantities get closer together) to scramble a set of numbers.  To simulate a
shuffle of a deck of cards by this method, which is a poor one for this purpose,
requires an expected 236.0 throws (darts and squares both equal to 52).

Art