# [Coco] Minesweeper

Neil Morrison neilsmorr at hotpop.com
Tue Feb 7 01:11:09 EST 2006

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

```