--orders: route several connection orders in parallel, keep the best

The default order is always one of the candidates, so the result is
never worse than a plain run; ties go to the earlier candidate.

.gitignore

@@ -20,3 +20,7 @@ htmlcov/
 # Editor / OS
 .DS_Store
 *.swp
+
+# Benchmark inputs and results: board lists name local, often private, designs
+/bench/boards*.txt
+/bench/results/

bench/bench.py

@@ -0,0 +1,206 @@
+"""Route boards under several connection orders and compare variants fairly.
+
+One routing run says little: which connection routes first moves a result by
+ten connections either way on a crowded board. This runs every board with
+every variant under the same seeds (``--seed``), so variant A and variant B
+face the same order on seed 3, and compares them seed by seed.
+
+    uv run python bench/bench.py BOARDS -v base= -v hist1="--history-cost 1" \\
+        --seeds 6 --jobs 4 --out bench/results/hist.jsonl
+
+BOARDS is a text file, one board per line: a name, a DSN path and any flags
+that board always needs, e.g.
+
+    sense  /path/to/charge-sense.dsn  --edge-clearance 0.5
+    # comments and blank lines are ignored
+
+A variant is ``NAME=FLAGS``, or ``NAME@SRC=FLAGS`` to run the code under SRC
+(a worktree's ``src`` directory) rather than the installed package. The first
+variant is the baseline. Results are appended to --out as JSON lines, and runs
+already in it are skipped, so an interrupted benchmark picks up where it left
+off. Exits non-zero if any run crashed or timed out.
+"""
+
+from __future__ import annotations
+
+import argparse
+import json
+import math
+import os
+import re
+import shlex
+import subprocess
+import sys
+import tempfile
+import threading
+import time
+from concurrent.futures import ThreadPoolExecutor, as_completed
+from pathlib import Path
+
+NOT_ROUTED = re.compile(r"freeroute: (\d+) connection\(s\) not routed")
+TO_ZONE = re.compile(r"freeroute: (\d+) more connection\(s\) left to a zone fill")
+
+
+def parse_boards(path: Path) -> list[tuple[str, Path, list[str]]]:
+    boards = []
+    for line in path.read_text().splitlines():
+        words = shlex.split(line, comments=True)
+        if not words:
+            continue
+        if len(words) < 2:
+            raise SystemExit(f"{path}: want 'name path [flags]', got {line!r}")
+        dsn = Path(words[1]).expanduser()
+        if not dsn.is_file():
+            raise SystemExit(f"{path}: no such DSN {dsn}")
+        boards.append((words[0], dsn, words[2:]))
+    return boards
+
+
+def parse_variant(spec: str) -> tuple[str, str | None, list[str]]:
+    head, sep, flags = spec.partition("=")
+    if not sep or not head:
+        raise SystemExit(f"variant {spec!r}: want NAME=FLAGS or NAME@SRC=FLAGS")
+    name, _, src = head.partition("@")
+    if src and not (Path(src) / "freeroute").is_dir():
+        raise SystemExit(f"variant {name}: {src} has no freeroute package")
+    return name, src or None, shlex.split(flags)
+
+
+def run_one(board, variant, seed: int, timeout: float) -> dict:
+    name, dsn, board_flags = board
+    vname, src, flags = variant
+    env = dict(os.environ)
+    if src:
+        env["PYTHONPATH"] = src + os.pathsep + env.get("PYTHONPATH", "")
+    with tempfile.TemporaryDirectory() as tmp:
+        cmd = [
+            sys.executable, "-m", "freeroute.cli", str(dsn), "-do", f"{tmp}/out.ses",
+            *board_flags, *flags, "--seed", str(seed),
+        ]
+        start = time.monotonic()
+        proc = subprocess.Popen(
+            cmd, env=env, stdout=subprocess.DEVNULL, stderr=subprocess.PIPE, text=True
+        )
+        expired = threading.Event()
+
+        def expire() -> None:
+            expired.set()
+            proc.kill()
+
+        timer = threading.Timer(timeout, expire)
+        timer.start()
+        err = proc.stderr.read()
+        # reap it here rather than through Popen, to keep its peak memory
+        _, wstatus, usage = os.wait4(proc.pid, 0)
+        timer.cancel()
+        proc.returncode = os.waitstatus_to_exitcode(wstatus)
+        proc.stderr.close()
+        status = "timeout" if expired.is_set() else (
+            "ok" if proc.returncode == 0 else f"exit {proc.returncode}"
+        )
+        rss_mb = round(usage.ru_maxrss / 1024)
+        secs = round(time.monotonic() - start, 1)
+    missing = NOT_ROUTED.search(err)
+    zone = TO_ZONE.search(err)
+    return {
+        "board": name, "variant": vname, "seed": seed, "status": status,
+        "unrouted": int(missing.group(1)) if missing else 0,
+        "to_zone": int(zone.group(1)) if zone else 0,
+        "secs": secs, "rss_mb": rss_mb,
+        "tail": err.strip().splitlines()[-1] if status != "ok" and err.strip() else "",
+    }
+
+
+def mean_sd(xs: list[float]) -> tuple[float, float]:
+    m = sum(xs) / len(xs)
+    sd = math.sqrt(sum((x - m) ** 2 for x in xs) / (len(xs) - 1)) if len(xs) > 1 else 0.0
+    return m, sd
+
+
+def report(rows: list[dict], boards, variants) -> None:
+    ok = {(r["board"], r["variant"], r["seed"]): r for r in rows if r["status"] == "ok"}
+    base = variants[0][0]
+    print(f"\nunrouted per board (lower is better), baseline {base!r}\n")
+    print(f"{'board':14} {'variant':14} {'n':>3} {'mean':>6} {'sd':>5} {'min':>4} {'max':>4}"
+          f" {'secs':>6}   vs baseline, seed by seed")
+    for bname, _, _ in boards:
+        for vname, _, _ in variants:
+            runs = sorted((k[2], r) for k, r in ok.items() if k[:2] == (bname, vname))
+            if not runs:
+                print(f"{bname:14} {vname:14}   no finished runs")
+                continue
+            xs = [r["unrouted"] for _, r in runs]
+            m, sd = mean_sd(xs)
+            t, _ = mean_sd([r["secs"] for _, r in runs])
+            line = (f"{bname:14} {vname:14} {len(xs):>3} {m:>6.1f} {sd:>5.1f} {min(xs):>4}"
+                    f" {max(xs):>4} {t:>6.0f}")
+            if vname != base:
+                diffs = [r["unrouted"] - ok[(bname, base, s)]["unrouted"]
+                         for s, r in runs if (bname, base, s) in ok]
+                if diffs:
+                    dm, dsd = mean_sd(diffs)
+                    se = dsd / math.sqrt(len(diffs)) if len(diffs) > 1 else float("inf")
+                    better = sum(d < 0 for d in diffs)
+                    worse = sum(d > 0 for d in diffs)
+                    # a difference inside two standard errors is not a finding
+                    verdict = ("better" if dm < 0 else "worse") if abs(dm) > 2 * se else "no clear change"
+                    line += (f"   {dm:+.1f} ± {se:.1f}  ({better} better, {worse} worse,"
+                             f" {len(diffs) - better - worse} same)  {verdict}")
+            print(line)
+    failed = [r for r in rows if r["status"] != "ok"]
+    for r in failed:
+        print(f"FAILED {r['board']} {r['variant']} seed {r['seed']}: {r['status']} {r['tail']}")
+
+
+def main(argv: list[str] | None = None) -> int:
+    ap = argparse.ArgumentParser(description=__doc__.split("\n\n")[0])
+    ap.add_argument("boards", type=Path, help="board list: name, DSN path, flags")
+    ap.add_argument("-v", "--variant", action="append", required=True,
+                    help="NAME=FLAGS or NAME@SRC=FLAGS; the first is the baseline")
+    ap.add_argument("--seeds", type=int, default=6, help="orders per board and variant")
+    ap.add_argument("--first-seed", type=int, default=0)
+    ap.add_argument("--jobs", type=int, default=4, help="runs at once")
+    ap.add_argument("--timeout", type=float, default=1800, help="seconds per run")
+    ap.add_argument("--out", type=Path, required=True, help="JSON lines, appended")
+    ap.add_argument("--report-only", action="store_true", help="summarise --out, run nothing")
+    args = ap.parse_args(argv)
+
+    boards = parse_boards(args.boards)
+    variants = [parse_variant(v) for v in args.variant]
+    if len({v[0] for v in variants}) != len(variants):
+        raise SystemExit("variant names must differ")
+    seeds = range(args.first_seed, args.first_seed + args.seeds)
+
+    rows: list[dict] = []
+    if args.out.exists():
+        rows = [json.loads(line) for line in args.out.read_text().splitlines() if line.strip()]
+    done = {(r["board"], r["variant"], r["seed"]) for r in rows if r["status"] == "ok"}
+    todo = [(b, v, s) for b in boards for v in variants for s in seeds
+            if (b[0], v[0], s) not in done]
+
+    if not args.report_only and todo:
+        args.out.parent.mkdir(parents=True, exist_ok=True)
+        print(f"{len(todo)} runs, {args.jobs} at a time", file=sys.stderr)
+        # retried runs replace their earlier failure
+        rows = [r for r in rows if (r["board"], r["variant"], r["seed"]) in done]
+        with ThreadPoolExecutor(args.jobs) as pool, args.out.open("w") as out:
+            for r in rows:
+                out.write(json.dumps(r) + "\n")
+            futures = [pool.submit(run_one, b, v, s, args.timeout) for b, v, s in todo]
+            for n, fut in enumerate(as_completed(futures), 1):
+                r = fut.result()
+                rows.append(r)
+                out.write(json.dumps(r) + "\n")
+                out.flush()
+                print(f"[{n}/{len(todo)}] {r['board']} {r['variant']} seed {r['seed']}:"
+                      f" {r['status']} unrouted {r['unrouted']} ({r['secs']}s,"
+                      f" {r['rss_mb']} MB)", file=sys.stderr)
+
+    wanted = {(b[0], v[0], s) for b in boards for v in variants for s in seeds}
+    rows = [r for r in rows if (r["board"], r["variant"], r["seed"]) in wanted]
+    report(rows, boards, variants)
+    return 1 if any(r["status"] != "ok" for r in rows) or len(rows) < len(wanted) else 0
+
+
+if __name__ == "__main__":
+    raise SystemExit(main())

