Routing algorithm

Once every cell is placed, a routing algorithm draws the actual metal wires that connect them — across a dozen stacked metal layers, around obstacles, without two wires touching. It is a colossal three-dimensional maze-solving problem: thousands to millions of nets, each needing its own non-conflicting path, sharing a finite grid of routing tracks. The work splits into 'global routing,' which assigns each net to a coarse corridor of tiles while watching congestion, and 'detailed routing,' which commits each wire to exact tracks and vias while obeying spacing rules.

The atomic primitive is Lee's maze router (1961): flood a grid outward from the source like ripples on a pond until you reach the target, then trace the shortest path back — guaranteed optimal for one net but slow. A* speeds this up by aiming the search toward the goal, and pattern routers try simple L- and Z-shapes first. The hard part is that nets fight over the same tracks, so routers use 'rip-up and reroute': tear out the worst offenders and lay them down again with penalties on crowded regions, iterating until everything fits.