NP-complete means that it's easy to test if we're right, but because of that complexity we can't always find a valid solution to test within a predictable period of time. Both circuit board routing and computer vision are variations on the same fundamental problems. Once we solve we, we solve the other.
However, when I was growing up most serious computer scientists believed that CV (computer vision) was a 'hard' problem that would never be 'solved'. After all, to do it right you must first at least solve subgraph isomorphism and a bunch of other things that are also NP-complete.
What they missed was that we don't actually NEED to solve it in a fixed amount of time. Even for things like driving a car the stochastic heuristic based answer is 'good enough'. e.g. - Cars driven by computers don't have to be perfect, they just have to kill other drivers less often than humans do.
We can find AN answer in polynomial time, and that's good enough. It might not be the ideal answer, but that doesn't matter in the real world.
People use NP complete as shorthand for 'impossible to do with a computer', but we now 'solve' (bypass?) NP complete problems regularly and at scale by just ignoring the fact that our answers aren't perfect.
> I'd love to see that chat log, and the final board. To be fair I've only been testing on nontrivial PCBs with 6+ layers and I haven't had the luck you have.
I wish I could share it, but it's for a commercial project that hasn't been released yet and I'm not sure if it will be open source, but a few folks have asked. I might do a blog post on it this weekend with as much detail as I can safely post.
It's only 3 layers, and less that 30 components, but the fact remains that I didn't design any of it by hand and it worked on the first go.