Speed-up search of incomplete solutions (#1116)

Speed-up search of incomplete solutions (#1116)

* Speed-up search of incomplete solutions

We now avoid earlier the solving of a dependency which has been already seen in
the search branch.

We also had a bug that was duplicating the search space with every extra
dependency. That meant an exponential increase in time for every extra
dependency. Fortunately, this only affected incomplete solutions.

In practice there are no visible changes as the solutions found are ultimately
the same.

* Fixes found by GHA

Co-authored-by: GHA <actions@github.com>