Adds the solution to the sequence of solutions. If the capacity is met, then the oldest (first) item is evicted and returned
a possibly evicted item
the solution to add