Project Euler

Migrating Ants

An n x n grid of squares contains n^2 ants, one ant per square. All ants decide to move simultaneously to an adjacent square (up, down, left, or right). We define f(n) to be the number of ways this...

Source sync Apr 19, 2026

Problem #0393

Level Level 16

Solved By 892

Languages C++, Python

Answer 112398351350823112

Length 408 words

dynamic_programminggeometrygraph

An $n \times n$ grid of squares contains $n^2$ ants, one ant per square.

All ants decide to move simultaneously to an adjacent square (usually $4$ possibilities, except for ants on the edge of the grid or at the corners).

We define $f(n)$ to be the number of ways this can happen without any ants ending on the same square and without any two ants crossing the same edge between two squares.

You are given that $f(4) = 88$.

Find $f(10)$.

Problem 393: Migrating Ants

Mathematical Analysis

Each valid configuration is a permutation $\sigma$ on the $n^2$ cells where:

$\sigma(v)$ is adjacent to $v$ for every cell $v$ (each ant moves to a neighbor).
The permutation is a bijection (no two ants land on the same cell).
No two ants cross the same edge: if $\sigma(u) = v$ , then $\sigma(v) \neq u$ (no 2-cycles/swaps).

Such a permutation decomposes into directed cycles of length $\geq 3$ , each using only grid-adjacent edges. Since every cycle has even length on a bipartite graph (the grid is bipartite under checkerboard coloring), the total number of cells $n^2$ must be even. Therefore $f(n) = 0$ for all odd $n$ .

Editorial

We use profile dynamic programming, processing the grid row by row. State representation.* The boundary between consecutive rows is encoded as a vector of length $n$ . At each column $j$ , the vertical flow takes one of three values. We $(0, 0)$ : no vertical movement at column $j$ . We then $(1, 0)$ : an ant moves downward across this boundary. Finally, $(0, 1)$ : an ant moves upward across this boundary.

Pseudocode

$(0, 0)$: no vertical movement at column $j$
$(1, 0)$: an ant moves downward across this boundary
$(0, 1)$: an ant moves upward across this boundary
Each cell has exactly 1 incoming and 1 outgoing direction
No horizontal swap: if an ant moves right from column $j$ to $j+1$, the ant at column $j+1$ cannot simultaneously move left to column $j$
Boundary conditions: no leftward/rightward movement off the grid edges

Proof of Correctness

The DP exactly enumerates all valid configurations:

Completeness: Every valid permutation assigns each cell one incoming and one outgoing adjacent direction. The row-by-row processing with column-by-column enumeration considers all such assignments.
Soundness: The three constraints (bijection, adjacency, no crossing) are enforced by: (a) the flow-conservation equations $\text{incoming} = \text{outgoing} = 1$ per cell, (b) restricting moves to grid neighbors, and (c) forbidding $(d=1, u=1)$ vertically and $(r=1, l=1)$ horizontally.
No overcounting: Each configuration corresponds to a unique sequence of boundary states, so it is counted exactly once.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

States per row boundary: $3^n$ .
Transitions per row: For each boundary state, the column-by-column DP runs in $O(n \cdot C)$ time where $C$ is the (small, bounded) number of choices per cell.
Total time: $O(n \cdot 3^n \cdot n \cdot C) = O(n^2 \cdot 3^n)$ .
Space: $O(3^n)$ for the DP table.
For $n = 10$ : $3^{10} = 59049$ states, computed in a few seconds.

Answer

\boxed{112398351350823112}

C++ project_euler/problem_393/solution.cpp

#include <bits/stdc++.h>
using namespace std;

// Problem 393: Migrating Ants
// Profile DP, row by row, 3 states per column (no vertical swap).
// State encoded in base 3, 3^n possible boundary states.

typedef long long ll;
typedef unordered_map<int, ll> State;

int N;
int pow3[11];

// Decode top state at column j: 0->(0,0), 1->(0,1), 2->(1,0)
pair<int,int> decode(int state, int j) {
    int v = (state / pow3[j]) % 3;
    if (v == 0) return {0, 0};
    if (v == 1) return {0, 1};
    return {1, 0};
}

int encode_bot(int bot_d, int bot_u) {
    if (bot_d == 0 && bot_u == 0) return 0;
    if (bot_d == 0 && bot_u == 1) return 1;
    return 2; // bot_d=1, bot_u=0
}

