1. The flippable regions need be flipped at most once, in any order. So, one could think of a solution as a collection of boolean variables, one for each region, indicating whether to flip it (true/1 if so, false/0 otherwise, feels natural).

2. A tile needs to be flipped an even number of times if it starts in the desired state, and an odd number of times otherwise. So: Give each tile an equation by forming the XOR (or addition modulo 2) of the variables for all the regions it inhabits, and then setting that expression equal to 0 if the tile starts out in the desired state, otherwise 1.

3. Observe that such equations are always easy to rearrange so as to solve for any desired variable.

4. Observe that we can therefore run through a familiar substitution process, and good things will happen.

What I find elegant here is that the resulting algorithm is known to many from early algebra and has a much more clearly bounded runtime than the backtracking searches that suit other logic puzzles. Of course, as you've evinced, the fuller representation with linear algebra opens many doors to both implementing this well and exploring its other properties.

Finding par, on the other hand, I'll have to consider further. I suspect that, after representing the solution space succinctly, you could get a fair way with a backtracking search therein (where to make a forward step is to concretely assign a value to a variable), with the search tree trimmed via the best par observed so far. If you have something drastically better than that, I'm sure that would be interesting!

Looking forward to seeing what you do next, also perhaps the potential blog post you mentioned elsewhere in this thread, etc.