I thought the debian SAT solver was a maintainer tool rather than something that ran every time? In any case, conda's implementation is really quite awful by comparison and they would have been well served by copying something that works instead of building something that doesn't.
Debian managed something like this over 20 years ago in dpkg. But somehow people must keep reinventing the wheel.