// Process one row given top boundary state, return map of bottom state -> count
State process_row(int top_state, bool is_last) {
    // Column-by-column DP
    // Key: (r_out, from_right, bot_int) packed as single int
    // r_out and from_right are each 0 or 1, bot_int < 3^N
    // Pack as: bot_int * 4 + r_out * 2 + from_right
    unordered_map<int, ll> dp, new_dp;

    auto pack = [](int r_out, int from_right, int bot_int) {
        return bot_int * 4 + r_out * 2 + from_right;
    };

    // Column 0
    auto [td0, tu0] = decode(top_state, 0);
    int S_in = 1 - td0;
    int S_out = 1 - tu0;
    if (S_in >= 0 && S_in <= 1 && S_out >= 0 && S_out <= 1) {
        // in_choices: (bot_u, from_right) summing to S_in
        // out_choices: (bot_d, r_out) summing to S_out
        vector<pair<int,int>> in_ch, out_ch;
        if (S_in == 0) in_ch = {{0,0}};
        else in_ch = {{0,1},{1,0}};
        if (S_out == 0) out_ch = {{0,0}};
        else out_ch = {{0,1},{1,0}};

        for (auto [bot_u, from_right] : in_ch) {
            for (auto [bot_d, r_out] : out_ch) {
                if (is_last && (bot_d || bot_u)) continue;
                if (bot_d && bot_u) continue;
                if (r_out && from_right) continue;
                int bv = encode_bot(bot_d, bot_u);
                dp[pack(r_out, from_right, bv)] += 1;
            }
        }
    }

    for (int j = 1; j < N; j++) {
        new_dp.clear();
        auto [td_j, tu_j] = decode(top_state, j);
        for (auto& [key, cnt] : dp) {
            int r_in = (key >> 1) & 1;
            int l_demand = key & 1;
            int bot_int = key >> 2;
            if (r_in && l_demand) continue;
            int si = 1 - td_j - r_in;
            int so = 1 - tu_j - l_demand;
            if (si < 0 || si > 1 || so < 0 || so > 1) continue;

            vector<pair<int,int>> in_ch, out_ch;
            if (si == 0) in_ch = {{0,0}};
            else in_ch = {{0,1},{1,0}};
            if (so == 0) out_ch = {{0,0}};
            else out_ch = {{0,1},{1,0}};

            for (auto [bot_u, from_right] : in_ch) {
                for (auto [bot_d, r_out] : out_ch) {
                    if (is_last && (bot_d || bot_u)) continue;
                    if (bot_d && bot_u) continue;
                    if (j == N - 1 && (r_out || from_right)) continue;
                    if (r_out && from_right) continue;
                    int bv = encode_bot(bot_d, bot_u);
                    int new_bot = bot_int + bv * pow3[j];
                    new_dp[pack(r_out, from_right, new_bot)] += cnt;
                }
            }
        }
        swap(dp, new_dp);
    }

    State result;
    for (auto& [key, cnt] : dp) {
        int bot_int = key >> 2;
        result[bot_int] += cnt;
    }
    return result;
}

ll solve(int n) {
    N = n;
    pow3[0] = 1;
    for (int i = 1; i <= n; i++) pow3[i] = pow3[i-1] * 3;

    State dp;
    dp[0] = 1;

    for (int row = 0; row < n; row++) {
        bool is_last = (row == n - 1);
        State new_dp;
        for (auto& [top_int, cnt] : dp) {
            State transitions = process_row(top_int, is_last);
            for (auto& [bot_int, ways] : transitions) {
                new_dp[bot_int] += ways * cnt;
            }
        }
        dp = new_dp;
    }
    return dp.count(0) ? dp[0] : 0;
}

int main() {
    // Verify
    assert(solve(2) == 2);
    assert(solve(4) == 88);

    // Compute f(10)
    ll ans = solve(10);
    cout << ans << endl;
    return 0;
}

Python project_euler/problem_393/solution.py

"""
Problem 393: Migrating Ants
An n x n grid of squares contains n^2 ants, one ant per square.
All ants simultaneously move to an adjacent square (up/down/left/right).
f(n) counts configurations where no two ants end on the same square
and no two ants cross the same edge. Given f(4) = 88, find f(10).
"""

import time

