So, then how are today's pcb layout techs solving these Np-hard problems in your mind, armed only with Altium?

Only decades of standards compliance, workmanship training, and experience. Human beings are very good at spotting patterns in noisy jungles, and making rational design tradeoffs.

Auto-routers have been around far longer than even smartphones. Somewhat functional in the trivial problem domains, and always useless where design choices mattered.

Best of luck solving a named problem. =3