[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