juliank, I was missing negative unit propagation in my dependency solver hence it was just running forever trying to install apt-utils=2.7.14build2 in all places it could backtrack to.
Like it doesn't do logical backtracking, it just backtracks to the previous decision level.
Now I propagate correctly
apt=2.7.14build2
-> not apt=<other version>
-> not any of its reverse dependenciesAnd it works correctly.