Detailed mathematical approach

Problem Summary

The problem asks for the number of proper 3-colorings of a triangular grid: every vertex receives one of three colors, and any two adjacent vertices must have different colors. In the actual instance there are \(n=8\) rows, row \(r\) contains \(2r+1\) vertices, and the whole graph therefore has \(1+3+\cdots+15=8^2=64\) vertices.

A brute-force search over \(3^{64}\) assignments is completely unrealistic. The successful idea is to sweep through the triangle row by row and keep only the interface information that can still influence the next row.

Mathematical Approach

The triangular shape is the reason a compact dynamic program exists. Once the rows are written in the right way, the dependence between consecutive rows becomes digitwise and can be aggregated efficiently.

Row structure and the future-facing boundary

Number the rows from top to bottom by \(r=0,1,\dots,n-1\). A coloring of row \(r\) can be written as

$v=(x_0,x_1,\dots,x_{2r}).$

Inside one row, consecutive vertices are adjacent, so every legal row coloring must satisfy

$x_i\ne x_{i+1}\qquad(0\le i\lt 2r).$

Now compare two consecutive rows. If row \(r-1\) is \((a_0,a_1,\dots,a_{2r-2})\) and row \(r\) is \((b_0,b_1,\dots,b_{2r})\), then the only inter-row edges join \(a_{2j}\) to \(b_{2j+1}\) for \(j=0,1,\dots,r-1\). So the previous row influences the next row only through its even positions, and the new row is constrained only at its odd positions.

Legal row states and signature splitting

Let \(S_r\) be the set of all legal colorings of row \(r\). Because the first entry has 3 choices and each later entry has exactly 2 choices different from its left neighbor,

$|S_r|=3\cdot 2^{2r}=3\cdot 4^r.$

For a state \(v=(x_0,\dots,x_{2r})\in S_r\), split the row into its even-position and odd-position signatures:

$E(v)=(x_0,x_2,\dots,x_{2r}),\qquad O(v)=(x_1,x_3,\dots,x_{2r-1}).$

The even signature has length \(r+1\), while the odd signature has length \(r\). This split is not cosmetic: \(O(v)\) is the part that must agree with the previous row's restrictions, and \(E(v)\) is the part that remains exposed to the next row.

The dynamic programming recurrence

Let \(F_r(v)\) denote the number of proper colorings of the first \(r+1\) rows whose \(r\)-th row is exactly \(v\in S_r\). The base case is row \(0\): there are three one-vertex colorings, and each contributes 1.

If \(u\in S_{r-1}\) and \(v\in S_r\), then the two rows are compatible exactly when every even-position color of \(u\) differs from the touching odd-position color of \(v\):

$E(u)_j\ne O(v)_j\qquad(j=0,1,\dots,r-1).$

Therefore

$F_r(v)=\sum_{\substack{u\in S_{r-1}\\ E(u)_j\ne O(v)_j\ \forall j}} F_{r-1}(u).$

After the last row, the required count is simply

$T_n=\sum_{v\in S_{n-1}} F_{n-1}(v).$

Collapse the transition to exposed interfaces

The recurrence still sums over every full coloring of the previous row, but the compatibility test depends only on \(E(u)\). That means we can aggregate all previous rows with the same exposed even signature. For each \(e\in\{0,1,2\}^r\), define

$A_{r-1}(e)=\sum_{\substack{u\in S_{r-1}\\ E(u)=e}} F_{r-1}(u).$

Then the transition becomes

$F_r(v)=\sum_{\substack{e\in\{0,1,2\}^r\\ e_j\ne O(v)_j\ \forall j}} A_{r-1}(e).$

This is the central simplification. For a fixed odd signature \(O(v)\), each digit of \(e\) may be any of the two colors different from the required odd digit, so exactly \(2^r\) even signatures are compatible out of the full \(3^r\) signature space. The implementations exploit precisely this digitwise independence.

Worked example: from width 3 to width 5

Consider the current row coloring

$v=(0,1,2,0,1).$

It is legal because neighboring entries are all different. Its odd signature is

$O(v)=(1,0).$

Any previous row of width 3 contributes only through its even signature \(e=(e_0,e_1)\), and compatibility requires

$e_0\ne 1,\qquad e_1\ne 0.$

So the only compatible even signatures are

$e\in\{(0,1),(0,2),(2,1),(2,2)\}.$

For this one row state we therefore have

$F_2(v)=A_1(0,1)+A_1(0,2)+A_1(2,1)+A_1(2,2).$

This small example shows why the transition naturally produces a \(2^r\) branching factor: each odd-position color forbids exactly one choice for the matching exposed digit from the previous row. As a whole-triangle sanity check, the 2-row triangle has \(3\cdot 2\cdot 2\cdot 2=24\) proper colorings.

How the Code Works

Enumerating admissible rows once

The C++, Python, and Java implementations first generate every legal coloring of each row with a depth-first search that enforces \(x_i\ne x_{i+1}\). Each row state is then stored through its odd and even signatures. The C++ and Python implementations encode these signatures as base-3 integers, while the Java implementation derives compact string signatures from the same row states.

Rolling the dynamic program through the interface

At the transition from row \(r-1\) to row \(r\), the implementations combine all previous counts that share the same exposed even signature. That converts many full row states into a much smaller table indexed by the \(3^r\) possible even signatures of length \(r\). Each current row then needs only the sum over those previous signatures that are digitwise different from its odd signature.

Reusing repeated compatibility queries

Many current row states have the same odd signature. The C++ and Python implementations memoize the compatible-interface sum for each required odd signature and obtain it by recursively enumerating the \(2^r\) admissible previous signatures. The Java implementation expresses the same recurrence more directly by scanning the aggregated previous signatures and testing digitwise compatibility. After the final row, all remaining counts are added. The C++ implementation also contains a brute-force cross-check for very small triangles, which independently verifies the recurrence.

Complexity Analysis

Row \(r\) has \(3\cdot 4^r\) legal states, so the largest row in the actual problem, \(r=7\), has \(3\cdot 4^7=49{,}152\) states. This is far smaller than \(3^{64}\), but still large enough that a naive row-to-row all-pairs transition would be wasteful.

After interface compression, the transition from row \(r-1\) to row \(r\) lives in a signature space of size \(3^r\). In the optimized integer-coded versions, building the aggregated table costs \(O(4^r)\), and evaluating all distinct compatibility sums costs \(O(3^r2^r)=O(6^r)\). Memory during the sweep is dominated by the current and previous row tables together with an aggregation array of size \(3^r\). Since the problem stops at \(r=7\), the method runs comfortably and computes the exact count without approximation.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=189
2. Graph coloring: Wikipedia - Graph coloring
3. Dynamic programming: Wikipedia - Dynamic programming
4. Transfer-matrix method: Wikipedia - Transfer-matrix method
5. Ternary numeral system: Wikipedia - Ternary numeral system
6. Triangular tiling: Wikipedia - Triangular tiling