Solution

Answer: 10834893628237824

Let the large equilateral triangle have side length $8$.

It is subdivided into

$$1+3+5+\cdots+15 = 8^2 = 64$$

small triangles.

We must count the number of proper $3$-colourings of these $64$ triangles, where adjacent triangles (sharing an edge) receive different colours.

1. Mathematical analysis

1.1 The graph interpretation

Treat each small triangle as a vertex of a graph.

Two vertices are connected iff the corresponding triangles share an edge.
We want the number of proper colourings of this graph using colours

${R,G,B}$.

This is therefore a graph-colouring counting problem.

The graph has:

$64$ vertices,
maximum degree $3$,
a very regular layered structure.

A direct brute-force search would require checking

$$3^{64} \approx 3.4\times10^{30}$$

assignments, which is impossible.

So we need dynamic programming.

1.2 Key insight: small frontier width

If we process triangles row-by-row (or more precisely, in a suitable geometric order), then at any moment only a small number of already-coloured triangles can still interact with future triangles.

This set is called the frontier.

For the triangular grid of side $8$, the frontier never exceeds size $8$.

Therefore:

instead of remembering all previous colours,
we only remember the colours on the frontier.

Since each frontier vertex has $3$ possible colours, the number of states is at most

$$3^8 = 6561,$$

which is tiny.

This makes an exact computation feasible.

1.3 Dynamic programming state

Suppose we process triangles in a fixed order:

$$T_0,T_1,\dots,T_{63}.$$

At step $i$:

some previously processed triangles still have neighbours not yet processed;
these triangles form the frontier.

The DP state is simply:

$$(\text{frontier colouring}) \mapsto \text{count}.$$

When processing the next triangle:

Determine which colours are forbidden by already-coloured neighbours.
Try the remaining colours.
Update the frontier.

Because every triangle has degree at most $3$, each transition is very small.

2. Python implementation

from collections import defaultdict

# ------------------------------------------------------------
# Build the triangular grid graph
# ------------------------------------------------------------

def build_graph(n):
    """
    Build the adjacency graph of the n^2 little triangles.

    Each small triangle is represented by its three lattice vertices.
    Two triangles are adjacent iff they share an edge
    (i.e. two common vertices).
    """

    triangles = []

    # Upward-pointing triangles
    for i in range(n):
        for j in range(n - i):
            tri = ((i, j), (i + 1, j), (i, j + 1))
            triangles.append(tri)

    # Downward-pointing triangles
    for i in range(n - 1):
        for j in range(n - 1 - i):
            tri = ((i + 1, j), (i, j + 1), (i + 1, j + 1))
            triangles.append(tri)

    m = len(triangles)

    # Build adjacency
    adj = [set() for _ in range(m)]

    for a in range(m):
        A = set(triangles[a])

        for b in range(a + 1, m):
            B = set(triangles[b])

            # Sharing an edge means sharing exactly two vertices
            if len(A & B) == 2:
                adj[a].add(b)
                adj[b].add(a)

    return triangles, adj

# ------------------------------------------------------------
# Choose a geometric processing order
# ------------------------------------------------------------

def triangle_centroid(tri):
    x = sum(v[0] for v in tri) / 3
    y = sum(v[1] for v in tri) / 3
    return (y, x)

# ------------------------------------------------------------
# Count proper 3-colourings using frontier DP
# ------------------------------------------------------------

def count_colourings(n=8):

    triangles, adj = build_graph(n)

    m = len(triangles)

    # Process triangles from top to bottom
    order = sorted(range(m),
                   key=lambda t: triangle_centroid(triangles[t]))

    pos = {v: i for i, v in enumerate(order)}

    # Past neighbours of each vertex
    past = {
        v: [u for u in adj[v] if pos[u] < pos[v]]
        for v in range(m)
    }

    # DP:
    # state = tuple of frontier colours
    # value = number of ways
    states = {(): 1}

    for i, v in enumerate(order):

        # Current active frontier
        active = sorted(
            {
                u for u in order[:i]
                if any(pos[w] >= i for w in adj[u])
            },
            key=lambda x: pos[x]
        )

        # Frontier after processing v
        next_active = sorted(
            {
                u for u in order[:i + 1]
                if any(pos[w] > i for w in adj[u])
            },
            key=lambda x: pos[x]
        )

        new_states = defaultdict(int)

        for key, count in states.items():

            colouring = dict(zip(active, key))

            # Colours forbidden by already-coloured neighbours
            forbidden = {
                colouring[u]
                for u in past[v]
                if u in colouring
            }

            for colour in range(3):

                if colour in forbidden:
                    continue

                new_colouring = colouring.copy()

                # Keep v only if it still has future neighbours
                if any(pos[w] > i for w in adj[v]):
                    new_colouring[v] = colour

                new_key = tuple(new_colouring[u]
                                for u in next_active)

                new_states[new_key] += count

        states = new_states

    return sum(states.values())

# ------------------------------------------------------------
# Compute the answer
# ------------------------------------------------------------

answer = count_colourings(8)

print(answer)

3. Code walkthrough

Graph construction

Each small triangle is encoded by its three lattice vertices.

Example upward triangle:

$$((i,j),(i+1,j),(i,j+1)).$$

Example downward triangle:

$$((i+1,j),(i,j+1),(i+1,j+1)).$$

Two triangles are neighbours exactly when they share two vertices.

Ordering

We process triangles from top to bottom using centroid coordinates.

This keeps the frontier small.

DP states

A state stores:

which frontier triangles exist,
and their colours.

The tuple key might look like:

(0, 2, 1, 0)

meaning:

frontier triangle #1 has colour 0,
frontier triangle #2 has colour 2,
etc.

Transition step

For the next triangle:

Find colours already used by neighbouring frontier triangles.
Try the remaining colours.
Update the frontier tuple.

4. Small sanity checks

For very small triangles:

side length $1$:

$$3$$

colourings.

side length $2$:

easy to verify by brute force.

The DP reproduces these correctly.

The final value is roughly $10^{16}$, which is reasonable:

much smaller than $3^{64}$,
but still enormous because the graph is sparse.

5. Final verification

Running the program gives:

$$10834893628237824$$

This is a positive integer of plausible magnitude and is the accepted Project Euler value.

Answer: 10834893628237824

Project Euler Problem 189