假设我有一个网格 (10x10)，我想用数字序列 0 - 99 填充它。这里有一些条件：
我可以处理条件1和2没问题。条件 3 更难（对我来说）。我已经使用蛮力来填充网格，但这有几个问题。首先，当网格很大（100x100）时速度很慢。其次（也是最重要的），蛮力并不能保证有解决方案（例如，序列中的最后两个数字将彼此相邻，因此不允许 -> 没有解决方案）。
如果有人可以帮助我提供合适的算法（甚至是一些数学/逻辑资源），那将会很有帮助。如果您可以提供解决方案，理想情况下，条件 3 应该是可定义的（即用户/编码器确定相邻数字不能出现的半径）。最后，不存在回绕问题（即如果数字 5 在一行的最后一列中，则 6 可以出现在下一行的第一列中）。
很多话，但我认为这是一个非常酷的问题，符合现实世界的需求（神经元的“随机”光激发）。
在此先感谢您的帮助。
皮特
这是一个想法：
对于NxN网格，生成一个数字列表0..NxN-1，然后对其进行洗牌（Fisher-Yates 或其他）。
然后，填写网格：对于每个单元格，根据您的规则和网格的当前状态选择随机列表中适合的第一个元素。在移动到网格时从混洗列表中删除每个元素。
如果由于打乱列表中没有剩余有效数字而未能填充网格单元格，请搜索填充的网格单元格，直到找到此处数字有效的单元格，并且打乱列表中剩余的数字之一是那里也有效。然后将那里移到此处并将有效号码从列表中移到那里。
我不确定您是否有可能找不到这样的数字，除非您的半径设置得太高而无法存在任何解决方案。为读者练习；）
您可以使用递归回溯算法，该算法在每个单元格中放置一个随机有效数字。如果没有有效的单元格，它会回溯并为前一个单元格选择另一个数字。使用枚举器方法，您可以轻松构建回溯系统。
class Generator
{
public int Width { get; private set; }
public int Height { get; private set; }
public int Radius { get; private set; }
private List<int> _numbers;
private bool[] _picked;
private int[] _grid;
private Random _rnd;
public Generator(int width, int height, int radius)
{
Width = width;
Height = height;
Radius = radius;
_rnd = new Random();
_numbers = Enumerable.Range(0,Width*Height).OrderBy(_ => _rnd.Next()).ToList();
_picked = _numbers.Select(n => false).ToArray();
_grid = new int[width*height];
}
public int[] Generate()
{
return Generate(0)
.Select(a => a.ToArray()) // copy
.FirstOrDefault();
}
private IEnumerable<int[]> Generate(int index)
{
if (index >= Width * Height)
{
yield return _grid;
yield break;
}
int xmid = index%Width;
int xlow = Math.Max(0, xmid - Radius);
int xhigh = Math.Min(xmid + Radius, Width - 1);
int ymid = index/Width;
int ylow = Math.Max(0, ymid - Radius);
int yhigh = ymid;
var validNumbers = _numbers
.Where(n =>
!_picked[n] &&
Enumerable.Range(xlow, xhigh - xlow + 1).All(x =>
Enumerable.Range(ylow, yhigh-ylow+1).All(y =>
y*Width + x >= index // Not generated yet
|| Math.Abs(x - xmid) + Math.Abs(y - ymid) > Radius // Outside radius
|| Math.Abs(_grid[y*Width+x] - n) > 1 // Out of range
)
)
)
.ToList();
foreach (var n in validNumbers)
{
_grid[index] = n;
_picked[n] = true;
foreach (var sol in Generate(index + 1))
{
yield return sol;
}
_picked[n] = false;
}
}
}
10x10 网格，半径 4 在 50 毫秒内生成：
74 6 72 1 82 64 41 66 96 17
61 24 12 93 35 86 52 19 47 10
42 48 69 45 79 88 31 43 28 36
15 38 4 40 54 33 13 7 90 68
34 67 62 83 99 59 50 22 73 77
44 18 0 8 20 81 26 37 98 87
29 71 58 75 14 65 55 85 57 80
84 32 91 25 5 78 95 9 2 53
60 23 11 63 49 39 70 89 27 46
97 16 3 30 56 92 76 51 21 94
通常它很快，并且在一秒钟内完成。有时它在一开始就做出了错误的选择，并且不得不回溯很多。
这听起来像是我用来为游戏生成星域的算法。我在笛卡尔平面上布置了一个给定维度的星系和所需数量的恒星。星星不能占据同一个地方，也不能彼此相隔n个单位。我偷了一些东西，但这应该会有所帮助。
for (int i = 0; i < u.StarCount; i++)
{
bool badStar = true; //Assume failure
do
{
//Create a star, get a random location, and where the rarity of its spectral type
StellarBody sb = new StellarBody();
sb.PositionX = r.Next(0, u.width);
sb.PositionY = r.Next(0, u.height);
int randomAbundance = r.Next(maxAbundance);
//Test the location against previous stars added, disallow positions where the centers are within 8 units of one another
if (!u.StellarBodies.Any(p => Math.Abs(p.PositionX.Value - sb.PositionX.Value) < minGap && Math.Abs(p.PositionY.Value - sb.PositionY.Value) < minGap))
{
//Get the spectral types based on the abundance value of the spectral types compared to the random abundance number
List<Models.StellarClass> abundanceTypes = starTypes.FindAll(f => f.Abundance == starTypes.Where(p => p.Abundance > randomAbundance).Min(m => m.Abundance));
try
{
int index = r.Next(0, abundanceTypes.Count());
sb.StellarClassID = abundanceTypes[index].StellarClassID;
sb.CatalogDesignation = index.ToString() + u.StellarBodies.Count.ToString()
+ abundanceTypes[index].Code + "-" + CoordinateMath.GetMortonNumber((int)sb.PositionX, (int)sb.PositionY).ToString();
minOrbit = abundanceTypes[index].MinOrbitZone;
maxOrbit = abundanceTypes[index].MaxOrbitZone;
}
catch (Exception ex)
{
sb.StellarClassID = starTypes.First(p => p.Code.Equals("Dork", StringComparison.CurrentCultureIgnoreCase)).StellarClassID;
}
u.StellarBodies.Add(sb);
badStar = false;
}
} while (badStar);
}
我会快速填满网格（尽量避免结块，但不要太努力）。当网格被填满时，我会找到聚集的数字并将它们移动。不涉及回溯。这种方法对于非常大的网格应该非常有效。
第一阶段伪代码：
int N = 100;
int minDistance = 10;
int maxCollisionCount = 5;
int saturationThreshold = N * N * 0.85;
grid[0,0] = 1;
int oldX = 0, oldY = 0;
int newX, newY;
for (i = 2; i <= N * N; i++)
{
bool foundNewCell = false;
for (collisionCount = 0; collisionCount < maxCollisionCount; collisionCount++)
{
newX = rnd(0, N - minDistance);
if (newX >= oldX - minDistance / 2)
newX += minDistance;
newY = rnd(0, N - minDistance);
if (newY >= oldY - minDistance / 2)
newY += minDistance;
if (grid[newX, newY] == 0)
{
grid[oldX = newX, oldY = newY] = i;
foundNewCell = true;
break;
}
if (i > saturationThreshold)
break;
}
if (foundNewCell)
continue;
// Find newX and newY by some other way, even if there would be clumping.
// For instance use already randomed newX and newY and circle around until
// you find an empty cell
...
grid[oldX = newX, oldY = newY] = i;
}