Simple Program Taking Extremely Long Time To Finish

Question

i am trying to create minesweeper in c# to do this i create an multidimensional array and then randomly pick positions using

Random rand = new Random;

the problem comes when trying to run the code, when i run it it takes an extremely long time to finish, i suspect it is because of the while loop and the if statements, if the rand.Next keeps getting the same values it could cause the loop to run for a long time. is there something im doing that is afftecting the pseudo randomness of my numbers. code below.

after returning to this questing a while later in an attempt to make it less horrendous it is clear that the reason for the program taking so long to run lies within the

while (counter < numberOfMines)
    {
        if (Minefield[randomNumber1, randomNumber2] == 9)
        {
            counter--;
        }
        else
        {
            Minefield[randomNumber1, randomNumber2] = 9;
            counter++;
        }
        randomNumber1 = (rand.Next(4)) + 1;
        randomNumber2 = (rand.Next(4)) + 1;
    }

section of the code. The reason that it was taking so long is that i was treating the while loop like a for loop and taking away from the counter when it was failing to place a mine. this is incorrect and i should have just not added to it.

using System;

class MainClass
{
    static void Main(string[] args)
    {
        int boardSize = 5;
        int numberOfMines = 25;
        GenerateMinefield(boardSize,numberOfMines);
        Console.ReadKey();
    }

    static int[,] GenerateMinefield(int boardSize, int numberOfMines)
    {
        int[,] Minefield = new int[boardSize + 2, boardSize + 2];
        for (int i = 0; i <= boardSize; i++)
        {
            for (int j = 0; j <= boardSize; j++)
            {
                Minefield[j, i] = 0;
            }
        }

        Random rand = new Random();
        int randomNumber1 = (rand.Next(4)) + 1;
        int randomNumber2 = (rand.Next(4)) + 1;
        int counter = 0;
        while (counter < numberOfMines)
        {
            if (Minefield[randomNumber1, randomNumber2] == 9)
            {
                counter--;
            }
            else
            {
                Minefield[randomNumber1, randomNumber2] = 9;
                counter++;
            }
            randomNumber1 = (rand.Next(4)) + 1;
            randomNumber2 = (rand.Next(4)) + 1;
        }

        for (int i = 0; i <= boardSize; i++)
        {
            for (int j = 0; j <= boardSize; j++)
            {
                Console.Write(Minefield[j, i]);
            }
            Console.WriteLine(Minefield[boardSize, i]);
        }
        
        return Minefield;
    }
}

Answer 1

Looks like your problem is in the counter--. You're not removing a mine, you're simply failing to place a mine, so counter should be unchanged.

Answer 2

If I understand correctly the while loop should look something like this:

        while (counter < numberOfMines)
        {
            if (Minefield[randomNumber1, randomNumber2] != 9)
            {
                  Minefield[randomNumber1, randomNumber2] = 9;
                  counter++;
            }
            randomNumber1 = (rand.Next(4)) + 1;
            randomNumber2 = (rand.Next(4)) + 1;
        }

Answer 3

It looks like you're trying to do the following:

1. Create a minefield board of size (N+2, N+2)
2. Fill the interior of the board (excluding the cells on the border) randomly with a specified number of mines.

It's possible to do this in linear time (i.e. O(N)) as follows:

1. Create a 1D array of bools with the same number of elements as the interior of the minefield, excluding the border cells.
2. Fill the start of array with a number of true values equal to the number of mines that you want.
3. Shuffle the array - now the "mines" are in random locations.
4. Go through the array and for every true value set the corresponding value in the minefield to 9.

It's slightly inefficient to create a temporary array almost the same size as the minefield, but this has the advantage that it will always run in linear time.

Putting this together:

static int[,] GenerateMinefield(int boardSize, int numberOfMines, Random rng)
{
    if (numberOfMines > boardSize)
        throw new InvalidOperationException($"{nameof(numberOfMines)} exceeds {nameof(boardSize)}");

    int[,] minefield = new int[boardSize + 2, boardSize + 2]; // Already filled with zeros.
    bool[] mines     = new bool[(boardSize-2)*2];

    for (int i = 0; i < numberOfMines; ++i) // Set the first 'numberOfMines' to 9.
        mines[i] = true;

    Shuffle(mines, rng); // Now the mines are in random locations.

    for (int i = 1, n = 0; i < boardSize; i++)
    {
        for (int j = 1; j < boardSize; j++, n++)
        {
            if (mines[n])
                minefield[j, i] = 9;
        }
    }

    return minefield;
}

static void Shuffle<T>(IList<T> array, Random rng)
{
    for (int n = array.Count; n > 1;)
    {
        int k = rng.Next(n);
        --n;
        T temp = array[n];
        array[n] = array[k];
        array[k] = temp;
    }
}

(That's using a standard shuffle algorithm.)

There's a better but more subtle way of doing this that doesn't require a separate array of bools. You can use the following code:

static int[,] GenerateMinefield(int boardSize, int numberOfMines, Random rng)
{
    if (numberOfMines > boardSize)
        throw new InvalidOperationException($"{nameof(numberOfMines)} exceeds {nameof(boardSize)}");

    int[,] minefield = new int[boardSize + 2, boardSize + 2]; // Already filled with zeros.
    int available = boardSize*2;

    for (int i = 1, n = 0; i < boardSize; i++)
    {
        for (int j = 1; j < boardSize; j++, n++)
        {
            if (rng.NextDouble() < numberOfMines / (double)available)
            {
                minefield[j, i] = 9;
                --numberOfMines;
            }
        }
    }

    return minefield;
}

The drawback of this approach is that it is not obvious how it works! It's also not completely evenly distributed, but I suspect that wouldn't matter for this program. See here for further discussion.