I tried modeling the problem as a mixed-integer linear program (one binary variable for each possible piece position) and CP-SAT solved this one in two minutes.

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