How can I create a semi-random grid of numbers such that each number appears once, AND most importantly is not too close to its precedding number?

Question

Lets say I have a grid (10x10) and I want to fill it with the number sequence 0 - 99. Here are some conditions:

1. Each number in the sequence should appear only once in the grid.
2. The placement of each number (from the sequence) should be random (x,y co-ordinates).
3. Subsequent numbers from the sequence (e.g. 5 and 6) cannot appear in the grid adjacent (or within a radius) of each other.

I can handle conditions 1 and 2 no problem. Condition 3 is harder (for me). I have used brute-force to fill the grid, but this has a couple of problems. Firstly, it is slow when the grid is biggish (100x100). Secondly (and most importantly), brute-force does not guarantee a solution (i.g. the final two numbers in the sequence will be adjacent each other and therefore not allowed -> no solution).

If someone can help me with a suitable algorithm (or even some maths/logic resources) that will be helpful. If you can provide a solution, ideally condition 3 should be definable (i.e. the user/coder determines the radius for which adjacent numbers cannot appear). Finally, there is no issue of wrap-around (i.e. if the number 5 in the last column of a row, then 6 can appear in the first column of the next row).

Lots of words, but I think this is a pretty cool problem with a real-world need ('random' photo-excitation of neurons).

Thanks in advance for your help.

Pete

Answer 1

You could use a recursive back-tracking algorithm, which puts a random valid number in each cell. If there is no valid cell, it back-tracks and picks another number for a previous cell. Using enumerator-methods, you can easily build a back-tracking system.

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 grid, with radius 4 generated in 50 ms:

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 

Often it is quick, and completes in under a second. Sometimes it makes a bad choice at the beginning, and have to back-track a lot.

Answer 2

Here's an idea:

For an NxN grid, generate a list of numbers 0..NxN-1, then shuffle it (Fisher-Yates or whatever).

Then, fill out the grid: for each cell, pick the first element in the shuffled list that will fit according to your rules and the current state of the grid. Remove each element from the shuffled list as it is moved to the grid.

If you fail to fill a grid cell because there are no valid numbers left in the shuffled list, search through the filled grid cells until you find a cell where the number there is valid here, and one of the numbers left in the shuffled list is also valid there. Then move there to here and move the valid number from the list there.

I'm not sure whether it's possible that you would not find such a number unless your radius was set too high for any solution to exist. Exercise for the reader ;)