[Coco] Minesweeper

[Mark McDougall]

Arthur Flexser wrote:

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

I can think of one approach. Place the numbers from 1 to 338 in an 
array. Choose a random number from 1-338 and that's your first number. 
Then remove that number from the array by shifting all the numbers above 
that down 1 space in the array. Then generate a random number from 
1-337. And so on...

Trouble is, shifting numbers takes time, although one can use mempcy for 
example. But at least it's deterministic and order N, unlike re-throwing 
'darts' as your remaining squares diminish.

The other problem is getting the random number in the correct range in 
the first place. One solution is to use the modulus of a very large 
random number. As long as the number is large enough (eg. 32 bits), it 
shouldn't affect the uniform distribution too much.

Regards,
Mark