Problem 189: Tri-colouring a Triangular Grid

Detailed mathematical approach

Problem Summary

A large triangle is cut into \(64\) small triangles by lines parallel to its sides. Counted from the top, its eight rows contain \(1,3,5,\dots,15\) small triangles, pointing alternately up and down, beginning and ending with an upward one. Every small triangle is to be coloured red, green or blue so that two triangles sharing an edge never have the same colour; triangles that meet only at a corner are not neighbours. Such a colouring is valid. Colourings obtained from each other by a rotation or a reflection count as different unless identical, so we count all valid colourings of the fixed figure. The statement shows one valid colouring and gives no numerical checkpoint. ^[1]

The whole solution in one sentence: we colour the figure one row at a time and group the counts so far by the colours of the upward triangles in the last row, because those are the only triangles that touch the next row.

Mathematical Approach

1. Rows, positions and neighbours

Number the rows \(r=0,1,\dots,7\) from the top and the triangles of row \(r\) by their positions \(c=0,1,\dots,2r\) from left to right. Even positions point up and odd ones down, so row \(r\) has \(r+1\) upward and \(r\) downward triangles, \(36\) and \(28\) in all. There are two kinds of neighbours:

• Inside a row, the triangles at positions \(c\) and \(c+1\) share a slanted edge.
• Between rows, the \(r\) upward triangles of row \(r-1\) stand with their bases on the line below that row, and the \(r\) downward triangles of row \(r\) hang from the same line with their tops. Both cover the line from left to right in pieces of unit length, so the downward triangle at position \(2j+1\) of row \(r\) shares an edge with the upward triangle at position \(2j\) of row \(r-1\), for \(j=0,1,\dots,r-1\).

All other edges lie on the boundary of the large triangle. Hence every neighbouring pair consists of an upward and a downward triangle, and every downward triangle has exactly three neighbours, the upward triangles to its left, to its right and above it; the figure has \(3\cdot28=84\) neighbouring pairs.

2. Graph colouring and the smallest figures

Joining neighbouring triangles gives a graph, and a valid colouring is a proper colouring of its vertices with three colours, in which the two ends of every edge differ. ^[2] The count is the value at \(3\) of its chromatic polynomial, which for arbitrary graphs is #P-complete to compute, ^[3] so we must use the shape of the figure. Every edge joins an upward and a downward triangle, so the graph is bipartite: ^[2] all upward triangles red and all downward ones green is valid, and not all three colours need to appear.

One row has \(3\) colourings. With two rows, the middle downward triangle touches the three upward ones, which touch nothing else, so the graph is a tree: \(3\) colours for the middle and \(2\) for each neighbour give \(3\cdot2^3=24\), the tree polynomial \(x(x-1)^3\) at \(x=3\). ^[3] From three rows on, the six triangles around each inner grid point form a closed ring, \(21\) rings for eight rows, and the choices are no longer independent. Trying all \(3^{64}\approx3.4\cdot10^{30}\) assignments is hopeless, and by Section 8 more than \(10^{12}\) colourings are valid, so they must be counted without being listed.

3. Colourings of one row

Write the colours as \(0\), \(1\) and \(2\). A colouring of row \(r\) is a sequence \(v=(x_0,x_1,\dots,x_{2r})\) in which consecutive entries differ. The first entry has \(3\) choices and each later one \(2\), because it only has to avoid its left neighbour, so the set \(S_r\) of these sequences has \(|S_r|=3\cdot4^r\) elements: from \(3\) for row \(0\) to \(49152\) for row \(7\), and \(4^8-1=65535\) for all eight rows.

4. What neighbouring rows share

Split a row colouring \(v\in S_r\) into the colours of its upward and of its downward triangles, the entries at even and at odd positions:

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

They have \(r+1\) and \(r\) entries. By Section 1, colourings \(u\in S_{r-1}\) and \(v\in S_r\) of consecutive rows cause no conflict between the two rows, and we say that \(u\) fits \(v\), written \(u\sim v\), exactly when

$$\begin{aligned}&E(u)_j\ne O(v)_j\\&\qquad(j=0,1,\dots,r-1).\end{aligned}$$

For example, \(v=(0,1,2,0,1)\) has \(O(v)=(1,0)\). The colouring \(u=(0,1,2)\) of row \(1\) has \(E(u)=(0,2)\) and fits, while \(u=(1,0,1)\) has \(E(u)=(1,1)\) and does not, because its first upward triangle and the first downward triangle of \(v\) both get colour \(1\).