src/freeroute/cli.py

@@ -19,6 +19,7 @@ import argparse
 import sys
 
 from freeroute.dsn.reader import parse_dsn
+from freeroute.route.orders import best_of_orders
 from freeroute.route.pipeline import (
     build_exact_routing_result,
     build_rooms_routing_result,
@@ -29,8 +30,8 @@ from freeroute.ses import write_ses
 #: which optional flags each engine actually implements. Anything not listed for
 #: an engine is rejected by :func:`_validate` rather than quietly ignored.
 ENGINE_OPTIONS: dict[str, frozenset[str]] = {
-    "grid": frozenset({"rip_up", "max_passes"}),
-    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes"}),
+    "grid": frozenset({"rip_up", "max_passes", "seed", "orders"}),
+    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders"}),
     "room": frozenset({"shove", "pack"}),
 }
 
@@ -41,6 +42,8 @@ _FLAG_NAMES = {
     "diagonal": "--diagonal",
     "rip_up": "--no-rip-up",
     "max_passes": "-mp/--max-passes",
+    "seed": "--seed",
+    "orders": "--orders",
 }
 
 
@@ -133,6 +136,26 @@ def build_parser() -> argparse.ArgumentParser:
         help="copper to board-edge clearance in mm, e.g. KiCad's min_copper_edge_clearance "
         "(the DSN does not carry it); default 0: copper only has to stay inside the outline",
     )