def f(n):
    """
    Compute f(n) using profile dynamic programming, processing the grid
    row by row and within each row column by column.

    State between rows: for each column j, encode the vertical flow:
      (d, u) where d=1 if an ant moves down, u=1 if an ant moves up.
      The no-crossing constraint forbids (d=1, u=1) at any column,
      leaving 3 valid states per column: (0,0), (0,1), (1,0).

    Within each row, process columns left to right tracking horizontal
    flow. The no-crossing constraint also forbids simultaneous left and
    right flow at any column boundary (horizontal swap).

    For each cell, exactly one ant arrives and one ant departs. We enforce:
      incoming = top_down + from_left + bottom_up + from_right = 1
      outgoing = top_up + to_left + bottom_down + to_right = 1
    """

    def process_row(n, top_state_int, is_last_row):
        """Given the vertical flow state above this row, compute all valid
        bottom-boundary states and their counts."""
        top = []
        ts = top_state_int
        for j in range(n):
            val = ts % 3
            if val == 0:
                top.append((0, 0))
            elif val == 1:
                top.append((0, 1))
            else:
                top.append((1, 0))
            ts //= 3

        # Column-by-column DP. State: (r_out, from_right, bot_int)
        # r_out: 1 if this cell sends its ant right
        # from_right: 1 if this cell declared incoming from right (demands
        #   the next column to send its ant left)
        dp = {}

        # Process column 0
        td, tu = top[0]
        S_in = 1 - td
        S_out = 1 - tu
        if 0 <= S_in <= 1 and 0 <= S_out <= 1:
            in_choices = [(0, 0)] if S_in == 0 else [(0, 1), (1, 0)]
            out_choices = [(0, 0)] if S_out == 0 else [(0, 1), (1, 0)]
            for bot_u, from_right in in_choices:
                for bot_d, r_out in out_choices:
                    if is_last_row and (bot_d or bot_u):
                        continue
                    if bot_d and bot_u:  # no vertical swap
                        continue
                    if r_out and from_right:  # no horizontal swap
                        continue
                    bv = 0 if (bot_d == 0 and bot_u == 0) else (1 if bot_u else 2)
                    key = (r_out, from_right, bv)
                    dp[key] = dp.get(key, 0) + 1

        # Process columns 1..n-1
        pow3 = [3 ** j for j in range(n)]
        for j in range(1, n):
            new_dp = {}
            td_j, tu_j = top[j]
            for (r_in_j, l_demand_j, bot_int), cnt in dp.items():
                if r_in_j and l_demand_j:  # horizontal swap forbidden
                    continue
                S_in = 1 - td_j - r_in_j
                S_out = 1 - tu_j - l_demand_j
                if S_in < 0 or S_in > 1 or S_out < 0 or S_out > 1:
                    continue
                in_choices = [(0, 0)] if S_in == 0 else [(0, 1), (1, 0)]
                out_choices = [(0, 0)] if S_out == 0 else [(0, 1), (1, 0)]
                for bot_u, from_right in in_choices:
                    for bot_d, r_out in out_choices:
                        if is_last_row and (bot_d or bot_u):
                            continue
                        if bot_d and bot_u:
                            continue
                        if j == n - 1 and (r_out or from_right):
                            continue
                        if r_out and from_right:
                            continue
                        bv = 0 if (bot_d == 0 and bot_u == 0) else (1 if bot_u else 2)
                        new_bot = bot_int + bv * pow3[j]
                        key = (r_out, from_right, new_bot)
                        new_dp[key] = new_dp.get(key, 0) + cnt
            dp = new_dp

        result = {}
        for (_, _, bot_int), cnt in dp.items():
            result[bot_int] = result.get(bot_int, 0) + cnt
        return result

    zero_state = 0
    dp = {zero_state: 1}
    for row in range(n):
        is_last = (row == n - 1)
        new_dp = {}
        for top_int, cnt in dp.items():
            transitions = process_row(n, top_int, is_last)
            for bot_int, ways in transitions.items():
                new_dp[bot_int] = new_dp.get(bot_int, 0) + ways * cnt
        dp = new_dp
    return dp.get(zero_state, 0)

# Verify with known values
assert f(2) == 2, f"f(2) = {f(2)}, expected 2"
assert f(4) == 88, f"f(4) = {f(4)}, expected 88"

# Compute f(10)
t0 = time.time()
answer = f(10)
elapsed = time.time() - t0
print(f"f(10) = {answer}")
print(f"Computed in {elapsed:.2f}s")
assert answer == 112398351350823112