5. Counting row by row

Let \(F_r(v)\) be the number of valid colourings of rows \(0,1,\dots,r\) whose row \(r\) is coloured \(v\in S_r\). Then \(F_0(v)=1\) for the three colourings of row \(0\), and for \(r\ge1\)

$$F_r(v)=\sum_{u\in S_{r-1},\ u\sim v}F_{r-1}(u).$$

Indeed, every neighbouring pair lies inside one row or in two consecutive rows. A colouring of rows \(0,\dots,r\) is therefore valid exactly when its rows \(0,\dots,r-1\) form a valid colouring, its row \(r\) is some \(v\in S_r\), and its row \(r-1\), say \(u\), satisfies \(u\sim v\). Deleting row \(r\) thus matches the colourings counted by \(F_r(v)\) one-to-one with the valid colourings of rows \(0,\dots,r-1\) whose last row fits \(v\), and grouping these by their last row \(u\) gives the sum. Summing over the colouring of the last row, the number of valid colourings of \(n\) rows is

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

Building each table once from the previous one is dynamic programming, ^[4] and slicing a system into layers that interact only with neighbouring layers is the transfer-matrix method of statistical mechanics. ^[5] Done naively, the last step alone would test \(12288\cdot49152\approx6\cdot10^8\) pairs \((u,v)\).

6. Grouping by the upward colours

Whether \(u\sim v\) holds depends on \(u\) only through \(E(u)\). We therefore add up the counts of all colourings of the previous row that share an upward pattern \(e\in\{0,1,2\}^r\):

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

Claim. For every \(v\in S_r\) we have \(F_r(v)=G_r(O(v))\), where for each downward pattern \(o\in\{0,1,2\}^r\)

$$G_r(o)=\sum_{e:\ e_j\ne o_j\ \forall j}A_{r-1}(e).$$

Proof. Split the sum of Section 5 according to the value \(e=E(u)\). For a fixed \(e\), either all these \(u\) fit \(v\), when \(e_j\ne O(v)_j\) for every \(j\), or none of them does, and together they contribute \(A_{r-1}(e)\). \(\square\)

Every downward pattern \(o\) occurs in some colouring of row \(r\), because each upward triangle of the row can avoid the at most two colours of the downward triangles beside it, so exactly \(3^r\) values \(G_r(o)\) are needed: \(2187\) for the last row instead of \(49152\) separate sums. Each \(e_j\) is chosen independently among the two colours other than \(o_j\), so every \(G_r(o)\) is a sum of exactly \(2^r\) values. A pattern \(e\) is stored as the base-\(3\) number \(e_0+3e_1+\dots+3^{r-1}e_{r-1}\), ^[6] which turns \(A_{r-1}\) and \(G_r\) into arrays of \(3^r\) entries.

7. Worked example: three rows

Row \(0\) gives \(A_0(e)=1\) for each colour \(e\). Each \(G_1(o)\) adds this value for the two colours \(e\ne o\), so \(F_1(v)=2\) for all \(12\) colourings of row \(1\), and \(T_2=24\). Next, \(A_1(e_0,e_1)\) adds \(F_1=2\) over the colourings \((e_0,x_1,e_1)\) of row \(1\), in which \(x_1\) avoids \(e_0\) and \(e_1\). Hence \(A_1=4\) if \(e_0=e_1\) and \(A_1=2\) otherwise; as a check, the \(3\) equal and \(6\) unequal pairs give \(3\cdot4+6\cdot2=24\).

For row \(2\), take a downward pattern \(o=(o_0,o_1)\). If \(o_0=o_1\), both \(e_0\) and \(e_1\) come from the two other colours, which gives two equal and two unequal pairs and \(G_2(o)=4+4+2+2=12\). If \(o_0\ne o_1\), exactly one of the four allowed pairs is equal, the one that repeats the third colour, so \(G_2(o)=4+2+2+2=10\); for \(o=(0,1)\) the allowed pairs are \((1,0)\), \((1,2)\), \((2,0)\) and \((2,2)\). In a colouring \((x_0,o_0,x_2,o_1,x_4)\) of row \(2\), the end entries \(x_0\) and \(x_4\) have \(2\) choices each, and \(x_2\) must avoid both \(o_0\) and \(o_1\). Each of the \(3\) equal patterns therefore occurs \(8\) times and each of the \(6\) unequal ones \(4\) times, \(48\) colourings in all, and

