Inexact cover, or cover with gaps
I'd propose this idea:

Let the algorithm run almost naturally, but if it encounters a shortest column that has no options left, do not backtrack immediately. Instead, ignore that column and pick another one. Do this up to four times per iteration. Once more than 4 columns have no options, do backtrack as you normally would.

This will eventually run until a solution is found, in which 4 cells will be left unassigned.

By allowing 4 option-less columns, you place no required knowledge on which columns (cells) should be left unoccupied. The matrix is kept small and tidy as before.

Performance: The search tree probably does not grow too vast, as most of the "stupid" piece placements will trigger the limit within 1 or 2 iterations. Accordingly, the tree should only be about one order of magnitude larger than usual.