_{[I posted this on Math Stack Exchange about two weeks ago, but didn't get any reply, so I'm trying it here.]}

Consider the following simplified form of "Gerrymandering": You have $n^2$ squares arranged as an $n\times n$ matrix. Each square is marked with either $0$ or $1$ which means a "voter preference" for one of two parties. The task is to divide the set of squares into $n$ subsets of the same size $n$ such that one of the parties, say $1$, has the majority in more than half of the regions - if that's possible at all. The main geometrical restriction is that each region has to be connected in the sense that two squares are connected if they share a whole edge (and not only a corner).

I wrote a backtracking algorithm to solve this problem which essentially tries all possible ways of assigning connected regions. It works, but it of course gets much slower as $n$ increases. I was wondering if this problem (or some variant of it) might be NP-complete. I would think, though, that to be able to find a polynomial-time reduction of a known NP-complete problem to this one, this problem has to be a bit more general. Obviously, there are various ways to generalize it:

• In its easiest form, the above only works for odd $n$ as for even $n$ there's the chance of a draw. But one could of course also allow draws and stipulate that, say, you've "won" in a $6\times6$ matrix if you can find three regions with a draw and two where your party wins.
• One could require that you have to win by a certain margin: $1$ needs to win at least $k$ more regions than $0$.
• The matrix doesn't have to be a square matrix.
• The regions don't have to have the exact same size.
• More than two parties...

I would want to keep the connectedness restriction, though.

I searched the web to find similar problems but wasn't really successful; maybe I didn't use the right words. I found some results about the math of Gerrymandering, but they are about different (and more complicated) problems. I also tried to find known problems that are obviously related to this one, but so far to no avail. So my questions are:

• Is this a known problem (maybe a game or puzzle)? And if so, what's its name?
• If not, does this look similar to a known problem?
• Any other hints where to look for more information?