$$T_3=24\cdot12+24\cdot10=528,$$

as a test of all \(3^9=19683\) colour assignments confirms. The same steps give \(T_4=31968\), \(T_5=5332224\), \(T_6=2450774016\) and \(T_7=3104112826368\).

8. Every colouring of the top rows can be continued

Below a valid colouring of rows \(0,\dots,r-1\), colour row \(r\) from left to right. The first triangle has \(3\) choices; each downward triangle must avoid its left neighbour and the triangle above it, which leaves \(1\) or \(2\) choices; and the upward triangle after it must avoid only its left neighbour, which leaves \(2\). Every colouring of the top \(r\) rows therefore extends in at least \(3\cdot2^r\) ways, and

$$T_n\ge\prod_{r=0}^{n-1}3\cdot2^{r}=3^{n}\,2^{n(n-1)/2},$$

which is \(3^8\cdot2^{28}\approx1.8\cdot10^{12}\) for eight rows. Different colourings of the top rows have different continuations, so every count that occurs during the computation, being a number of valid colourings of some top rows, is at most \(T_n\).

9. Colouring the downward triangles last

All neighbours of a downward triangle point up, so once the \(36\) upward triangles are coloured, each downward triangle independently has \(3-d\) choices, \(d\) being the number of different colours among its three neighbours. For two rows, \(3\) of the \(27\) colourings of the upward triangles use one colour, \(18\) use two and \(6\) use three, and \(3\cdot2+18\cdot1+6\cdot0=24\) again. Row by row, this is a transfer matrix ^[5] from the upward colours \(a\) of row \(r-1\) to those, \(b\), of row \(r\), with the entries

$$\prod_{j=0}^{r-1}\Bigl(3-\bigl|\{a_j,b_j,b_{j+1}\}\bigr|\Bigr).$$

The programs do not use this form, but it served as an independent check.

How the Code Works

In the C++ program, ^[7] parse_arguments reads --size=, with \(8\) rows as the default, and --skip-checkpoints; any other argument, an empty or non-digit size included, or a size below \(1\) gives exit code \(1\). parse_int_after_prefix accumulates the digits in an int without a range check, so a size beyond the range of int is undefined behaviour. ^[8] Unless switched off, run_checkpoints requires solve(n) to equal brute_small(n) for \(n=1,2,3,4\), where both give \(3\), \(24\), \(528\) and \(31968\), and otherwise leads to exit code \(2\); then main prints solve(options.size).

build_row_states, called with the length \(2r+1\), lists \(S_r\) by a depth-first search that skips the colour of the left neighbour, and keeps for each colouring only a RowState with the base-3 codes even_code of \(E(v)\) and odd_code of \(O(v)\), leftmost triangle in the lowest digit. solve builds these lists for all rows, starts with dp_prev holding three ones, which is \(F_0\), and for each later row \(r\)

• adds dp_prev[i] into agg[even_code] for every state i of row \(r-1\), which gives \(A_{r-1}\);
• evaluates \(G_r(o)\) in compatible_sum(req_code): the digits of req_code go into req_digits, and the recursive lambda rec gives each position the two colours other than its digit and adds agg[code] at each of the \(2^r\) leaves; memo caches the results, the largest u64 value marking an empty entry;
• sets dp_curr[i] to compatible_sum(odd_code) for every state of row \(r\), which is \(F_r\) by Section 6, and swaps it into dp_prev.

The sum of the final dp_prev is \(T_n\). brute_small numbers the triangles row by row, row \(r\) from index \(r^2\), and backtracks, testing each colour against the neighbours with a smaller index.

Python nests build_row_states and the cached recurrence inside solve, with lists, tuples and a dictionary memo; like Java, it fixes \(8\) rows and has no options or checkpoints, and its recursion is at most \(16\) calls deep. Java keeps \(A_{r-1}\) directly, in a HashMap dp keyed by the digit strings evenSig of the previous row. For each colouring of row \(r\) it adds the values of all keys that compatible accepts against oddSig, without a cache, and merge adds the result to the entry of the colouring's own upward pattern, building \(A_r\). The final sum of all values is \(T_n\).

