Three steps to the capitol

The cheaper route

Jane Street's October puzzle asks you to divide an 11 by 11 grid into connected, symmetric states. Some states have a capitol. You can move one square up, down, left, or right, paying the smaller of the two states' areas at each step. The 33 numbers in the grid are the costs of reaching a nearest capitol.

The 11 at (1,6) is my favorite part of the finished map. It sits in a 10-square state, two rows above a singleton capitol. Go down, right, down and the trip costs 10 + 10 + 1 = 21. Go right, down, down and it costs 5 + 5 + 1 = 11. That first step lands in the five-square bar along the top edge. The next step puts you back in the state you started in.

Both trips take three steps and end at the same square. Crossing the border twice saves 10. You can compare them on the map above, or click another square to trace one of its cheapest routes. Coordinates throughout are row, column, starting at 1.

What a single 1 forces

A clue of 1 is unusually helpful. Every step costs at least 1, so the capitol must be one step away. For that step to cost 1, one of its endpoints must be a one-square state. A singleton is its own capitol, so it cannot be the numbered cell. It has to be a neighbor.

Look at the 1 at (5,11). Put a singleton above it, at (4,11), and the 14 at (3,11) would be only one step from a capitol, at cost 1. Put the singleton to its left, at (5,10), and the 4 at (5,9) would have the same problem. There is no square to the right. That forces a singleton at (6,11).

Large differences between clues also tell you something about the states. The 51 at (4,4) and the 7 at (3,3) differ by 44. Either two-step route between them must cost at least 44. A route through a middle square costs at most twice that square's state area, so both (3,4) and (4,3) belong to states of at least 22 squares. In the solution, both belong to the 37-square state.

Finding the states

The capitol rule is easy to misread. Every nonidentity symmetry of a state must fix exactly one square. A straight three-square bar has a half-turn center, but reflecting it along its length fixes all three squares. It has no capitol. Checking one symmetry is not enough.

I used an AI-assisted search in OR-Tools CP-SAT to find the partition. The search combined a catalog of all connected symmetric shapes through area 11 with cell-by-cell variables for larger states. The difficult part was getting the shapes and the distances to work at the same time.

A relaxed search found a promising set of state areas before it satisfied all the symmetry rules. Its 37-square state was asymmetric and its proposed capitol was wrong. Keeping the areas fixed made the remaining search manageable. The full model rearranged the four-square state near the center, restored the large state's half-turn symmetry, and placed its capitol at (7,6). Two formulations reached the same map. That final repair took about five seconds; the exploratory search took much longer.

Ruling out a cheaper path

Finding a route that costs 51 only proves the answer is at most 51. There must also be no route costing 50. The completed distance field gives a short way to check that.

Give each cell a nonnegative value d, with zero exactly at the capitols. On every edge, the difference between the two values must be no greater than the cost of the step. Then any route to zero must cost at least the value at its starting square.

For the other direction, every non-capitol needs a neighbor whose value is lower by exactly the cost of stepping there. Following those neighbors spends precisely d. Each step decreases the value, so the walk must reach a zero. Together, these two checks prove that every value is a shortest-path distance.

The verifier checks all 220 edges and a descending step at every non-capitol. It also reconstructs the graph and runs Dijkstra from all eight capitols. All 33 clues agree. For two quick examples, the 51 reaches (2,3) for 37 + 7 + 7. The 77 takes three steps left along the bottom row to (11,6), for 37 + 37 + 3.

408,951

The last calculation uses state areas, not travel costs. Replace each cell by the size of its state, sum each row, square those eleven totals, and add. The result is 408,951.

As a check on the counting, the row totals add to 2,033. A state of area a contributes a to each of its a squares, so that same total must equal the sum of the squared state areas. It does.

The downloadable verifier needs only Python's standard library. Run python3 verify.py solution.json to check the states, capitols, clues, and arithmetic. A separate audit used rational-coordinate symmetry checks and Floyd-Warshall and reached the same result. These checks establish that this partition works. They do not prove it is unique.