[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": 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?

_{[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?

[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": 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, i.e. each square of each region must share at least one edge with at least one other square of the same region.

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?

[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": 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?