C++ counts in u64, an unsigned 64-bit type, Java in the signed 64-bit long, and Python with unbounded integers. By Section 8 no intermediate value exceeds \(T_8\). Each colouring of eight rows is one of seven rows followed by one of the \(3\cdot4^7=49152\) row colourings, so \(T_8\le49152\,T_7\), and \(T_7\lt2^{42}\) gives \(T_8\lt2^{58}\): nothing overflows. With --size=, however, C++ is exact only up to \(8\) rows. For \(9\) rows the count is about \(1.04\cdot10^{20}\) by an exact Python computation, more than \(2^{64}\), and since unsigned arithmetic works modulo \(2^{64}\), ^[8] the program silently prints its remainder on division by \(2^{64}\). From \(10\) rows on, compatible_sum writes past the end of req_digits, a std::array<int, 8> whose operator[] checks no bounds, which is undefined behaviour. ^[8]

Complexity and Verification

For \(n\) rows, the C++ and Python programs list \(4^n-1\) row colourings, make \(4^{n-1}-1\) additions into agg and \(4^n-4\) lookups of cached sums, and the cached sums visit

$$\sum_{r=1}^{n-1}3^r\cdot2^r=\frac{6^n-6}{5}$$

leaves. This takes \(O(6^n)\) time, as encoding the rows adds only \(O(n\cdot4^n)\), and \(O(4^n)\) memory, because the lists of all rows are kept. For \(8\) rows these are \(65535\) row colourings, about half a megabyte of codes in C++, \(16383\) additions, \(65532\) lookups and \(3279\) cached sums with \(335922\) leaves. The Java program calls compatible for each of the \(3\cdot4^r\) colourings of row \(r\) and each of the \(3^r\) keys, \(117267732\) calls for \(8\) rows, each comparing at most \(r\) digits, so its time is \(O(n\cdot12^n)\); it also keeps every row colouring as a full array, \(O(n\cdot4^n)\) memory. On the computer used for this article, C++ took about \(0.01\) seconds, Python \(0.16\) and Java, including the start of its virtual machine, \(0.9\).

Besides the C++ checkpoints, we checked for this article that the three programs print the same number; that a separate C backtracking search finds \(T_1,\dots,T_6\), listing all \(2450774016\) colourings of six rows; that the transfer of Section 9 and a generic triangle-by-triangle dynamic programming, run in two different orders, reproduce \(T_1,\dots,T_7\) and agree with the programs for eight rows; and that every \(T_n\) with \(2\le n\le8\) is divisible by \(6\). The last test must hold, because permuting the three colours maps valid colourings to valid ones, and only the identity fixes a colouring that uses at least two colours. A memory checker confirms the write past req_digits for \(10\) rows. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The neighbour structure, the row recurrence and its grouping by upward patterns, the worked example and the bounds are derived in this article.

1. Project Euler 189 — Tri-colouring a Triangular Grid. The official statement asks for the number of colourings of 64 triangles with red, green and blue in which triangles sharing an edge differ; triangles sharing only a vertex are not neighbours, and rotated or reflected colourings count as distinct unless identical.
2. Wikipedia — Graph coloring. A proper vertex colouring gives the two ends of every edge different colours, and the graphs that can be coloured with two colours are exactly the bipartite graphs.
3. Wikipedia — Chromatic polynomial. P(G, k) counts the proper k-colourings of a graph G. A graph with n vertices is a tree exactly when P(G, x) = x(x − 1)ⁿ⁻¹, and evaluating P(G, 3) for a given graph G is #P-complete.
4. Wikipedia — Dynamic programming. Each sub-problem is solved only once; saving values already calculated is called memoization, and the bottom-up approach builds larger solutions from tables of smaller ones.
5. Wikipedia — Transfer-matrix method (statistical mechanics). It applies when a system can be broken into a sequence of subsystems that interact only with adjacent ones; transfer matrices carry the weights between the states of consecutive subsystems.
6. Wikipedia — Ternary numeral system. Base 3 writes numbers with the digits 0, 1 and 2, the places being worth the powers of 3; for example, 365 is 111112 in base 3.
7. C++ — Euler189.cpp. The linked immutable C++ revision contains build_row_states, solve, brute_small and run_checkpoints. It is the implementation record for this article.
8. cppreference — Arithmetic operators: unsigned arithmetic is performed modulo 2ⁿ for an n-bit type, while signed overflow is undefined behaviour. cppreference — std::array::operator[]: no bounds checking is performed, and accessing a nonexistent element is undefined behaviour.