+    parser.add_argument(
+        "--seed",
+        type=int,
+        metavar="N",
+        help="grid and exact engines: shuffle the order connections are routed in; "
+        "the same seed gives the same result (default: fewer-pin nets first)",
+    )
+    parser.add_argument(
+        "--orders",
+        type=int,
+        metavar="N",
+        help="grid and exact engines: route N connection orders in parallel and keep the "
+        "one leaving the fewest connections unrouted (the default order is one of them)",
+    )
+    parser.add_argument(
+        "--jobs",
+        type=int,
+        metavar="J",
+        help="processes for --orders (default: one per order, up to the CPU count)",
+    )
     return parser
 
 
@@ -152,6 +175,8 @@ def main(argv: list[str] | None = None) -> int:
             ("diagonal", args.diagonal),
             ("rip_up", args.no_rip_up),
             ("max_passes", args.max_passes is not None),
+            ("seed", args.seed is not None),
+            ("orders", args.orders is not None),
         )
         if asked
     ]
@@ -173,29 +198,46 @@ def main(argv: list[str] | None = None) -> int:
     rip_up = not args.no_rip_up
     max_passes = args.max_passes if args.max_passes is not None else 10
 
+    if args.orders is not None and args.orders < 1:
+        parser.error("--orders must be at least 1")
     if args.engine == "exact":
-        result = build_exact_routing_result(
-            dsn,
-            layers=layers,
-            shove=args.shove,
-            diagonal=args.diagonal,
-            rip_up=rip_up,
-            max_passes=max_passes,
-            edge_clearance_mm=args.edge_clearance,
-            resolution=2 if args.grid_resolution is None else args.grid_resolution,
-            heuristic_weight=args.heuristic_weight,
-        )
-    elif args.engine == "room":
+        options = {
+            "layers": layers,
+            "shove": args.shove,
+            "diagonal": args.diagonal,
+            "rip_up": rip_up,
+            "max_passes": max_passes,
+            "edge_clearance_mm": args.edge_clearance,
+            "resolution": 2 if args.grid_resolution is None else args.grid_resolution,
+            "heuristic_weight": args.heuristic_weight,
+        }
+    elif args.engine == "grid":
+        options = {
+            "layers": layers,
+            "rip_up": rip_up,
+            "max_passes": max_passes,
+            "edge_clearance_mm": args.edge_clearance,
+            "resolution": 1 if args.grid_resolution is None else args.grid_resolution,
+        }
+    if args.engine == "room":
         result = build_rooms_routing_result(
             dsn, layers=layers, shove=args.shove, pack=args.pack,
             edge_clearance_mm=args.edge_clearance,
         )
