Hex

Hex is played on a rhombus of hexagons. Two players take turns coloring a cell — one wants to build an unbroken chain of their color connecting the left and right sides, the other wants to connect top and bottom. The first to bridge their two sides wins.

That's the whole game. Yet from those two rules springs a small miracle: a Hex board can never end in a draw. Once every cell is filled, exactly one player has connected their sides — always. (This fact is equivalent to a deep result in topology, the Brouwer fixed-point theorem.)

And there is a second, stranger fact. On any board, the first player can force a win. We can prove this with certainty. What we cannot do — for boards bigger than a handful of cells — is tell you a single move that wins.

You are Blue, connecting the left and right edges. The bot is Red, connecting top and bottom. Tap an empty cell to place your stone; the bot replies. The instant either color links its two sides, that chain lights up.

<p class="hint">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{your_move}}</div>
<div class="btns">
  <button id="reset" type="button">{{new_game}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.blue { color: #2563eb; }
.red { color: #dc2626; }
.board { position: relative; width: 320px; height: 250px; margin: .4rem auto; }
.hexwrap { position: absolute; width: 40px; height: 46px; }
.hex { width: 100%; height: 100%; cursor: pointer;
       clip-path: polygon(50% 0%, 100% 25%, 100% 75%, 50% 100%, 0% 75%, 0% 25%);
       background: #e8eef3; border: none; transition: background .12s; display: block; }
.hex.empty:hover { background: #d4dde6; }
.hex.blue { background: #2563eb; cursor: default; }
.hex.red  { background: #dc2626; cursor: default; }
.hex.win  { box-shadow: 0 0 0 3px #fbbf24; filter: brightness(1.15); }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; text-align: center; }
.status.blue { color: #2563eb; }
.status.red  { color: #dc2626; }
.btns { display: flex; gap: .5rem; justify-content: center; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }

// Code not found

Try to lose on purpose by leaving gaps — you will find the board simply refuses to stay unfinished without a winner. When the last cell is colored, someone has always connected. That no-draw guarantee is what makes the next fact possible: a clean argument that the first player wins, even though the board above is small enough to fill in by brute force but a real 11×11 board is not.

Here is the argument that the first player wins, due to John Nash (around 1949). It is called strategy stealing.

• Suppose, for contradiction, the second player had a guaranteed winning strategy S.
• The first player can then steal it: play any arbitrary first move, then simply follow S as if they were the second player. In Hex an extra stone of your own color never hurts you — it can only help.
• That would make both players winners, which is impossible since Hex can never draw. So no winning strategy for the second player exists — meaning the first player must have one.

Read that again: the proof never names a move. It shows a winning strategy exists without producing it. This is a nonconstructive proof — it wins the argument, not the game.

And finding the actual moves is brutally hard. In 1981 Stefan Reisch proved that Hex is PSPACE-complete: deciding who wins a given Hex position is as hard as any problem solvable in polynomial memory, a class believed to dwarf P vs NP-style difficulty. So the gap is real and permanent: we know the first player wins, yet computing how, on a full-size board, is intractable.

Hex is tiny, but the ideas around it are everywhere:

• Existence without construction. Strategy stealing is a clean example of proving something exists without building it — the same move that powers many results across mathematics, from fixed-point theorems to the pigeonhole principle.
• The frontier of game AI. Because optimal Hex is PSPACE-complete, programs can't just look it up; modern Hex bots lean on the same deep search and neural-network ideas that cracked Go.
• Two-player games as a complexity yardstick. Generalized board games — Hex, Go, Checkers — are the canonical hard problems for PSPACE and beyond, the way SAT is the canonical NP problem.
• A lesson in humility. Hex shows that knowing the answer exists and knowing the answer are genuinely different — a distinction at the heart of computational complexity.

Hex is the rare game that hands you a victory and withholds the instructions. A two-line argument proves the first player can always win, yet for any serious board no one can tell you the moves — and Reisch's theorem says no one ever will tell you cheaply, because the problem is PSPACE-complete.

So Hex is a perfect little parable for the limits of computation: the difference between "a solution exists" and "here is the solution" is not a technicality. Sometimes, as with this elegant grid of hexagons, that gap is the whole story — and it sits right next to P vs NP among the deepest questions about what we can and cannot compute.