My approach - standard backtrack.  
I represented the board as a 15 by 21 rectangle, and the two
types of cells (parity) as 0 and 1.  For each orientation of 
each piece, I had to track the locations of the cells it would 
fill, and also their parity.  I followed a set scanning order, 
going across the rows, bottom to top, from right to left, find 
the first unfilled cell, scan the randomized list of pieces and 
orientations to find the next piece of proper parity which would 
fit, and testing to see if holes were created, and also if the 
piece touched the top, to see that any regions created were not 
divisible by 5.  When no more placements were possible, lift 
the last piece and continue.

Occasionally a region would occur which was fillable only by 
pieces already in place.  The solver would spin its wheels trying 
to fill the rest of that row, hitting the bad place, then 
backtracking. If this happened early on, too much time would be 
required to backtrack far enough due to the larger number of 
possibilities.  I decided not to program a check for this, since 
most of the time the solver ran very quickly up to the 57-59 
pieces placed range, and getting past bad areas was very fast 
due to the small number of pieces left to try.  Also each time 
I restarted, the run was different due to the randomization.