# Is this kind of “Gerrymandering” NP-complete?

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?