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.
(
geocities.com/liviozuc)