随机生成一个唯一的数字网格
本文关键字:唯一 数字 数字网 网格 一个 随机 | 更新日期: 2023-09-27 17:56:35
我有一个 2D 整数数组 5x5,我做了一个解决方案,在每个数组单元格中随机生成数字 1 - 5:
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;
}
现在这段代码完成了它的工作。(不确定效率 - 任何关于效率的额外建议都会有所帮助。
但我的问题是,每列和每行只能包含一次数字 1-5!(更像数独。而且我不确定如何做到这一点(或最好的方法)。
我的第一个想法是创建一个堆栈,并将每行创建的所有值推送到堆栈中,然后检查它以查看该行是否已经包含该值。 如果是,则生成一个新值,再次检查等。但是迭代堆栈也是一个坏主意,这对于检查行也有好处,但是当涉及到检查列的唯一性时,它变得有点困难!
所以基本上,我怎样才能使所有行和列都唯一,但每次仍然能够随机生成。最好的方法是什么?
我找到了一个解决方案,我愿意为任何其他偶然发现这篇文章寻找答案的人发布。生成一个唯一的数字网格 N x N(虽然我只测试了 5x5),以下代码应该可以解决问题:
以下内容在 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;
此解决方案提出了一些功能,其中源不会发布...但是对于任何狂热的开发人员来说,它们都非常简单:)
祝您编码愉快!
亚历克斯
我想你可能不得不这样做,就像解决数独一样。换句话说,最初每个单元格可以包含 5 个值中的任何一个:因此您可以随机设置第一个单元格,没有任何限制。然后设置下一个单元格:现在有一个限制,它不能有第一个单元格的值(它在同一行中),所以你可能需要花几次时间才能得到一个有效的数字。
只需继续沿着每一行和每一列工作,始终检查左边(下列索引)是否已经设置在此行上的值,并检查(下行索引)已在此列上设置的值。如果您尝试将单元格设置为此行或列上已使用的值,请重试。
如果您需要使用不同大小的网格,这应该是可扩展的。如有必要,我将留给您如何优化它(提示:设置最后一个单元格最终可能会比任何其他单元格花费更长的时间,即使它是只有一个可能值的单元格)。
我认为你不需要关心这么小的电网(即使是在更大的电网中)的效率。
最简单的解决方案是通过简单地遍历网格来检查当前行和列中要写入该单元格的值。