GRiddles Series A: Puzzle 1

I thought it would be fun to solve a puzzle from G-Research.

Problem Statement

Chromatic Rotations

A 101 × 101 grid is divided into $101^2$ unit cells. Each cell is to be coloured in yellow, grey or green.

A colouring is called proper if: no two cells sharing an edge have the same colour and every 2 × 2 square composed of four cells contains all three colours.

Proper colourings are grouped as follows: two proper colourings belong to the same group if one can be obtained from the other by a rotation of the grid.

Determine the number of such groups of proper colourings.

Answer

The number of groups for a given grid size can be calculated with the following formula:

and the number of groups for a $101^2$ grid is $1.2052035331942 \times 10^{60}$. In the following sections we explain how we arrived at this solution.

Preamble

To tackle this problem, we will break it into two steps: building proper colourings and building rotation groups. Before we can investigate rotational groups of proper colourings, we need to understand how proper colourings are constructed and derive a formula for all possible combinations for a given grid size. With the formulation behind proper colourings, we can determine how they form rotational groups and again derive a formula for the number of groups.

To simplify the discussion, we will use integers in place of colours. We will also refer to the set of all proper colourings for a grid size NxN as $PC_N$. Proper colourings have two sets of rules, which we will refer to as the edge constraint and the composition constraint.

Proper Colourings

Base Case — 2×2 Grid

Starting with the simplest case, we want to build a formula to construct all possible $PC_2$ grids. This will help to generalize to larger grids. We use the following grid to refer to cell values:

We start by choosing a value $k$ for $A$, where $k \in {0,1,2}$. To satisfy the edge constraint, $B$ and $C$ can both be either $(k + 1) \bmod 3$ or $(k + 2) \bmod 3$. Now we just have to determine $D$ to satisfy the composition constraint. This is a crucial detail that will allow us to simplify larger problems — $D$ is fully determined by $A,B,C$. To see this, consider the four possible combinations (with the modulo operator left out for simplicity):

For each combination of $A,B,C$, we can complete the grid with $D = (B+C-A) \bmod 3$. We can now construct every $PC_2$ by choosing one of three values for $A$, and one of two values for $B$ and $C$. Therefore, the size of the proper colourings set is $|PC_2| = 3\times2^2$.

Generalized Case — N×N Grid

Without loss of generality, we will consider a 3×3 grid. Extending to larger grids will be obvious. We start by embedding a 2×2 grid into the 3×3 grid:

We already know there are $3\times2^2$ possible combinations of 2×2 grids to define $A,B,D,E$, so we just need a formula to complete the rest of the grid. Looking at the 2×2 grid $D,E,G,H$, it looks like a similar sub-problem as the base case: $D$ and $E$ are already determined, so we need to choose $G$ and $H$ will be fully defined. Similar logic applies to grid $B, C, E, F$ where we choose $E$ and $F$ follows. Finally, for grid $E,F,H,I$ the only unknown is $I$, but the base case shows this is also fully defined.

Therefore, to complete $PC_3$, we only needed to choose values for $G$ and $E$ in addition to $PC_2$. Therefore $|PC_3| = |PC_2|\times2^2=3\times2^4$. This logic directly extends to larger grids, where only values along the first row and column are free variables and the edge constraint means there are only two options after the origin. Therefore, the number of proper colouring grids for any grid size is:

Rotation Groups

To solve the main problem, we need to understand the relationship between grids in $PC_N$ and rotation groups. More specifically, we need a formula for the number of unique grids that comprise any rotation group. We only consider rotations of $0, 90, 180, 270$ degrees because anything else will generate non-unique grids. In fact, for some grids rotations of $90, 180, 270$ degrees will not produce three unique grids. For example, for the following grid, no rotation generates a unique grid:

and its associated rotation group is comprised solely of itself.

To simplify things, we will refer to the set of rotation groups comprised of $N$-many unique grids as $G_N$. Solving the main problem boils down to formulating how $PC_N$ is distributed into sets $G_4, G_2, G_1$, from which the combined size of sets provides our solution.

3×3 Case

Because the grid size for the full problem is odd, we will only focus on odd-sized grids. In the 3×3 case, let us first consider what is required for a $180$-degree rotation to return the same grid.

Using the 2×2 base case, we first choose values for $A$, $B$, $D$. However, unlike the general 3×3 case, the rest of the grid is already fully defined when we combine the proper colouring constraints and the rotation equivalence. For example:

can be completed as follows: $I=k$ because $A=I$, $H=k+1$ because $B=H$, $F=k+2$ because $D=F$, and finally $E=k$, $G=k$, and $C=k$ because of the edge constraint. The complete grid is:

Note in this case $R_0 \neq R_{90}$ but if we had chosen $D=k+1$ or $B=k+2$, then $R_0 = R_{90}=R_{180}=R_{270}$.

