Here is the description of a problem

Given an array of strings representing an $N$x$N$ grid of $red$ and $blue$ cells and a target color $r$ or $b$, partition the grid into $N$ sections of $N$ contiguous cells. The goal is to have the maximum number of sections where more than half of cells are of the target color. Return the sections as an array of arrays of strings representing the coordinates of the cells in each section.

For example, in a 3×3 grid, given

$$

begin{pmatrix}

b & r & r\

b & b & b\

b & b & r

end{pmatrix}

$$

and a target color of $b$ the expected return would be

$$

begin{eqnarray}

section&=&(2,1) (1,1) (1,2)\

section&=&(1,3) (2,3) (2,2)\

section&=&(3,1) (3,2) (3,3)

end{eqnarray}

$$

To solve the problem, what I wanted to try is to represent the matrix as graph and then perform these steps

- Find all the (N-1)-hop neighbors and create arrays like $((1,1), (1,2), (1,3))$ for $N=3$
- Find all combinations of those arrays that covers the whole matrix
- Rank it somehow?
- ???

(failed to come up with a solution for step 3 and below).

However I believe my approach would be too complex if for example N will become like 6, 7 etc, because it is basically a brute force. *So I have been wondering if there is some existing algorithm that tackles the same problem*?