[Coco] Minesweeper

[Neil Morrison]

This is the card dealing algorithm. It is well known. Set up an array of 
elements, one for each card. Randomly select one. If the value is <> 0, it 
is a valid deal. Mark the array value as zero and 'deal' that card.

If the value = 0 the card has been dealt. Select another.

This is MUCH quicker than shifting. In effect, you have 52 flags.

Neil

----- Original Message ----- 
From: "Mark McDougall" <msmcdoug at iinet.net.au>


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