Project Euler

Tri-colouring a Triangular Grid

Consider the following configuration of 64 triangles: A triangular grid of side 8 is divided into small triangles (both upward-pointing and downward-pointing). We need to colour each small triangle...

Source sync Apr 19, 2026

Problem #0189

Level Level 10

Solved By 2,453

Languages C++, Python

Answer 10834893628237824

Length 411 words

geometrydynamic_programminggraph

Consider the following configuration of $64$ triangles:

We wish to colour the interior of each triangle with one of three colours: red, green or blue, so that no two neighbouring triangles have the same colour. Such a colouring shall be called valid. Here, two triangles are said to be neighbouring if they share an edge.

Note: if they only share a vertex, then they are not neighbours.

A colouring $C^\prime $ which is obtained from a colouring $C$ by rotation or reflection is considered distinct from $C$ unless the two are identical.

How many distinct valid colourings are there for the above configuration?

Problem 189: Tri-colouring a Triangular Grid

Mathematical Analysis

Grid Structure

A triangular grid of side $n$ has $n^2$ small triangles arranged in $n$ rows:

Row $k$ (for $k = 1, \ldots, n$ ) contains $2k - 1$ triangles.
Row $k$ has $k$ upward-pointing triangles and $k - 1$ downward-pointing triangles.
Total triangles: $n^2 = 64$ for $n = 8$ .

Adjacency Rules

An upward-pointing triangle in row $k$ is adjacent to its left and right neighbors in the same row (if they exist) and to the downward-pointing triangle directly below it in row $k+1$ .
A downward-pointing triangle in row $k$ is adjacent to its left and right neighbors and to the upward-pointing triangle directly above it in row $k-1$ .

Row-by-Row Dynamic Programming

We process the grid row by row. The key insight is that the coloring constraints between rows only involve the “top edge” colors visible to the next row.

For each row, the state is defined by the sequence of colors of the upward-pointing triangles (since only these have edges connecting to the next row’s downward-pointing triangles).

State: A tuple of $k$ colors representing the upward-pointing triangles in row $k$ .

Transition: When moving from row $k$ (with $k$ upward triangles) to row $k+1$ (with $k+1$ upward triangles and $k$ downward triangles):

Each downward triangle $j$ in row $k+1$ must differ from upward triangle $j$ of row $k$ (shared edge) and from upward triangles $j$ and $j+1$ of row $k+1$ (adjacent in same row).
Upward triangles in row $k+1$ must differ from their same-row neighbors.

Implementation

We enumerate all valid colorings of upward triangles per row, then for each pair of consecutive rows, check if a valid assignment of the downward triangles exists. This uses dynamic programming with state being the coloring of upward triangles.

The number of upward triangles per row is at most 8, giving at most $3^8 = 6561$ states. The transitions are computed by iterating over valid configurations.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity

Time: $O(n \cdot 3^{2n})$ in the worst case (for the transition computation), where $n = 8$ .
Space: $O(3^n)$ for storing the DP states.

Answer

\boxed{10834893628237824}

C++ project_euler/problem_189/solution.cpp

#include <bits/stdc++.h>
using namespace std;

// Encode a row's upward triangle colors as a base-3 number
// Row k has k upward triangles, colors 0,1,2

