Agreed. Dep had its warts (20 minutes for a very simple dep ensure...), but it solved the 80% use case in a way that was least objectionable for the majority. The fact that they can't (won't?) even refactor dep to suit their new ideas or try and revitalize the gps project just tells me that they don't really care about solving this for end users and just want to have fun writing a fancy dependency graph solver. Which is cool and all, but at least give me a stable API first.
Other package managers, including the ones mentioned in the OP, don't have SAT solvers either. This isn't a new feature of dependency resolution algorithms.