Detailed mathematical approach

Problem Summary

Let \(F(n)\) denote the number of valid migrations on an \(n \times n\) grid. Every cell initially contains one ant, every ant must move to a neighboring cell, every cell must receive exactly one ant, and two ants are not allowed to traverse the same undirected edge in opposite directions. In graph terms, each vertex has out-degree \(1\) and in-degree \(1\), so a valid migration is a disjoint union of directed cycles, with 2-cycles forbidden.

Mathematical Approach

Step 1: Convert the migration into two perfect matchings

Color the grid as a checkerboard, with black and white cells. Every legal move goes from one color to the other, because adjacent cells always have opposite parity. Split the directed edges of a migration into two sets:

$M_1=\{\text{moves from black to white}\},\qquad M_2=\{\text{moves from white to black}\}.$

Now inspect \(M_1\). Every black vertex has exactly one outgoing move, so every black cell is incident to exactly one edge of \(M_1\). Every white vertex has exactly one incoming move, and the only possible source is a black neighbor, so every white cell is also incident to exactly one edge of \(M_1\). Therefore \(M_1\) is a perfect matching of the bipartite grid graph. By the same argument, \(M_2\) is another perfect matching.

The forbidden “swap positions across one edge” condition says that the two matchings may not use the same undirected edge. Hence valid migrations are in bijection with ordered pairs \((M_1,M_2)\) of edge-disjoint perfect matchings. This is the central reformulation used by all three solution files.

Step 2: Immediate parity consequence

If \(n\) is odd, the checkerboard coloring contains different numbers of black and white cells, namely

$\left\lceil\frac{n^2}{2}\right\rceil \neq \left\lfloor\frac{n^2}{2}\right\rfloor.$

A perfect matching in a bipartite graph requires both color classes to have equal size, so for odd \(n\) no perfect matching exists at all. Therefore

$F(n)=0\qquad\text{for odd }n.$

This matches the checkpoint logic in the C++ program, where the brute-force verification for \(n=3\) agrees with the DP result \(F(3)=0\).

Step 3: Describe one row by a profile state

The implementations process the board row by row. For one matching layer, consider a fixed row \(r\). Some cells in that row may already be matched vertically to row \(r-1\); the code records those columns by a bitmask \(in\). If bit \(c\) is set, then cell \((r,c)\) is already occupied in that matching layer and needs no new decision inside the current row.

For Problem 393 we must track two matching layers simultaneously, so the state is a pair \((in_1,in_2)\). The code packs it into one integer:

$state = in_1 + (in_2 \ll n).$

Here \(in_1\) belongs to the black-to-white matching and \(in_2\) to the white-to-black matching. At the end of the row we obtain two new masks \((out_1,out_2)\), representing vertical edges that continue downward into row \(r+1\).

Step 4: Local choices for one cell

Inside one matching layer, an unoccupied cell has only two possible ways to be matched while scanning left to right:

$\text{horizontal to }(r,c+1)\qquad\text{or}\qquad \text{vertical to }(r+1,c).$

If the cell is already covered by an incoming vertical edge from above, the only option is “filled”. On the last row, vertical placement is impossible because there is no row below.

This is exactly what the helper options_for_cell returns in C++, Python, and Java: Filled, Horizontal, or Vertical, together with the bit updates needed for the current occupancy mask and for the outgoing mask.

Step 5: Why only two conflict checks are needed

Within one matching layer, the occupancy mask already guarantees that each cell is used exactly once. Across the two layers, the only forbidden situation is reusing the same undirected edge, because that would mean the two directed matchings traverse it in opposite directions. For the current column \(c\), that can happen in exactly two ways:

$\text{both layers choose the same horizontal edge }(r,c)\text{--}(r,c+1),$

$\text{both layers choose the same vertical edge }(r,c)\text{--}(r+1,c).$

That is why the DFS rejects only the pairs (Horizontal, Horizontal) and (Vertical, Vertical) at the same column. No other cross-layer test is necessary.

Step 6: Transfer recurrence

For fixed input masks \((in_1,in_2)\) and a flag telling us whether we are on the last row, the depth-first search enumerates every legal filling of that row and counts how many of them lead to each output pair \((out_1,out_2)\). Let

$T_{\mathrm{last}}((in_1,in_2)\to(out_1,out_2))$

be that multiplicity. Then the row DP is

$\mathrm{DP}_{r+1}(out_1,out_2)=\sum_{in_1,in_2}\mathrm{DP}_r(in_1,in_2)\,T_{\mathrm{last}(r)}((in_1,in_2)\to(out_1,out_2)).$

The initial condition is

$\mathrm{DP}_0(0,0)=1,$

because before the first row there are no pending vertical edges. The final answer is

$F(n)=\mathrm{DP}_n(0,0),$

because after the last row there must again be no unfinished vertical edges.

Worked Example: \(n=2\)

The \(2 \times 2\) grid has exactly two perfect matchings: the two horizontal edges, or the two vertical edges. Since the two layers must be edge-disjoint, one layer must choose the horizontal matching and the other must choose the vertical matching. The pair is ordered, so we get two possibilities:

$F(2)=2.$

These are precisely the clockwise and counterclockwise 4-cycles around the square, and they match the checkpoint f(2)=2 in the repository code.

How the Code Works

The C++ solution keeps dp as unordered_map<int, BigInt>, where the key is the packed profile state and the value is the number of ways to reach it. The cache transition_cache_ stores the previously computed transition list for a triple \((in_1,in_2,last\_row)\). The Python version uses ordinary dictionaries and Python's arbitrary-precision integers, while the Java version mirrors the same structure with HashMap, explicit Transition objects, and BigInteger.

The C++ file also contains internal validation: it checks \(F(2)=2\), \(F(4)=88\), and compares the DP against brute force for \(n=3\). For the actual Project Euler input \(n=10\), the implementations return

$112398351350823112.$

Complexity Analysis

The profile space is a subset

$\mathcal{S}\subseteq \{0,1\}^n \times \{0,1\}^n,$

so there are at most \(2^{2n}\) combined masks. Building one uncached transition map is itself exponential in \(n\), because the DFS explores all legal row fillings for the two coupled matching layers. However, each profile \((in_1,in_2,last\_row)\) is solved only once and then reused whenever it reappears in the outer DP. Thus the algorithm is exponential in the board width, but only linear in the number of rows after transition reuse. Memory usage is also exponential in \(n\), dominated by the DP frontier and the cached transition tables. That is still practical for \(n=10\), while direct enumeration over all neighbor choices would be completely infeasible.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=393
2. Perfect matching: Wikipedia — Perfect matching
3. Bipartite graph: Wikipedia — Bipartite graph
4. Profile dynamic programming / transfer matrix patterns: cp-algorithms — Dynamic Programming on Broken Profile
5. Repository implementations used as source of truth: solutionsCpp/Euler393.cpp, solutionsPython/Euler393.py, solutionsJava/Euler393.java.