[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?

An interesting mathematical problem, more or less equivalent to finding a
formula for the expected number of dart throws when there are N squares and i
darts, and a dart must be rethrown if it hits a square already occupied by
another dart. Any takers?

Art