int main() {
    const int N = 8;

    // Row 1: 1 upward triangle, 3 choices
    // State: tuple of colors of upward triangles
    // Represent as vector<int> -> map to count

    // Use map from vector<int> to long long count
    // Row 1
    map<vector<int>, long long> dp;
    for (int c = 0; c < 3; c++) {
        dp[{c}] += 1;
    }

    for (int row = 2; row <= N; row++) {
        // Previous row has (row-1) upward triangles
        // Current row has row upward triangles and (row-1) downward triangles
        // Order in current row: up_1, down_1, up_2, down_2, ..., down_{row-1}, up_row
        // Adjacency within row: consecutive elements differ
        // Adjacency between rows: down_j in current row is adjacent to up_j in previous row

        map<vector<int>, long long> new_dp;

        for (auto& [prev_up, cnt] : dp) {
            // Generate all valid colorings of current row
            // Current row upward triangles: up[0..row-1]
            // Current row downward triangles: down[0..row-2]
            // Constraints:
            //   up[0] != down[0]
            //   down[j] != up[j], down[j] != up[j+1], down[j] != prev_up[j]
            //   (within row: up[j] != down[j-1] for j>=1, and up[j] != down[j] for j<row-1)
            //   These are equivalent to the above since the sequence alternates

            // Build current row incrementally: up[0], down[0], up[1], down[1], ...
            // At each step, choose color satisfying constraints

            // Use recursive generation
            vector<int> cur_up(row), cur_down(row - 1);

            function<void(int)> generate = [&](int pos) {
                // pos goes through the 2*row-1 triangles in order:
                // 0: up[0], 1: down[0], 2: up[1], 3: down[1], ...
                if (pos == 2 * row - 1) {
                    new_dp[cur_up] += cnt;
                    return;
                }

                if (pos % 2 == 0) {
                    // Upward triangle: index pos/2
                    int idx = pos / 2;
                    for (int c = 0; c < 3; c++) {
                        // Must differ from left neighbor (down[idx-1]) if exists
                        if (idx > 0 && c == cur_down[idx - 1]) continue;
                        cur_up[idx] = c;
                        generate(pos + 1);
                    }
                } else {
                    // Downward triangle: index pos/2
                    int idx = pos / 2;
                    for (int c = 0; c < 3; c++) {
                        // Must differ from left neighbor (up[idx])
                        if (c == cur_up[idx]) continue;
                        // Must differ from right neighbor (up[idx+1]) - not placed yet
                        // Actually we handle that when placing up[idx+1]
                        // Must differ from prev_up[idx] (top neighbor)
                        if (c == prev_up[idx]) continue;
                        cur_down[idx] = c;
                        generate(pos + 1);
                    }
                }
            };

            generate(0);
        }

        dp = new_dp;
    }

    long long total = 0;
    for (auto& [state, cnt] : dp) {
        total += cnt;
    }

    cout << total << endl;
    return 0;
}

Python project_euler/problem_189/solution.py

"""
Problem 189: Tri-colouring a Triangular Grid

Count valid 3-colourings of a triangular grid of side 8 where no two
adjacent triangles share the same colour.
"""
from collections import defaultdict

def solve():
    N = 8

    # Row 1: 1 upward triangle
    # State = tuple of colors of upward triangles in the row
    dp = defaultdict(int)
    for c in range(3):
        dp[(c,)] += 1

    for row in range(2, N + 1):
        new_dp = defaultdict(int)

        for prev_up, cnt in dp.items():
            # Generate valid colorings of current row
            # Current row: row upward triangles, (row-1) downward triangles
            # Sequence: up[0], down[0], up[1], down[1], ..., down[row-2], up[row-1]

            cur_up = [0] * row
            cur_down = [0] * (row - 1)

            def generate(pos):
                if pos == 2 * row - 1:
                    new_dp[tuple(cur_up)] += cnt
                    return

                if pos % 2 == 0:
                    # Upward triangle at index pos//2
                    idx = pos // 2
                    for c in range(3):
                        if idx > 0 and c == cur_down[idx - 1]:
                            continue
                        cur_up[idx] = c
                        generate(pos + 1)
                else:
                    # Downward triangle at index pos//2
                    idx = pos // 2
                    for c in range(3):
                        if c == cur_up[idx]:
                            continue
                        if c == prev_up[idx]:
                            continue
                        cur_down[idx] = c
                        generate(pos + 1)

            generate(0)

        dp = new_dp

    total = sum(dp.values())
    print(total)

if __name__ == "__main__":
    solve()