Counting Without Counting: How the 3×3 Solver Works

From Claude Code: Every Unranked 3×3 game in Spare Squares shows you a number called the maximum score. It's the best result anyone could possibly achieve on the board you were given. When you finish, the game tells you what fraction of that you reached. That number isn't precomputed and it isn't an estimate — it's calculated, exactly, every time a 3×3 game starts. By your phone. The honest version of the problem is brutal. You have nine tiles. Each tile has four sides. You need to place all nine in a 3×3 grid, and each tile can be rotated four ways. Every adjacent pair of edges scores between 0 and 3 points based on a fixed lookup table — twelve internal edges, so the perfect score is 60. To find the best arrangement by brute force, you'd have to try every permutation of nine tiles into nine slots, with every rotation: 9! × 4⁹ ≈ 95 billion arrangements. On a phone, in the half-second between tapping "Start" and seeing the board, that is not happening. So the user's solver doesn't do that. The trick is recognizing that the 3×3 grid has a structure you can exploit. Think of the nine slots as a plus sign and four corners. The four "arm" slots (top-center, center-left, center-right, bottom-center) are special: every corner slot is adjacent to exactly two of them, and the very center is adjacent to all four. If you fix what goes in the four arms — and fix their rotations — then every remaining slot becomes independent. The score that any leftover tile would earn in any leftover slot depends only on the tiles already placed around it. There's no interaction between the choices. That changes everything. Once the arms are pinned, the question "what's the best way to place the remaining five tiles in the remaining five slots?" stops being a combinatorial nightmare and becomes a 5×5 cost matrix. For each of the five free tiles, in each of the five free slots, you compute the best score that tile could achieve there (trying its four rotations). Then you find the highest-scoring assignment by trying all 5! = 120 permutations. That last step is small enough to brute-force directly. The outer search — over choices of which four tiles go on the arms, and in what arrangement and rotation — is bigger but still tractable. C(9,4) = 126 ways to pick the four arm tiles. Six distinct circular arrangements of those four. 4⁴ = 256 ways to rotate them. Multiply: about 23 million states, each followed by the small inner permutation. That fits in well under a second. The other optimization that earns its keep is the corner cache. A corner tile's score depends on exactly six things: which corner it is, the two arm tiles flanking it, the rotations of those two arms, and the corner tile itself. That's it — the rest of the board doesn't matter. Across the millions of arm configurations the solver tries, the same corner-with-the-same-neighbors situation comes up many times. So the algorithm builds a key from those six values and remembers the score it computed. Next time the same key shows up, it returns the cached value instead of re-trying four rotations of the corner tile. The center slot doesn't get this treatment, because its score depends on all four arms — caching by a four-tile key has too many distinct states to pay off. So the center is recomputed every time. That's fine; it's only one slot. There's also an early exit. If at any point the running best hits 60, the solver returns immediately. Most boards never reach 60 — the random tiles usually don't permit it — but the check costs nothing and saves real time on the boards that do. The whole thing lives in the client and runs locally on every device, every Unranked 3×3 game. About 120 lines, in any language. It's the kind of decomposition — fix a backbone, then exploit the independence the backbone creates — that doesn't show up unless you stare at the geometry of the problem for a while. The naive search is unbounded in any practical sense; the structured search runs in the time it takes you to swipe up. Every game, on your phone, a small algorithmic search runs and decides what the best you could possibly do. It's a nifty little bit of algorithm solving — quietly, twelve thousand kilometers of pixel away from anyone who'd ever see it work.