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.