Randomly Generate a unique Number grid
I have a 2D integer array, 5x5, and I have made a solution that randomly generates the numbers 1 - 5 in each of the array cells:
public int[,] generateGrid()
{
int seed = DateTime.Now.Second; // generate seed
Random rand = new Random(seed); // initialise random number with seed
int[,] grid = new int[_gridSize, _gridSize]; // create 2D array for grid
for (int i = 0; i < _gridSize; i++) // loop through rows
{
for (int j = 0; j < _gridSize; j++) // loop throug columns
{
int value = 0; // initialise the value to be entered into cell
while (value == 0) // while value is invalid ( "0" ) keep generating new number
{
value = rand.Next() % _gridSize + 1; // generate value from 0 - gridsize
grid[i, j] = value; // input value. Note: if value = 0, the loop will regenerate a new value
}
}
}
return grid;
}
Now this code does it's job. (Not sure about efficiency -- any extra advice on efficiency would be helpful.)
But my problem is, each column and each row can only contain the number 1-5 once! (rather like Sudoku.) and I'm not sure about how to do this (or the best way to do it).
My first idea was to make a stack, and push all the values created per row in the stack, then check it to see if the row already contains that value. if it does, generate a new value, check again etc. But iterating the stack is a bad idea, also, that's good for checking开发者_Go百科 the rows, but when it comes to checking the columns for uniqueness, it gets a bit difficult!
So basically, how can I make all rows and columns unique, but still be able to generate randomly each time. And what would be the best way to do this?
I found a solution that I'm willing to post for any other people stumbling across this post looking for an answer. To generate a unique number grid N x N (Although I've only tested 5x5), The following code Should do the trick:
// What Follows Is In C#
public int[,] generateGrid() // POSSIBLE UPDATE:: WHEN RESETING GRID ROW, REMEMBER PREVIOUS ORDER TO AVOID SAME COMFLICTION TWICE
{
Random rand = new Random();
ArrayList availableColumnNumbers = new ArrayList();
ArrayList availableRowNumbers = new ArrayList();
ArrayList availableNumbers = new ArrayList();
int[,] grid = new int[_gridSize, _gridSize];
availableColumnNumbers = resetArrayList(); // create a list that holds the numbers 1 - Grid Size
availableRowNumbers = resetArrayList(); // create a list that holds the numbers 1 - Grid Size
for (int row = 0; row < _gridSize; row++) // loop through rows
{
for (int column = 0; column < _gridSize; column++) // loop through columns
{
if (row == 0) // if row to be filled if the first row
{
int position = rand.Next(availableRowNumbers.Count); // Generate a random position
grid[row, column] = (int)availableRowNumbers[position]; // place available row numbers
availableRowNumbers.RemoveAt(position); // update available row numbers
}
else // row to be filled has constraints. Fill in, taking constraints into consideration
{
// update available column number, finds out what values are already in the column, and generates the only available values
availableColumnNumbers = getAvailableColumnNumbers(grid, column);
// combine available Rows and Columns to get a list of available numbers for that cell
availableNumbers = getSimilarNumbers(availableRowNumbers, availableColumnNumbers);
if (availableNumbers.Count != 0) // if there are available numbers to place,
{
int position = rand.Next(availableNumbers.Count);
grid[row, column] = (int)availableNumbers[position]; // place available number
availableRowNumbers.Remove((int)availableNumbers[position]); // update available row numbers
}
else // Confliction: There are no available numbers (restart entire row)
{
grid = resetRow(grid, row); // reset the entire row where confliction occured
column = -1; // start again at begining of column
availableRowNumbers = resetArrayList(); // reset Array List
}
}
}
availableRowNumbers = resetArrayList();// reset available row array
}
return grid;
This solution poses some functions whereby the source is not posted... but they're pretty straight forward for any avid developer to figure out:)
Happy Coding!
Alex
I guess you may have to do this a bit like solving a Sudoku. In other words initially each cell can contain any of the 5 values: so you set the first cell randomly, with no restrictions. Then set the next cell: now there is a restriction, it cannot have the value for the first cell (it's in the same row), so you may need to take a few goes to get a valid number.
Just keep working along each row and column, always checking back to the left (lower column index) for the values already set on this row, and checking up (lower row index) for the values already set on this column. If you try to set a cell to a value already used on this row or column just try again.
This should be expandable if you need to use different-sized grids. I will leave it to you how to optimise it if necessary (hint: setting the last cell may end up taking a longer than any other cell, even though it is the one which has only one possible value).
I don't think you need to care about efficiency in such a small grid (not even in a bigger one).
Simplest solution would be to check the current row and column for the value you're about to write into that cell, by simply iterating over the grid.
精彩评论