Search code examples
arraysalgorithmlanguage-agnostic

How do I generate a 2D Array with values, each with neighbours of different, non-repeating values?

I have a square 2D Array, which I wish to fill with values between 1 to 4. For this to be correct, the neighbours of any of the values inside the array would need to look like this, as an example:

x 2 x
3 1 1
x 4 x

The x values are irrelevant to the middle value 1. As we can see, the neighbours of middle value 1 do not appear more than once, aside from itself

An incorrect value's neighbours would look like this:

x 2 x
3 1 2
x 4 x

One of the neighbours of middle value 1 appear more than once (the value of 2 appears twice), and we don't want this.

I have made a LUA solution for this problem, but it is very slow, as all it does is add 2 rules to the generation and runs through all combinations until it finds a valid one.

The rules being:

  1. Corner neighbours (in our case the xs) cannot have the same value as the middle value
  2. The next value OVER the relevant neighbours cannot have the same value as the middle value. Explanation for rule 2:
y y y y
y 1 y x
y y y y

The x in this instance cannot have the value of 1, this applies for every vertical and horizontal direction (up-down-left-right)

EDIT: I now know I can just repeat a tileable pattern, but this is not what I wanted, as I do not want a clear repetition to be observable

Solution

  • You can simply repeat a pattern to get the desired array.

    1. Row 1: 1 2 3 4 1 2 3... repeated for the required number of columns
    2. Row 2: 3 4 1 2 3 4 1... repeated similarly
    3. Row 3: Same as row 2
    4. Row 4: Same as row 1
    5. Row 5: Start repeating pattern from row 1

    ...continued for the required number of rows.

    Here's an example for a 6x6 grid:

    1 2 3 4 1 2
3 4 1 2 3 4
3 4 1 2 3 4
1 2 3 4 1 2
1 2 3 4 1 2
3 4 1 2 3 4

    This is guaranteed to follow both rules, since:

    1. The diagonal for a value of x here will always be 5 - x, and x != (5 - x) for x in [1,2,3,4].
    2. The next over value for 1 will always be 3 and vice versa (in any direction), and same for 2 and 4.

    Edit: In your comment, you've mentioned that you needed the array to be more "varied". Any form of randomness would mean that we can't use any patterns. In that case, your current solution can not be improved, since you can't use any pattern for optimisation.