# [Coco] Minesweeper

Arthur Flexser flexser at fiu.edu
Mon Feb 6 19:23:35 EST 2006

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