Palindrome. We observe that grids in both $G_2$ and $G_1$ are palindromic along the first row and column. Since we know the rest of the grid is defined by these values, we only need the first half of the row and column to define the entire grid. In fact, for $G_1$ grids, we only need to define the column, since the row is identical.

So how many proper colourings can we construct using palindromes? Let’s first define the number of palindrome combinations along first column: $V = 3 \times 2^{\frac{(N-1)}{2}}$, and along the first row (without the origin): $H = 2^{\frac{(N-1)}{2}}$. Since each group in $G_1$ contains one unique grid, the size of the set is $|G_1| = V$. Note that all possible combinations of row and column palindromes will contain both $G_2$ and $G_1$, so we must remove $G_1$ from $G_2$. Also, since each group in $G_2$ contains two unique grids, we have to account for this when we compute the size of the set: $|G_2| = \frac{V \left( H - 1 \right)}{2}$.

Recap. We have almost everything we need to solve this problem. Let us collect the equations (with some symbol redefinitions to make it easier):

The final step is to compute the size of $G_4$. Recall that $G_1$ contains one grid per element, $G_2$ contains two, and $G_4$ contains four. Therefore, we can compute the total number of proper colourings from the size of the $G$ sets: $P = 4 E_4 + 2 E_2 + E_1$ and solve for $E_4$ with $E_4 = \frac{P - 2 E_2 - E_1}{4}$.

Solution. The formula needed to answer the question is $E_1 + E_2 + \frac{P - 2 E_2 - E_1}{4}$, which simplifies to the following:

Since the problem is a $101^2$ grid, the number of groups is $1.2052035331942 \times 10^{60}$.

Supplementary

We wrote a small Python script to verify the solution on smaller grids:

import numpy as np

def is_proper(grid: np.ndarray) -> bool:

    # Check edge constraint
    if not (np.all(grid[:, 1:] != grid[:, :-1]) and np.all(grid[1:, :] != grid[:-1, :])):
        return False

    # Check composition constraint
    a = grid[:-1, :-1]
    b = grid[:-1, 1:]
    c = grid[1:, :-1]
    d = grid[1:, 1:]
    mask = (1 << a) | (1 << b) | (1 << c) | (1 << d)
    return np.all(mask == 7)

def fill_axis(grid: np.ndarray, mask: np.ndarray, vertical: bool) -> None:
    n = grid.shape[0]
    step = np.array([(mask >> i) & 1 for i in range(n-1)], dtype=np.uint8)
    step += 1

    if vertical:
        set_indices = [(i, 0) for i in range(1,n)]
        get_indices = [(i-1, 0) for i in range(1,n)]
    else:
        set_indices = [(0,i) for i in range(1,n)]
        get_indices = [(0,i-1) for i in range(1,n)]

    for i in range(n-1):
        grid[set_indices[i]] = (grid[get_indices[i]] + step[i]) % 3

def fill_interior(grid: np.ndarray) -> None:
    n = grid.shape[0]
    for i in range(1, n):
        for j in range(1, n):
            grid[i, j] = (int(grid[i - 1, j] + grid[i, j - 1]) - int(grid[i - 1, j - 1])) % 3

def generate_proper_grids(n: int, validate: bool):
    if n < 2:
        raise ValueError("n must be >= 2")

    global_set: set[bytes] = set()
    group_set: set[bytes] = set()

    grid = np.empty((n, n), dtype=np.uint8)
    axis_choices = 2 ** (n - 1)

    for origin in (0, 1, 2):
        grid[0,0] = origin
        for v_mask in range(axis_choices):
            fill_axis(grid, v_mask, True)

            for h_mask in range(axis_choices):
                fill_axis(grid, h_mask, False)

                fill_interior(grid)

                if validate:
                    assert is_proper(grid)

                key = grid.tobytes()
                if key in global_set:
                    continue

                group_set.add(key)
                global_set.add(key)
                global_set.add(np.rot90(grid, 1).tobytes())
                global_set.add(np.rot90(grid, 2).tobytes())
                global_set.add(np.rot90(grid, 3).tobytes())

    return {"group_count": len(group_set),
            "global_count": len(global_set)}


def main():

    start_N = 3
    finish_N = 11
    for N in range(start_N, finish_N, 2):
        result = generate_proper_grids(N, True)

        V = 3 * 2 **((N-1)//2)
        H = 2 **((N-1)//2)
        P = 3 * 2**(2*(N-1))
        E1 = V
        E2 = V*(H-1) // 2
        E4 = (P - 2*E2 - E1) // 4
        G = E1+E2+E4

        assert (result["group_count"] == G)
        assert (result["global_count"] == P)

        print(f"N={N}")
        print(f"Computed: groups {result['group_count']}, Proper Colourings {result['global_count']}")
        print(f"Calculated: groups {G}, Proper Colourings {P}\n")

if __name__ == "__main__":
    main()