1
$\begingroup$

I have a matrix with three possible elements: A, B and C. The size of the matrix could be a maximum of 15x16.

$$ \begin{bmatrix} A & A & C & A\\ A & C & B & C\\ A & C & B & C\\ A & A & C & A \end{bmatrix} $$

I need create a second matrix with the same size but different types. I need to cover all Cs with a "group", but NOT cover all Bs. As from the matrix could be covered, but dont need to be. The coverage needs to be done with groupes. Cells in a group are all connected. Each group can't be bigger than 12. The first example could be covered with only one group.

0 - empty 1 - first group $$ \begin{bmatrix} 0 & 1 & 1 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 \end{bmatrix} $$

I need an efficient algortihm that can produce legal groups (<= 12 cells) that cover all the Cs. The goal is to have as less as possible groups. If first goal is achived, the second goal is to use less material for coverage.

How to tackle this? This seems to be a very complex problem.

Second example: $$ \begin{bmatrix} A & A & C & C & A & A\\ A & C & B & B & C & A\\ A & C & B & C & A & A\\ A & C & B & C & C & A\\ A & A & C & C & B & C\\ A & A & A & A & C & A \end{bmatrix} $$ One of the solutions to example 2: 0 - empty 1 - first group 2 - second group $$ \begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 2 & 0 & 0\\ 0 & 1 & 0 & 2 & 2 & 0\\ 0 & 1 & 1 & 2 & 0 & 2\\ 0 & 0 & 0 & 2 & 2 & 2 \end{bmatrix} $$

