Given that Cargo is written in Rust, you would think there would be at least one battle tested solver that could be used. Perhaps it was harder to extract and make generic than write a new one?
Cargo's solver incorporates concepts that .debs don't have, like Cargo features, and I'm sure that .debs have features that Cargo packages don't have either.
Historically apt hasn't had much of a "solver". It's basically take the user's upgrade/install action, if there's some conflict or versioned requirement, go to the candidate (≈newest barring pinfile shenanigans) of the involved packages, and if there's still a conflict, bail.
It was always second-tier utilities like Aptitude that tried to search for a "solution" to conflicting packaging constraints, but this has always been outside of the core functionality, and if you accepted one of Aptitude's proposed paths, you would do so knowing that the next apt dist-upgrade was almost certainly going to hose everything again.
I think the idea in Apt-world is that it's the responsibility of the archive maintainer to at all times present a consistent index for which the newest versions of everything can coexist happily together. But this obviously breaks down when multiple archives are active on the same apt conf.
Cargo isn't satisfied with its own solver either. Solvers are a hard and messy problem.
The problem is theoretically NP complete (a SAT solver), but even harder than that: users also care about picking solutions that optimize for multiple criteria like minimal changes, more recent versions, minimal duplication (if multiple versions can coexist), all while having easy-to-understand errors when dependencies can't be satisfied, and with better-than-NP performance. It ends up being complex and full of compromises.
