The Math Behind Netwalk —Graph Theory & Spanning Trees Explained

May 26, 2026 · 6 min read

Updated September 17, 2026: clarified game-mode rules, win validation and the limits of seeded generation.

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 bounded 5×5 board has 25 vertices and 40 possible neighbor edges (20 horizontal and 20 vertical). The generator first connects just enough edges to form a spanning tree. A Torus board also permits neighbors across opposite boundaries, so its available edge set is different.

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.

Bounded and Torus preserve that tree: a valid solved board has exactly one path between any pair of tiles. Classic starts with a tree but can add edges and allow cycles. A unique path within a solved tree does not prove that a scrambled board has only one valid solution.

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:

Choose the server: Classic uses a random starting tile; Bounded and Torus use the center. 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.

Tree growth yields one connected component without cycles. Preserving those edges gives a valid stored solution. This implementation selects and removes entries from a frontier array; it is not the priority-queue implementation of weighted Prim's algorithm, so the usual O(E log V) bound should not be attributed to this code.

Classic Adds Edges; Bounded and Torus Keep a Tree

A spanning tree is not automatically an easy puzzle. The solved graph has one path between any pair of vertices, but the player sees rotated pieces rather than that graph. Local choices may stay ambiguous for many moves. This implementation does not test uniqueness or grade boards by the deductions required.

Only Classic adds extra edges after tree generation. Adding a previously absent edge creates a cycle. Bounded, Torus and the Daily puzzle do not add these edges. This distinction matters when solving: a closed loop rules out a Bounded or Torus candidate, but does not by itself invalidate a Classic board.

Classic attempts extra connections with probabilities based on the total number of cells:

Up to 25 cells: 12% per candidate edge
26–81 cells: 8%
82–225 cells: 5%
More than 225 cells: 3%

These are generator settings, not measured difficulty ratings. Some candidate edges already exist in the tree, so a successful random check does not always add a new connection. The settings do not establish a unique solution or a required solve time.

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 from the server. It follows reciprocal pipe connections, marking reachable tiles. Connectivity is necessary but not sufficient to win: every opening must match its neighbor, and Bounded and Torus also reject cycles.

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.

For a 25×25 board there are 625 tiles to inspect. The cyan glow shows current reachability, not proof that a tile has its final orientation. A connected board with an unmatched opening still fails validation. See the board-generation and validation walkthrough for the separate checks.

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.

Classic samples each tile for locking with an 18% probability, so an individual board does not necessarily have exactly 18% locked tiles. These clues retain their generated orientations. Bounded, Torus and Daily have no generated locks. A clue narrows local choices, but we do not measure difficulty or mathematical entropy from the lock count.

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.

Players using the same UTC date, board size and game version receive the same Daily board. Daily uses Bounded rules. The default date rolls over at midnight UTC; opening or restarting Daily selects that date. To compare results, agree on the date, size and version first. Read the Daily seeds and fair-score guide for the limits of reproducibility.

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:

Preserving the generated connections gives at least one solution. That construction does not guarantee uniqueness.
Apply the rules of your mode: all openings must match; Bounded and Torus also require a tree, while Classic permits cycles.
Use the glow as reachability feedback, then inspect boundaries and unmatched openings. Connecting more tiles temporarily is not always progress toward a valid solution.

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