<sub>[I posted [this][1] on Math Stack Exchange about two weeks ago, but didn't get any reply, so I'm trying it here.]</sub> --- 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][2]][2] 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://math.stackexchange.com/q/3119994 [2]: https://i.sstatic.net/6iMO1.png