-    else:
-        result = build_routing_result(
-            dsn, layers=layers, rip_up=rip_up, max_passes=max_passes,
-            edge_clearance_mm=args.edge_clearance,
-            resolution=1 if args.grid_resolution is None else args.grid_resolution,
+    elif args.orders and args.orders > 1:
+        result, kept, tried = best_of_orders(
+            dsn_text, args.engine, options, orders=args.orders, seed=args.seed, jobs=args.jobs
         )
+        counts = ", ".join(f"{'default' if s is None else s}: {m}" for s, (m, _z) in tried)
+        print(
+            f"freeroute: tried {len(tried)} orders, kept "
+            f"{'the default order' if kept is None else f'--seed {kept}'} (unrouted {counts})",
+            file=sys.stderr,
+        )
+    elif args.engine == "exact":
+        result = build_exact_routing_result(dsn, seed=args.seed, **options)
+    else:
+        result = build_routing_result(dsn, seed=args.seed, **options)
 
     ses_text = write_ses(dsn, result)
     missing = [u for u in result.unrouted if not u[3]]

src/freeroute/route/exact_router.py

@@ -94,6 +94,7 @@ def route_board_exact(
     edge_clearance: int | None = None,
     resolution: int = 1,
     heuristic_weight: float = 1.0,
+    seed: int | None = None,
 ) -> ExactRouteResult:
     """Route ``board`` orthogonally and verify the result with exact geometry.
 
@@ -122,6 +123,7 @@ def route_board_exact(
         edge_clearance=edge_clearance,
         resolution=resolution,
         heuristic_weight=heuristic_weight,
+        seed=seed,
     )
     edge = 0 if edge_clearance is None else edge_clearance
     outline = board.outline

src/freeroute/route/grid_router.py

@@ -28,6 +28,7 @@ from __future__ import annotations
 
 import heapq
 import math
+import random
 
 from freeroute.board.board import BasicBoard
 from freeroute.board.items import ConductionArea, ObstacleArea, Pin
@@ -154,8 +155,12 @@ class GridRouter:
         edge_clearance: int | None = None,
         resolution: int = 1,
         heuristic_weight: float = 1.0,
+        seed: int | None = None,
     ) -> None:
         self.board = board
+        # None keeps the deterministic order; a seed shuffles which connection
+        # routes first, to measure how much a result owes to the order
+        self.seed = seed
         # how far (in cells) an escape stub may run to leave a walled-in pin
         self._escape_cells = 12
         self._crowded_cache: dict = {}
@@ -212,6 +217,10 @@ class GridRouter:
         self._pad_own: dict[Node, set[int]] = {}
         self._keepout: set[Node] = set()
         self._via_keepout: set[Node] = set()
+        # inner power (plane) layers: not routed on, reached by vias
+        self._power_layers = {
+            i for i, layer in enumerate(board.layer_structure.arr) if not layer.is_signal
+        }
         self._zone_cells: dict[int, list[Node]] = {}
         # per-connection occupancy (owner = connection index)
         self._cell_owner: dict[Node, int] = {}
@@ -393,6 +402,9 @@ class GridRouter:
         self, conn: _Connection, allow_ripup: bool, conns: list[_Connection]
     ) -> list[Node] | None:
         goal_cell = self._group_target(conn.b_group)
+        if not conn.b_group[0] and any(z.layer in self._power_layers for z in conn.b_group[1]):
+            # the plane is everywhere: aim at where the route starts instead
+            goal_cell = self._group_target(conn.a_group)
         starts = self._group_ends(conn.a_group, conn.net_no, conns)
         goals = self._group_ends(conn.b_group, conn.net_no, conns)
         if not starts or not goals:
@@ -434,9 +446,18 @@ class GridRouter:
                 continue
             current = entry[1]
             if current in goals:
-                path = _reconstruct(came_from, current)
-                conn.a_end, conn.b_end = starts.get(path[0]), goals[current]
-                return path
+                end = goals[current]
+                cell = (current[0], current[1])
+                if isinstance(end, ConductionArea):  # a plane end needs its via to fit
+                    ok = via_ok.get(cell)
+                    if ok is None:
+                        ok = via_ok[cell] = self._via_placeable(cell, net_no, conns)
+                else:
+                    ok = True
+                if ok:
+                    path = _reconstruct(came_from, current)
+                    conn.a_end, conn.b_end = starts.get(path[0]), end
+                    return path
             cx, cy, cl = current
             base = g_score[current]
             for dx, dy in self._neighbours:
@@ -499,10 +520,12 @@ class GridRouter:
         return True
 
     def _zone_nodes(self, zone) -> list[Node]:
-        """Cells of a zone where a via of this net fits inside its copper."""
+        """Cells of a zone where a via of this net fits inside its copper; for a
+        plane on a power layer, on every routing layer (a via reaches it)."""
         key = id(zone)
         if key not in self._zone_cells:
             h = self.via_half
+            layers = [zone.layer] if zone.layer in self.layers else list(self.layers)
             nodes = []
             for tile in zone.tiles:
                 for cell in self._cells_in_box(tile.bounding_box(), 0):
@@ -511,7 +534,7 @@ class GridRouter:
                         zone.polygon.contains(IntPoint(c.x + dx, c.y + dy))
                         for dx in (-h, h) for dy in (-h, h)
                     ):
-                        nodes.append((*cell, zone.layer))
+                        nodes.extend((*cell, layer) for layer in layers)
             self._zone_cells[key] = sorted(set(nodes))
         return self._zone_cells[key]
 
@@ -549,8 +572,10 @@ class GridRouter:
             for node in sorted(self._end_nodes(pin, net_no, conns)):
                 ends.setdefault(node, pin)
         for zone in group[1]:
+            plane = zone.layer in self._power_layers
             for node in self._zone_nodes(zone):
-                ends.setdefault(node, None)
+                # a plane end is marked with the plane: the route ends in a via
+                ends.setdefault(node, zone if plane else None)
         return ends
 
     def _group_target(self, group) -> Cell:
@@ -704,6 +729,11 @@ class GridRouter:
 
     def _commit(self, conn: _Connection, path: list[Node]) -> None:
         wire_segs, via_cells = _split_path(path)
+        via_cells = list(via_cells)
+        if isinstance(conn.a_end, ConductionArea):
+            via_cells.append((path[0][0], path[0][1]))
+        if isinstance(conn.b_end, ConductionArea):
+            via_cells.append((path[-1][0], path[-1][1]))
         conn.trace_cells = [(cell, layer) for layer, cells in wire_segs for cell in cells]
         conn.via_cells = list(via_cells)
         for cell, layer in conn.trace_cells:
@@ -724,8 +754,8 @@ class GridRouter:
                     conn.via_halo.append(c)
         ends = ((conn.a_end, wire_segs[0], 0), (conn.b_end, wire_segs[-1], -1)) if wire_segs else ()
         for pin, (layer, cells), at in ends:
-            if pin is None:
-                continue  # ended on a zone: no stub
+            if not isinstance(pin, Pin):
+                continue  # ended on a zone or a plane: no stub
             cell = cells[at]
             for c in self._stub_cells(pin.location, cell):
                 node = (*c, layer)
@@ -735,9 +765,9 @@ class GridRouter:
         conn.wires = []
         for idx, (layer, cells) in enumerate(wire_segs):
             points = [self._cell_center(c) for c in cells]
-            if idx == 0 and conn.a_end is not None:
+            if idx == 0 and isinstance(conn.a_end, Pin):
                 points.insert(0, conn.a_end.location)
-            if idx == len(wire_segs) - 1 and conn.b_end is not None:
+            if idx == len(wire_segs) - 1 and isinstance(conn.b_end, Pin):
                 points.append(conn.b_end.location)
             points = _simplify(points)
             if len(points) >= 2:
@@ -794,9 +824,13 @@ class GridRouter:
         best_count = -1
         best_snapshot: list[tuple[int, list, list]] | None = None
         best_unrouted = len(conns)
+        # conns[i].index == i is what rip-up relies on, so shuffle a view
+        order = list(conns)
+        if self.seed is not None:
+            random.Random(self.seed).shuffle(order)
         for _ in range(passes):
             changed = False
-            for conn in conns:  # deterministic: connection creation order
+            for conn in order:
                 if conn.routed:
                     continue
                 if self._try_route(conn, conns):
@@ -835,12 +869,26 @@ class GridRouter:
         for zone in self.board.get_conduction_areas():
             if zone.layer in self.layers and zone.net_nos and self._zone_is_solid(zone):
                 zones_by_net.setdefault(zone.net_nos[0], []).append(zone)
+        # planes: zones of a net on an inner power layer, solid by construction
+        planes_by_net: dict[int, list] = {}
+        for zone in self.board.get_conduction_areas():
+            if zone.net_nos and zone.layer in self._power_layers:
+                planes_by_net.setdefault(zone.net_nos[0], []).append(zone)
+        plane_ids = frozenset(id(z) for zs in planes_by_net.values() for z in zs)
         conns: list[_Connection] = []
-        nets = set(pins_by_net) | set(zones_by_net)
+        nets = set(pins_by_net) | set(zones_by_net) | set(planes_by_net)
         # deterministic: fewer-pin nets first, then by net number
         for net_no in sorted(nets, key=lambda n: (len(pins_by_net.get(n, [])), n)):
-            groups = _connected_groups(pins_by_net.get(net_no, []), zones_by_net.get(net_no, []))
-            for ga, gb in zip(groups, groups[1:], strict=False):
+            zones = zones_by_net.get(net_no, []) + planes_by_net.get(net_no, [])
+            groups = _connected_groups(pins_by_net.get(net_no, []), zones, plane_ids)
+            hubs = [g for g in groups if any(id(z) in plane_ids for z in g[1])]
+            if hubs:
+                # a plane net: every other group goes straight to the plane
+                # (usually a stub and a via), not pad to pad across the board
+                pairs = [(g, hubs[0]) for g in groups if g is not hubs[0]]
+            else:
+                pairs = list(zip(groups, groups[1:], strict=False))
+            for ga, gb in pairs:
                 conn = _Connection(len(conns), net_no, _first(ga[0]), _first(gb[0]))
                 conn.a_group, conn.b_group = ga, gb
                 conns.append(conn)
@@ -900,8 +948,15 @@ def _ends_of(conn) -> tuple[str, str]:
     return _group_label(conn.a_group), _group_label(conn.b_group)
 
 
-def _pin_touches_zone(pin: Pin, zone) -> bool:
-    """A pad on the zone's layer whose centre or a corner lies in the zone."""
+def _pin_touches_zone(pin: Pin, zone, plane: bool = False) -> bool:
+    """A pad on the zone's layer whose centre or a corner lies in the zone.
+
+    For a plane on an inner power layer: a through-hole pad (on more than one
+    copper layer) inside it passes through the plane and is joined to it; an
+    SMD pad is not, and needs a via.
+    """
+    if plane:
+        return len(pin.layers) > 1 and zone.polygon is not None and zone.polygon.contains(pin.location)
     if zone.layer not in pin.layers or zone.polygon is None:
         return False
     if zone.polygon.contains(pin.location):
@@ -913,7 +968,9 @@ def _pin_touches_zone(pin: Pin, zone) -> bool:
     return any(zone.polygon.contains(c) for c in corners)
 
 
-def _connected_groups(pins: list[Pin], zones: list) -> list[tuple[list[Pin], list]]:
+def _connected_groups(
+    pins: list[Pin], zones: list, planes: frozenset = frozenset()
+) -> list[tuple[list[Pin], list]]:
     """Pins and zones of one net that copper already joins: a pad in a zone
     is connected to it, and two zones sharing a pad are one. Only the groups
     need routing between them. Pin groups come first, in pin order."""
@@ -927,7 +984,7 @@ def _connected_groups(pins: list[Pin], zones: list) -> list[tuple[list[Pin], lis
 
     for j, zone in enumerate(zones):
         for i, pin in enumerate(pins):
-            if _pin_touches_zone(pin, zone):
+            if _pin_touches_zone(pin, zone, id(zone) in planes):
                 parent[find(i)] = find(len(pins) + j)
     groups: dict[int, tuple[list[Pin], list]] = {}
     order: list[int] = []
@@ -1002,6 +1059,7 @@ def route_board(
     edge_clearance: int | None = None,
     resolution: int = 1,
     heuristic_weight: float = 1.0,
+    seed: int | None = None,
 ) -> RouteResult:
     """Convenience wrapper: build a :class:`GridRouter` and route the board."""
     router = GridRouter(
@@ -1017,5 +1075,6 @@ def route_board(
         edge_clearance=edge_clearance,
         resolution=resolution,
         heuristic_weight=heuristic_weight,
+        seed=seed,
     )
     return router.route()

src/freeroute/route/orders.py

@@ -0,0 +1,67 @@
+"""Route one board in several connection orders at once and keep the best.
+
+Which connection routes first moves the result on a crowded board by several
+connections either way, and no single order wins everywhere. Routing a few
+orders in parallel processes and keeping the one that leaves the fewest
+connections unrouted costs cores, not wall time.
+
+Without a seed the candidates are the default order and seeds 0 to N-2, so the
+result is never worse than a plain run. With seed S they are seeds S to S+N-1.
+Ties go to the earlier candidate, so the choice is deterministic.
+"""
+
+from __future__ import annotations
+
+from concurrent.futures import ProcessPoolExecutor
+import os
+
+from freeroute.dsn import parse_dsn
+from freeroute.ses import RoutingResult
+
+from .pipeline import build_exact_routing_result, build_routing_result
+
+
+def candidate_seeds(orders: int, seed: int | None = None) -> list[int | None]:
+    orders = max(int(orders), 1)
+    if seed is None:
+        return [None, *range(orders - 1)]
+    return list(range(seed, seed + orders))
+
+
+def score(result: RoutingResult) -> tuple[int, int]:
+    """Connections left open, then those left to a zone fill: lower is better."""
+    missing = sum(1 for u in result.unrouted if not u[3])
+    return missing, len(result.unrouted) - missing
+
+
+def route_once(dsn_text: str, engine: str, options: dict, seed: int | None) -> RoutingResult:
+    dsn = parse_dsn(dsn_text)
+    if engine == "exact":
+        return build_exact_routing_result(dsn, seed=seed, **options)
+    if engine == "grid":
+        return build_routing_result(dsn, seed=seed, **options)
+    raise ValueError(f"routing orders are not supported by the {engine} engine")
+
+
+def best_of_orders(
+    dsn_text: str,
+    engine: str,
+    options: dict,
+    *,
+    orders: int,
+    seed: int | None = None,
+    jobs: int | None = None,
+) -> tuple[RoutingResult, int | None, list[tuple[int | None, tuple[int, int]]]]:
+    """Route ``orders`` orders and return the best result, the seed that made
+    it (None for the default order), and every candidate's seed and score."""
+    seeds = candidate_seeds(orders, seed)
+    if len(seeds) == 1:
+        result = route_once(dsn_text, engine, options, seeds[0])
+        return result, seeds[0], [(seeds[0], score(result))]
+    jobs = max(1, min(jobs or os.cpu_count() or 1, len(seeds)))
+    with ProcessPoolExecutor(jobs) as pool:
+        futures = [pool.submit(route_once, dsn_text, engine, options, s) for s in seeds]
+        results = [f.result() for f in futures]
+    scores = [score(r) for r in results]
+    best = min(range(len(seeds)), key=lambda i: (scores[i], i))
+    return results[best], seeds[best], list(zip(seeds, scores, strict=True))

src/freeroute/route/pipeline.py

@@ -80,6 +80,7 @@ def route_dsn_board(
     layers: list[int] | None = None,
     rip_up: bool = True,
     max_passes: int = 10,
+    seed: int | None = None,
 ) -> tuple[RouteResult, int, list[str]]:
     """Route a parsed :class:`DsnBoard`; return the board-unit result, the scale,
     and the layer names. ``layers`` restricts routing to those signal-layer
@@ -100,6 +101,7 @@ def route_dsn_board(
         layers=layers,
         rip_up=rip_up,
         max_passes=max_passes,
+        seed=seed,
     )
     return result, scale, [layer.name for layer in dsn.layers]
 
@@ -140,11 +142,12 @@ def build_routing_result(
     rip_up: bool = True,
     max_passes: int = 10,
     edge_clearance_mm: float | None = None,
+    seed: int | None = None,
 ) -> RoutingResult:
     """Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
     route, scale, layer_names = route_dsn_board(
         dsn, layers=layers, rip_up=rip_up, max_passes=max_passes,
-        edge_clearance_mm=edge_clearance_mm, resolution=resolution,
+        edge_clearance_mm=edge_clearance_mm, resolution=resolution, seed=seed,
     )
     return _to_routing_result(route, dsn, scale, layer_names)
 
@@ -160,6 +163,7 @@ def route_dsn_board_exact(
     rip_up: bool = True,
     shove: bool = False,
     diagonal: bool = False,
+    seed: int | None = None,
 ) -> tuple[ExactRouteResult, int, list[str]]:
     """Route a parsed :class:`DsnBoard` with the exact-geometry (orthogonal,
     DRC-verified) track; return the exact result, the scale, and layer names.
@@ -184,6 +188,7 @@ def route_dsn_board_exact(
         rip_up=rip_up,
         shove=shove,
         diagonal=diagonal,
+        seed=seed,
     )
     return exact, scale, [layer.name for layer in dsn.layers]
 
@@ -199,6 +204,7 @@ def build_exact_routing_result(
     rip_up: bool = True,
     max_passes: int = 10,
     edge_clearance_mm: float | None = None,
+    seed: int | None = None,
 ) -> RoutingResult:
     """Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
     exact, scale, layer_names = route_dsn_board_exact(
@@ -211,6 +217,7 @@ def build_exact_routing_result(
         edge_clearance_mm=edge_clearance_mm,
         resolution=resolution,
         heuristic_weight=heuristic_weight,
+        seed=seed,
     )
     return _to_routing_result(exact.result, dsn, scale, layer_names)
 

tests/route/test_orders.py

@@ -0,0 +1,44 @@
+"""--orders: route several connection orders and keep the best."""
+
+from __future__ import annotations
+
+from pathlib import Path
+
+from freeroute.cli import main
+from freeroute.route.orders import best_of_orders, candidate_seeds, route_once, score
+
+FIXTURES = Path(__file__).resolve().parent.parent / "dsn" / "fixtures"
+# Greedy (no rip-up), the default order strands a net here and seeds 1 to 3 do not.
+RIPUP = (FIXTURES / "ripup_needed.dsn").read_text()
+GREEDY = {"rip_up": False}
+
+
+def test_the_default_order_is_always_a_candidate_without_a_seed():
+    assert candidate_seeds(1) == [None]
+    assert candidate_seeds(4) == [None, 0, 1, 2]
+    assert candidate_seeds(3, seed=7) == [7, 8, 9]
+
+
+def test_keeps_the_order_that_leaves_the_fewest_unrouted():
+    assert score(route_once(RIPUP, "grid", GREEDY, None)) == (1, 0)
+    result, kept, tried = best_of_orders(RIPUP, "grid", GREEDY, orders=3, jobs=2)
+    assert kept == 1
+    assert score(result) == (0, 0)
+    assert tried == [(None, (1, 0)), (0, (1, 0)), (1, (0, 0))]
+
+
+def test_ties_go_to_the_earlier_candidate():
+    # every order routes this board fully, so the default order is kept
+    _, kept, tried = best_of_orders(RIPUP, "grid", {}, orders=3, jobs=3)
+    assert kept is None
+    assert all(s == (0, 0) for _, s in tried)
+
+
+def test_cli_orders_writes_the_best_session(tmp_path, capsys):
+    out = tmp_path / "best.ses"
+    rc = main([str(FIXTURES / "ripup_needed.dsn"), "--no-rip-up", "--orders", "3", "-do", str(out)])
+    assert rc == 0
+    err = capsys.readouterr().err
+    assert "tried 3 orders, kept --seed 1" in err
+    assert "not routed" not in err
+    assert out.read_text().startswith("(session")

tests/route/test_real_board_geometry.py

@@ -164,3 +164,50 @@ def test_cli_names_the_connections_it_could_not_route(tmp_path, capsys):
     assert main([str(dsn), "--engine", "exact", "-do", str(tmp_path / "out.ses")]) == 0
     err = capsys.readouterr().err
     assert "1 connection(s) not routed" in err and "N: A-1 to B-1" in err
+
+
+# --- inner plane layers (a 4-layer board with a GND plane on In1.Cu) --------
+
+def _four_layer_dsn():
+    return """(pcb four (parser) (resolution um 10) (unit um)
+  (structure
+    (layer F.Cu (type signal)) (layer In1.Cu (type power))
+    (layer In2.Cu (type power)) (layer B.Cu (type signal))
+    (boundary (path pcb 0  0 0  30000 0  30000 -30000  0 -30000  0 0))
+    (plane GND (polygon In1.Cu 0  500 -500  29500 -500  29500 -29500  500 -29500  500 -500))
+    (via "Via[0-3]_600:300_um") (rule (width 250) (clearance 150)))
+  (placement
+    (component S (place G1 5000 -5000 front 0) (place G2 25000 -5000 front 0)
+                 (place G3 15000 -25000 front 0) (place A 5000 -15000 front 0) (place B 25000 -15000 front 0))
+    (component T (place GT 15000 -15000 front 0)))
+  (library
+    (image S (pin smd 1 0 0))
+    (image T (pin tht 1 0 0))
+    (padstack smd (shape (rect F.Cu -300 -300 300 300)) (attach off))
+    (padstack tht (shape (circle F.Cu 1000)) (shape (circle B.Cu 1000)) (attach off))
+    (padstack "Via[0-3]_600:300_um" (shape (circle F.Cu 600)) (shape (circle B.Cu 600)) (attach off)))
+  (network (net GND (pins G1-1 G2-1 G3-1 GT-1)) (net SIG (pins A-1 B-1))))"""
+
+
+def test_smd_pads_reach_an_inner_plane_by_their_own_via():
+    dsn = parse_dsn(_four_layer_dsn())
+    result, scale, names = route_dsn_board_exact(dsn)
+    gnd = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "GND")
+    sig = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "SIG")
+    assert len(result.result.vias.get(gnd, [])) == 3  # one per SMD pad, none for the THT pad
+    for _layer, pts in result.result.wires.get(gnd, []):  # stubs, not tracks across the board
+        length = sum(abs(q.x - p.x) + abs(q.y - p.y) for p, q in zip(pts, pts[1:], strict=False))
+        assert length < 3000 * scale  # under 3 mm: a stub to its via
+    assert sig in result.result.routed_net_numbers  # signals still route on the outer layers
+    assert all(names[layer] in ("F.Cu", "B.Cu") for segs in result.result.wires.values() for layer, _ in segs)
+
+
+def test_a_through_hole_pad_inside_a_plane_needs_no_route():
+    from freeroute.route.grid_router import _connected_groups
+
+    board = build_board(parse_dsn(_four_layer_dsn()))
+    plane = [z for z in board.get_conduction_areas() if z.name == "GND"]
+    gnd_pins = [p for p in board.get_pins() if p.component_ref in ("G1", "G2", "G3", "GT")]
+    groups = _connected_groups(gnd_pins, plane, frozenset(id(z) for z in plane))
+    hub = next(g for g in groups if g[1])
+    assert [p.component_ref for p in hub[0]] == ["GT"]

tests/route/test_router.py

@@ -264,6 +264,19 @@ def test_larger_board_still_connects_its_multipin_nets():
     assert len(result.routed_net_numbers) == multi_pin == 4
 
 
+def test_a_seed_is_repeatable_and_does_change_the_order():
+    # The benchmark samples seeds to measure how much a result owes to the
+    # routing order. A seed that changed nothing would make every sample the
+    # same run and report no spread at all.
+    text = (FIXTURES / "kicad_routable.dsn").read_text()
+    default = _wire_key(route_dsn_board(parse_dsn(text))[0])
+    runs = {s: route_dsn_board(parse_dsn(text), seed=s)[0] for s in range(4)}
+    again = route_dsn_board(parse_dsn(text), seed=1)[0]
+    assert _wire_key(again) == _wire_key(runs[1])
+    assert any(_wire_key(r) != default for r in runs.values())
+    assert all(r.unrouted == 0 for r in runs.values())
+
+
 # --- oracle parity ----------------------------------------------------------
 
 

tests/test_cli.py

@@ -154,6 +154,8 @@ def test_cli_supported_combinations_are_accepted(tmp_path):
         "diagonal": ["--diagonal"],
         "rip_up": ["--no-rip-up"],
         "max_passes": ["-mp", "4"],
+        "seed": ["--seed", "3"],
+        "orders": ["--orders", "2"],
     }
     for engine, options in ENGINE_OPTIONS.items():
         for option in options:

uv.lock

@@ -128,7 +128,7 @@ wheels = [
 
 [[package]]
 name = "freeroute"
-version = "0.1.0"
+version = "2026.7.14"
 source = { editable = "." }
 
 [package.dev-dependencies]