Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 289: Eulerian Cycles

Project Euler Problem 289 Solution

EulerSolve provides an optimized solution for Project Euler Problem 289, Eulerian Cycles, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We must compute $L(6,10)\bmod 10^{10}$, where $L(m,n)$ counts Eulerian-cycle structures on the rectangular graph defined in the problem. A naive search is hopeless: each lattice vertex admits many local pairings, and those local choices must remain globally compatible until the very end. Mathematical Approach 1. Why a frontier state is sufficient Process the lattice vertices in a fixed sweep order, column by column and inside each column from bottom to top. After some prefix of vertices has been processed, every already-handled local port has degree $2$, so the processed subgraph is a disjoint union of paths and cycles. The only information that can still affect the future is how the unfinished paths touch the current cut. Label the boundary stubs by $0,1,\dots,B_v-1$. Each unfinished component hits the cut in exactly two stubs, so the entire past is encoded by a perfect matching $\sigma_v:\{0,\dots,B_v-1\}\to\{0,\dots,B_v-1\},\qquad \sigma_v(\sigma_v(i))=i,\ \sigma_v(i)\ne i.$ The code stores this matching as a partner array state[i] = \sigma_v(i) . No richer graph structure is required: once the partner of every open stub is known, the future can be processed exactly. 2. Local Euler constraints become local pairings A lattice point may be adjacent to one, two, or four unit cells....

Detailed mathematical approach

Problem Summary

We must compute $L(6,10)\bmod 10^{10}$, where $L(m,n)$ counts Eulerian-cycle structures on the rectangular graph defined in the problem. A naive search is hopeless: each lattice vertex admits many local pairings, and those local choices must remain globally compatible until the very end.

Mathematical Approach

1. Why a frontier state is sufficient

Process the lattice vertices in a fixed sweep order, column by column and inside each column from bottom to top. After some prefix of vertices has been processed, every already-handled local port has degree $2$, so the processed subgraph is a disjoint union of paths and cycles.

The only information that can still affect the future is how the unfinished paths touch the current cut. Label the boundary stubs by $0,1,\dots,B_v-1$. Each unfinished component hits the cut in exactly two stubs, so the entire past is encoded by a perfect matching

$\sigma_v:\{0,\dots,B_v-1\}\to\{0,\dots,B_v-1\},\qquad \sigma_v(\sigma_v(i))=i,\ \sigma_v(i)\ne i.$

The code stores this matching as a partner array state[i] = \sigma_v(i). No richer graph structure is required: once the partner of every open stub is known, the future can be processed exactly.

2. Local Euler constraints become local pairings

A lattice point may be adjacent to one, two, or four unit cells. Each adjacent cell contributes two local half-edges, so a corner vertex has $2$ active ports, an edge vertex has $4$, and an interior vertex has $8$. The port names in the implementation are

$E_L,E_U,N_R,N_L,W_U,W_L,S_L,S_R.$

Because an Eulerian cycle must use every local incidence exactly once, the active ports at one vertex must be partitioned into disjoint pairs. The number of perfect pairings on $2k$ labeled ports is

$ (2k-1)!!=\frac{(2k)!}{2^k k!}. $

Therefore the only local branching factors are

$2\text{ ports } \to 1,\qquad 4\text{ ports } \to 3,\qquad 8\text{ ports } \to 105.$

The program precomputes these pairing lists once in PairingCache.

3. How one local pair rewires the frontier

Suppose a local pairing joins labels $a$ and $b$. There are exactly three cases.

Old-old. Both labels already belong to the incoming frontier. If $\sigma(a)=b$, then this operation closes one component completely. Otherwise, if $\sigma(a)=p_a$ and $\sigma(b)=p_b$, removing $a$ and $b$ from the frontier forces $p_a$ and $p_b$ to become a new matched pair.

Old-new. If $a$ is old and $c$ is a newly created outgoing label, then the former partner $\sigma(a)$ is transferred to $c$.

New-new. Two outgoing labels are simply paired with each other.

This is exactly the logic implemented by apply_pair. After all local pairs are applied, the surviving outgoing labels are renumbered to form the next state $\sigma_{v+1}$.

4. Why premature cycles must be rejected

The target is one global Eulerian cycle, not several disconnected cycles. If a component closes before the final vertex, it no longer touches the frontier, so no later decision can merge it with the rest of the graph. Such a transition is therefore invalid.

Hence the dynamic program enforces:

$\text{for non-final vertices: } \texttt{closed}=0.$

At the very last vertex the opposite condition holds: we must finish with exactly one closure and no remaining frontier labels, i.e.

$\text{final acceptance: } \texttt{closed}=1 \text{ and } B_{\mathrm{final}}=0.$

5. Transfer-matrix recurrence

Let $D_v(\sigma)$ be the number of valid partial constructions after processing the first $v$ sweep positions and ending in frontier state $\sigma$. For the next vertex, define $T_v(\sigma,\sigma')$ as the number of local pairings that transform $\sigma$ into $\sigma'$ without creating an illegal premature cycle. Then

$D_{v+1}(\sigma')=\sum_{\sigma} D_v(\sigma)\,T_v(\sigma,\sigma') \pmod{10^{10}}.$

This is a standard transfer-matrix / frontier-DP recurrence, but the state is not merely a bitmask: it is a matching on the cut, because connectivity matters.

6. Why the boundary bookkeeping in the code works

The implementation rotates the rectangle so that $n \le m$. This does not change $L(m,n)$, but it minimizes the frontier width and therefore the number of states.

The arrays row_wires and prefix count how many old labels lie to the right of the current row, how many belong to the bottom slice, and how many belong to the left slice. From these counts the code can build, in $O(1)$ per vertex, the exact map

$\text{old labels} \longrightarrow \text{new labels after removing consumed ports and inserting outgoing ports}.$

That is why the expensive part of the algorithm is the number of frontier states, not geometric bookkeeping.

7. Small checks and worked examples

The program validates several small instances before computing the target:

$L(1,1)=1,\qquad L(1,2)=2,\qquad L(2,2)=37,\qquad L(3,3)=104290.$

The first case is easy to visualize: a single cell forces one Eulerian cycle. The second case already shows why the DP is necessary: even a $1\times2$ strip has multiple globally valid ways to wire the local pairings into a single cycle.

How the Code Works

The code precomputes all perfect pairings of size $2$, $4$, and $8$, then sweeps through the $(m+1)(n+1)$ lattice vertices. For each vertex it builds a VertexContext, iterates over all current states, applies every valid local pairing through process_state, and accumulates counts modulo $10^{10}$ in the next hash map. Large DP layers may optionally be split across threads, but the mathematics is entirely the frontier-matching recurrence above.

Complexity Analysis

If $S_w$ denotes the number of reachable frontier matchings for width $w=\min(m,n)$, then the total running time is roughly

$O\big((m+1)(n+1)\cdot S_w \cdot 105\big),$

because each vertex tests at most $105$ local pairings per state. Memory usage is $O(S_w)$. The exponential difficulty is entirely concentrated in $S_w$, which is why rotating the rectangle to keep the smaller dimension as the width is crucial.