[I posted this on math.stackexchange.com about two weeks ago, but didn't get any reply, so I'm trying it here.]

Consider the following simplified form of ["Gerrymandering"](https://en.wikipedia.org/wiki/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).

[![example picture][1]][1]

I wrote a [backtracking algorithm](http://weitz.de/gm/) 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?


  [1]: https://i.sstatic.net/6iMO1.png