$\endgroup$
5
  • 1
    $\begingroup$ Can you define what you mean by connected? Do you count diagonally adjacent cells as adjacent, or only horizontal/vertical adjacencies? What do you want the output of your algorithm to be? A single list of groups, such that every C is covered by one of the groups in the list? Do the groups need to be disjoint? $\endgroup$
    – D.W.
    Commented Sep 27, 2022 at 18:49
  • $\begingroup$ @D.W. Diagonal cells are NOT connected. As output I want a 2D matrix with groups so every C is covered by one of the groups. Groups can touch but can also be disjoint. I need an algorithm that efficiently calculates the groups. $\endgroup$ Commented Sep 27, 2022 at 20:21
  • $\begingroup$ The major priority is having less groups. $\endgroup$ Commented Sep 27, 2022 at 20:22
  • $\begingroup$ In practical terms, these matrices are very small - so you might be able to get away with something that's not necessarily optimal in the formal sense, cause they'll fit in cache. E.g., pick a C, do a flood fill (breadth first search) to find disconnected subgraphs, and make a note of the size of each (count nodes). Then for the ones of size N that are larger than 12, you know you need Ceil(N/12) groups, then do a constrained flood fill for each group (flood fill until you reach 12 nodes (or some other number < 12, then pick the next free C). $\endgroup$ Commented Sep 30, 2022 at 8:10
  • $\begingroup$ @FilipMilovanović That would be a good started approach. In fact I did it. But the disadvantage is that it could leave us with several tiny group. E.g. with 3 groups smaller than 3 cells. Ideally they could be combined into one group $\endgroup$ Commented Oct 4, 2022 at 8:29

1 Answer 1

1
$\begingroup$

This looks very hard to me. I wouldn't be surprised if it is NP-hard.

If I had to solve it in practice, my first thought would be to try to solve it using a SAT solver or an ILP solver. I outline below how you could do that.

Given $k$, let's figure out whether there is a way to solve this using $k$ groups. If we can do that, we can use binary search over $k$ to find the smallest $k$ for which a solution exists (e.g., try $k=1,2,4,8,\cdots$ to find the first power of two for which a solution exists, then use binary search to narrow down exactly the minimum workable value of $k$).

Solving with a SAT solver

To solve this with a SAT solver, we need to formulate the problem in terms of boolean variables. I suggest introducing boolean variables $x_{c,i,j}$, where $c$ ranges over cells (locations) in the original matrix, $1 \le i \le 12$, and $1 \le j \le k$. The intent is that $x_{\cdot,12,j}$ should represent the $j$th group, i.e., $x_{c,12,j}$ should be true iff the $j$th group puts a 1 in cell $c$.

We need to ensure that the groups cover all C's. This can be done with the following constraints (clauses):

  • For each cell $c$ that contains a C, $x_{c,12,1} \lor \cdots \lor x_{c,12,k}$

We need to ensure that the groups don't cover any B. This can be done with the following constraints:

  • For each cell $c$ that contains a B and each $i,j$, $\neg x_{c,i,j}$

We need to ensure that each group has at most 12 1's. This can be done as follows:

Finally, we need to ensure that each group is connected. This is the hardest, but can be done as follows. The idea is that we'll grow a group, starting from a single cell (say $c_0$) and then expanding it; then $x_{\cdot,i,j}$ will be true for all cells with a 1 that are at most Manhattan distance $\le i$ from cell $c_0$. This can be expressed in SAT as follows:

  • For each $j$, exactly one of $x_{\cdot,1,j}$ is true. This is a cardinality/pseudo-boolean constraint; see above for how to enforce it.

  • $x_{\cdot,i,j}$ contains at least as many cells as $x_{\cdot,i-1,j}$, i.e., for each $i,j,c$ with $i>1$, $x_{c,i-1,j} \implies x_{c,i,j}$.

  • $x_{\cdot,i,j}$ is grown from $x_{\cdot,i-1,j}$ by adding only neighbors of cells in $x_{\cdot,i-1,j}$, i.e., for each $i,j,c$ with $i>1$, we have $$x_{c,i,j} \implies (x_{c,i-1,j} \lor x_{c_L,i-1,j} \lor x_{c_R,i-1,j} \lor x_{c_U,i-1,j} \lor x_{c_D,i-1,j})$$ where $c_L,c_R,c_U,c_D$ are the four cells that are adjacent to $c$.

  • It may be helpful to add the extra constraint that $x_{\cdot,i,j}$ has at most 12 true values, for each $i,j$.

Finally, take the conjunction of all of these constraints, hand them to an off-the-shelf SAT solver (I like Z3Py), and ask it whether it can find any satisfying assignment. If it can, then you have found a solution using $k$ groups. If it can't, then you know there is no solution using $k$ groups.

Solving with an ILP solver

Another option is to use an ILP solver. Cardinality constraints are easier to express in an ILP solver, and boolean constraints are slightly messier but can all be done (see Express boolean logic operations in zero-one integer linear programming (ILP)), so you could do this with ILP instead of SAT. I don't know which will be more effective. You could try both if necessary.

Here's how this looks, for your particular case. We have 0-or-1 integer variables $x_{c,i,j}$, i.e., they are all marked integer and we add inequalities $0 \le x_{c,i,j} \le 1$. Now let's walk through the constraints (linear inequalities).

We need to ensure that the groups cover all C's. This can be done with the following inequalities:

  • For each cell $c$ that contains a C, $x_{c,12,1} + \cdots + x_{c,12,k} \ge 1$.

We need to ensure that the groups don't cover any B. This can be done with the following constraints:

  • For each cell $c$ that contains a B and each $i,j$, $x_{c,i,j} = 0$.

We need to ensure that each group has at most 12 1's. This can be done as follows:

  • $\sum_c x_{c,12,j} \le 12$

Finally, we need to ensure that each group is connected. Following a similar idea as before, this can be expressed as an ILP as follows:

  • For each $j$, $\sum_c x_{c,1,j} = 1$.

  • For each $i,j,c$ with $i>1$, $x_{c,i-1,j} \le x_{c,i,j}$.

  • For each $i,j,c$ with $i>1$, we have $$x_{c,i,j} \le x_{c,i-1,j} + x_{c_L,i-1,j} + x_{c_R,i-1,j} + x_{c_U,i-1,j} + x_{c_D,i-1,j}$$ where $c_L,c_R,c_U,c_D$ are the four cells that are adjacent to $c$.

  • It may be helpful to add the extra constraint that $\sum_c x_{c,i,j} \le 12$, for each $i,j$.

Finally, take all of these linear inequalities, hand them to an off-the-shelf ILP solver (Gurobi?), and ask it whether it can find any solution. If it can, then you have found a solution using $k$ groups. If it can't, then you know there is no solution using $k$ groups.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.