Detailed mathematical approach

Problem Summary

Let \(O_{a,b}\) be the equal-angled octagon whose side lengths, read cyclically, are \(a,b,a,b,a,b,a,b\). We must compute \(t(O_{4,2})\), where \(t(O_{a,b})\) counts tilings of this octagon by unit-edge rhombi and unit squares. The implementations do not use a closed formula; instead they count tilings recursively by describing every remaining subregion only through its boundary.

Mathematical Approach

The key observation is that every tile edge lies in one of eight directions separated by \(45^\circ\). After scaling coordinates by \(2\), those directions become

$ (2,0),\ (\sqrt{2},\sqrt{2}),\ (0,2),\ (-\sqrt{2},\sqrt{2}),\ (-2,0),\ (-\sqrt{2},-\sqrt{2}),\ (0,-2),\ (\sqrt{2},-\sqrt{2}). $

Every coordinate can therefore be written as \(r+s\sqrt{2}\), which matches the algebraic representation used by the implementations.

Step 1: Encode the Region by an Eight-Direction Boundary Word

The initial octagon is encoded by the cyclic word

$ w_{a,b}=(\underbrace{0,\dots,0}_{a},\underbrace{1,\dots,1}_{b},\underbrace{2,\dots,2}_{a},\underbrace{3,\dots,3}_{b},\underbrace{4,\dots,4}_{a},\underbrace{5,\dots,5}_{b},\underbrace{6,\dots,6}_{a},\underbrace{7,\dots,7}_{b}). $

More generally, any remaining subregion is represented by the cyclic sequence of its unit boundary steps. If \(w\) is such a word, let \(T(w)\) denote the number of tilings of the region enclosed by \(w\).

Step 2: Choose a Canonical Boundary Edge

To avoid double counting, the recursion always selects the lowest boundary vertex, breaking ties by taking the leftmost one. Let that vertex be \(p\), and let the outgoing boundary edge from \(p\) have direction \(d\). In any valid tiling, exactly one tile uses that exposed boundary edge, so the recursion only needs to enumerate the possible tiles attached there.

Step 3: Only Three Local Tiles Are Possible

Let \(u\) be the unit vector in direction \(d\). The second side of the tile must turn into the interior by \(45^\circ\), \(90^\circ\), or \(135^\circ\). Therefore the only candidates use the unit vector in direction \(d+\delta \pmod 8\) with \(\delta\in\{1,2,3\}\), and their corners are

$ p,\qquad p+u,\qquad p+u+v,\qquad p+v. $

The case \(\delta=2\) gives a square; the cases \(\delta=1\) and \(\delta=3\) give the two rhombus orientations. No other convex unit-edge square or rhombus can share the chosen boundary edge and still lie inside the region.

Step 4: Enforce Geometric Validity

A candidate tile is accepted only when its two interior corners lie inside or on the current polygon and none of its four edges crosses an existing boundary edge, except for shared endpoints or the shared boundary edge itself. Cross products, segment tests, and vertex coordinates all stay inside the algebraic lattice generated by \(1\) and \(\sqrt{2}\), so the geometric tests follow the same exact combinatorial geometry as the tiles.

Step 5: Update the Boundary by Symmetric Difference

Write \(E(P)\) for the set of unit edges on the current boundary and \(E(Q)\) for the boundary of the chosen tile. When the tile is removed from the remaining region, shared edges disappear and newly exposed tile edges appear, so

$ E(P\setminus Q)=E(P)\triangle E(Q), $

where \(\triangle\) denotes symmetric difference. The resulting edge set is rebuilt into one or more counterclockwise boundary cycles by a deterministic walk: start from the lowest-leftmost unused edge and always take the smallest left turn. If the region splits into cycles \(w_1,\dots,w_r\), then the subproblems are independent and

$ T(w)=\sum_{Q} \prod_{i=1}^{r} T(w_i), $

with the empty boundary contributing \(1\).

Worked Example: \(O_{1,1}\)

For \(a=b=1\), the initial boundary word is

$ w_{1,1}=(0,1,2,3,4,5,6,7). $

The canonical starting vertex is the lowest-leftmost corner, and its outgoing boundary edge points east. The recursion therefore tests exactly three first tiles: one rhombus turning northeast, one square turning north, and one rhombus turning northwest. Summing all valid descendants gives

$ t(O_{1,1})=8, $

which matches one of the small checkpoint values used to validate the recurrence.

How the Code Works

The C++, Python, and Java implementations all follow the same recurrence. They build the initial boundary word for \(O_{4,2}\), expand it into vertices, choose the canonical lowest-leftmost start, try up to three candidate tiles, reject candidates that fail point-in-polygon or segment-intersection tests, and update the boundary through symmetric difference of unit edges. Every reconstructed cycle is oriented counterclockwise before memo lookup so that equivalent subregions share the same cache entry. The count is stored in arbitrary-precision integers, and the C++ implementation also checks small benchmark values such as \(t(O_{1,1})=8\), \(t(O_{2,1})=76\), and \(t(O_{3,2})=456572\).

Complexity Analysis

If a state has boundary length \(m\), then building its vertices, scanning for the canonical start, testing the three candidate tiles, checking segment intersections, and reconstructing the next boundary cycles each take linear time in \(m\). Thus one visited state costs \(O(m)\) time and \(O(m)\) temporary memory. The full search is still exponential in the worst case because the number of distinct boundary states can grow exponentially, but memoization, immediate geometric rejection, and decomposition into independent cycles reduce the practical search space sharply.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=594
2. Tiling problem: Wikipedia — Tiling problem
3. Quadratic integer: Wikipedia — Quadratic integer
4. Symmetric difference: Wikipedia — Symmetric difference
5. Point in polygon: Wikipedia — Point in polygon