Mains

This article walks through the minimum spanning tree puzzle, explains why the greedy rule actually gives a perfect answer every time, and shows how to read the board, lay cable without wasting money, and handle the tricky maps where a long cable turns out to be right.

What the board shows you

A set of green dots sits on the map. Each dot is a village. Faint lines run between some of them, and each line has a price tag sitting at its midpoint. Those lines are cables you could lay, and the number is what that cable costs.

Your job is to connect every village to every other village for as little total cable as possible. Villages do not all need a direct link. If village A connects to village B, and village B connects to village C, then A can reach C through B. That indirect reach is the whole reason the puzzle is cheap rather than expensive.

A counter at the top tracks how many villages are joined so far, how much cable you have laid, and what the cheapest possible total is. That cheapest figure is not a rough target. It is the exact answer, worked out before you start.

Controls and board sizes

Tap or click a cable line to lay it. Tap the same line again to pick it back up. Picking up cable is free and instant. Only what is down at the end counts toward your total.

A dropdown labelled Region lets you pick the map size. Small gives you six villages. Medium gives you eight. Large gives you ten. More villages means more possible cables and more choices to sift through, but the method stays the same.

Press New game to get a fresh map at whatever size you have chosen. The villages move, the cables change, and the prices change with them.

The rule that solves everything

Sort every cable by price. Lay the cheapest one. Then lay the next cheapest. Keep going. If a cable would connect two villages that are already connected to each other by some route through the network, skip it, because it adds cost and nothing else. The board will refuse it for you.

That is the entire method. It sounds too simple to be perfect, but it is. Joseph Kruskal proved in 1956 that this greedy approach gives the cheapest possible network every single time. The proof works by an exchange argument. Suppose some other network were cheaper. Adding any cable the greedy rule chose creates a loop, and some cable on that loop must cost at least as much. Swap them and the total does not go up. Repeat until the two networks are the same. There is no cheaper answer hiding anywhere.

Why loops are blocked, not penalised

When you try to lay a cable between two villages that already have a path linking them, the board stops you and explains why. It does not let you pay extra for nothing. This is a guard rail, not a punishment.

The reason loops are never useful is simple. A network that joins N villages needs exactly N minus one cables. Six villages need five cables. Ten need nine. Any more than that and you have paid for a cable that carries no new connection. Since every cable has a positive cost, adding a loop always makes the total worse.

Reading the prices before you start

Before you lay anything, scan the numbers. The cheapest cable on the board is always safe to take. It will be part of every optimal network when all prices are different. So start there.

Then look at the second cheapest. If it does not connect two villages that the first cable already joins, lay it too. Work through the price list in order. Most of the time you will lay cables without a single refusal, because the cheap ones tend to be short and short cables rarely form loops.

On a small board this takes a few seconds. On a large board with eighteen or twenty cables, it helps to mentally sort them before you begin tapping. Find the three or four cheapest, lay those, then scan for the next tier.

When a long cable is the right call

A village sitting off on its own, far from everything else, will only be reachable by one or two cables. If only one cable reaches it, that cable is in the answer no matter what it costs. There is no choice involved. You pay it or the village stays disconnected.

This is the one place beginners hesitate. A cable costing twelve looks wrong when every other cable on the board costs three or four. But price only matters when you have options. A village with a single cable has none. Lay it and move on.

On larger boards you sometimes see two cables reaching a remote village, one costing nine and one costing eleven. The greedy rule handles this perfectly. You will reach the nine before the eleven, so the nine gets laid and the eleven is skipped. No special thinking required.

The same logic applies to clusters. Two villages huddled together in a corner might share a cheap cable between them and then need one expensive cable back to the main group. Both of those cables are in the answer. The cheap one joins the pair, and the expensive one joins the pair to everyone else.

Common mistakes and how to sidestep them

• Starting with the cable nearest to the centre instead of the cheapest one. Position on the map has nothing to do with price. Always sort by number, not by geography.
• Trying to build a neat star or ring shape. The cheapest network looks messy. It has no pattern. Let the prices decide the shape.
• Forgetting that you can pick cables back up. If you laid one by accident or want to try a different approach, tap it again. Only the final layout is scored.
• Assuming every cable will be used. On a medium board with maybe fourteen cables and eight villages, only seven will be in the answer. Half the cables on the board exist only to tempt you.
• Ignoring the refusal message. When the board says two villages are already connected, that is useful information. It tells you the network has already grown past that pair, and you can stop thinking about them.

A worked example on a small board

Six villages, nine possible cables. The prices are 2, 3, 3, 4, 5, 6, 7, 8, and 10. You need five cables.

Start with the 2. Then the first 3. Then the second 3. Then the 4. Four cables laid, five villages joined. The 5 would close a loop, so the board refuses it. The 6 reaches the last village. Five cables, total cost 18. That matches the cheapest figure shown at the top.

Notice that the 5, 7, 8, and 10 were never touched. Four cables out of nine served no purpose except to make the puzzle look harder than it is. The board avoids having too many cables with equal prices, so the sorting step is nearly always clear cut. When two cables share a price, either one works, and the total stays the same.

Why this puzzle is rare

Most problems about choosing a cheapest set of items are genuinely hard. The travelling salesman, the knapsack, the set cover - all of them resist the greedy approach. Taking the cheapest option at each step gives a good answer, but not the best one.

Connecting a network is different. It belongs to a family of problems called matroids, where the greedy rule is guaranteed to find the optimal answer. Matroids are much rarer than people expect, which is why this puzzle feels surprising. You expect to need clever thinking, backtracking, or trial and error. You need none of those things. The dumbest possible strategy - cheapest first, skip loops - is the smartest one.

Everything stays on your own machine

The map, the cables, the prices, and the optimal answer are all worked out inside your browser. No part of the puzzle is sent to a server. There is no account, no login, and no data leaving your device. Your best score is kept in local storage on the machine you are using, and clearing the browser data removes it.

You can test this by loading the page, turning off your network connection, and pressing New game. A fresh map appears, the optimal total is computed, and everything works exactly as before. The server was never involved.