Edit: Under 10s with CP-SAT after removing many variables (had multiple variables for the same pieces).