The Math Behind Netwalk — Graph Theory & Spanning Trees Explained

May 26, 2026 · 6 min read

Every Netwalk board you've ever played — every 5×5, every 25×25 marathon, every Daily Puzzle — was born from a single mathematical guarantee: this puzzle has a solution. That guarantee comes from graph theory, specifically from something called a spanning tree. Let's unpack how it works.

The Board as a Graph

In mathematics, a graph is a set of points (vertices) connected by lines (edges). A Netwalk board is a grid graph: each tile is a vertex, and each shared border between adjacent tiles is a potential edge.

A 5×5 board has 25 vertices. If every adjacent pair of tiles were connected, you'd have 40 edges (20 horizontal + 20 vertical). But Netwalk doesn't connect everything — it connects just enough to form a spanning tree.

A spanning tree is a subset of edges that:

Connects every vertex — you can reach any tile from any other tile by following pipes.
Has no cycles — there's exactly one path between any two tiles. No redundant loops.
Uses exactly (V - 1) edges — for 25 vertices, exactly 24 connected edges.

When all tiles are correctly rotated in Netwalk, the connected pipes form a spanning tree rooted at the server. Every node has a single, unambiguous path back to the orange hub.

Prim's Algorithm: How Netwalk Boards Are Born

Netwalk uses Prim's algorithm to generate every board. Named after computer scientist Robert C. Prim (1957), it's one of the classic algorithms for finding a minimum spanning tree in a weighted graph. In Netwalk's case, all edge weights are equal (or randomized), so it produces a random spanning tree.

Here's how it works inside the game:

Pick a starting tile at random — this becomes the server. Mark it "visited."
Build a frontier — collect all unvisited tiles adjacent to visited tiles. These are candidates for connection.
Pick a random frontier edge — connect the visited tile to the unvisited one. Mark the new tile visited.
Expand the frontier — the newly visited tile brings its unvisited neighbors into the candidate pool.
Repeat until every tile is visited.

This guarantees a single connected component with no cycles — a puzzle that is always solvable. The algorithm runs in O(E log V) time, where E is the number of possible edges and V is the number of tiles. Even on a 25×25 board (625 tiles, ~1,200 possible edges), it finishes in milliseconds.

Extra Edges: Making Puzzles Interesting

A pure spanning tree would make for a trivially easy puzzle. With only one path between any two tiles, every pipe orientation would be forced — there'd be no ambiguity, no challenge.

So Netwalk adds extra edges — random additional connections beyond the spanning tree. An extra edge creates a cycle: two different paths between the same two points. This introduces ambiguity: a tile might connect correctly in more than one way, but only one orientation leads to all tiles being connected to the server.

The extra edge probability scales with grid size:

Small grids (5×5): ~12% chance per possible edge
Medium grids (7×7–9×9): ~8%
Large grids (12×12–15×15): ~5%
Huge grids (20×20+): ~3%

Larger grids need fewer extra edges proportionally because the base spanning tree already provides enough complexity. Too many extra edges on a 25×25 board would make the puzzle chaotic, not challenging.

Why Every Rotation Matters: The Bitmask Encoding

Each tile's pipe configuration is stored as a 4-bit integer — one bit per direction (North=1, East=2, South=4, West=8). These combine via bitwise OR:

A straight vertical pipe: N | S = 1 | 4 = 5
A horizontal pipe: E | W = 2 | 8 = 10
An L-shaped bend (NE): 1 | 2 = 3
A T-junction (N-E-S): 1 | 2 | 4 = 7
A cross (+): 1 | 2 | 4 | 8 = 15

When you click a tile, the game rotates this bitmask 90° clockwise: North becomes East, East becomes South, etc. Mathematically, this is a left bit-shift with wrap-around: ((mask << 1) & 15) | ((mask >> 3) & 1). Four clicks bring it full circle — literally.

Flood Fill: How the Game Knows You've Won

Every time you rotate a tile, the game runs a flood fill (also called graph traversal or BFS/DFS) starting from the server. It follows connected pipes outward, marking every reachable tile. If every non-empty tile is reachable, you win.

The algorithm:

Start at the server. Mark it visited.
Check all four neighbors. If a neighbor has a pipe facing the server AND the server's tile has a pipe facing the neighbor, the connection is valid. Mark the neighbor visited and add it to the stack.
Recursively explore from each newly visited tile.
When no more tiles can be reached, count visited tiles. If count equals total non-empty tiles, all nodes are connected.

This runs on every click. For a 25×25 board, that's 625 tiles to check — and it completes in under a millisecond. The cyan glow you see on connected tiles is the flood fill result, rendered in real time.

Locked Tiles and the Entropy of a Puzzle

Each puzzle starts with all non-locked tiles rotated randomly (0-3 steps from correct). The "entropy" of a starting position — how scrambled it is — affects solve difficulty independently of grid size.

Locked tiles reduce entropy by pinning down correct orientations in specific locations. A board with 18% locked tiles has significantly less ambiguity than one with 0%. They're the game's way of giving you footholds — guaranteed correct positions to build from.

The actual challenge of a puzzle comes from the interaction between:

Grid size — more tiles = more rotations to find
Extra edges — more ambiguity = harder to deduce correct orientations
Locked tiles — more anchors = easier deduction
Starting rotations — how far each tile is from correct

This is why no two Netwalk puzzles feel the same, even on the same grid size.

The Daily Puzzle: Deterministic Randomness

The Daily Puzzle uses today's date (e.g., "2026-05-26") as a seed for a pseudorandom number generator. Same seed → same sequence of "random" numbers → identical board for everyone. The algorithm is deterministic: given the same input, you always get the same output.

This means every player on Earth sees the same puzzle on the same day. Compare solve times with friends, or just enjoy knowing thousands of people are untangling the exact same network you are. The seed changes at midnight, and a fresh board appears.

Why This Matters (Even If You're Not a Mathematician)

You don't need to understand graph theory to enjoy Netwalk. But knowing the underlying structure gives you an edge:

The spanning tree guarantee means there is always a solution. No guessing whether a board is broken.
Cycles from extra edges mean sometimes a tile can face two ways and still connect locally — but only one way connects everything. When stuck, look for the path that reaches the most tiles.
The flood fill's real-time feedback means you're never in the dark. If a tile doesn't glow, backtrack and fix the chain.

Ready to play with math on your side? Play Netwalk now →