How to generate two random numbers, X and Y, and make sure they are never repeated?

Question

Ok, so I am writing a Minesweeper app in WinForms. This is my first C# app so it has been a huge learning process. I want to randomly generate two numbers to put into two separate arrays, mineX & mineY. These two arrays are the coordinates for where all the mines are going to be placed on the board.

Here is the issue, I want to make sure that when it randomly generates these numbers, that X,Y will never be the same. I've done the research and know how to generate a single number and make each one unique. My issue is I want the combination of two random numbers to be unique.

Here is my code for the placeMines method.

    private void placeMines()
    {
        Random rnd = new Random();

        for (int i = 0; i < MINE_COUNT; i++)
        {               
                bombX[i] = rnd.Next(0, BOARD_X);
                bombY[i] = rnd.Next(0, BOARD_Y)'
        }
    }

This seems to be a simple issue to resolve, but I can't figure it out for the life of me.

Answer 1

1. Create a list of possible mine positions.
2. Choose a random item from the list, remove the item.
3. Repeat 2 until there're enough mines.

Sample code:

const int BOARD_X = 10;
const int BOARD_Y = 6;
const int MINE_COUNT = 30;

List<int> positions = Enumerable.Range(0, BOARD_X * BOARD_Y).ToList();
var rnd = new Random();
for (int i = 0; i < MINE_COUNT; i++) {
    int index = rnd.Next(positions.Count);
    int pos = positions[index];
    positions.RemoveAt(index);
    int x = pos % BOARD_X, y = pos / BOARD_X;
    Console.WriteLine("({0}, {1})", x, y);
}

NOTE: If the number of positions is big, you can optimize algorithm for space by using bit vectors. I'll leave this as an exercise.

Answer 2

Generate all positions (let it be struct with two int fields x, y) in array and shuffle this array.

Random _rand = new Random();
Position[] allPositions = GenerateAllPositions();

for (int i=allPositions.Length-1; i>=1; i--)
{
     int j = _rand.Next(0, i+1);
     // now swap
     Position tempPosition = allPositions[i];
     allPositions[i] = allPositions[j];
     allPositions[j] = tempPosition;
}

Now you can have temp int variable lastQueriedPositionIndex = 0, increase it by one when you pick any position. If lastQueriedPositionIndex == allPositions.Length make lastQueriedPositionIndex=0 and invoke this "swap" routine again. This is O(n) worst case solution instead of O(n^2) solution proposed by Athari - however in small board dimensions you won't see any diffrence.