Finding all partitions of a grid into k connected components

Question

I am working on floor planing on small orthogonal grids. I want to partition a given $m \times n$ grid into $k$ (where $k \leq nm$, but usually $k \ll nm$) connected components in all possible ways so that I can compute a fitness value for each solution and pick the best one. So far, I have the fitness evaluation at the end of the algorithm, no branch-and-bound or other type of early-termination, since the fitness function is specified by users and usually requires the complete solution.

My current approach to listing all possible grid partitions into connected components is quite straight forward and I am wondering what optimizations can be added to avoid listing duplicate partitions? There must be a better way than what I have right now. I know the problem is NP, but I would at like to push my algorithm from brute-force to a smart and efficient approach.

Overview

For better visualization and description I will reformulate the task to an equivalent one: paint the grid cells using $k$ colors so that each color builds a single connected component (with respect to 4-neighborhood) and of course all grid is completely painted.

My approach so far:

1. Generate all seed scenarios. A seed scenario is a partial solution where each color is applied to a single cell only, the remaining cells are yet empty.
2. Collect all possible solutions for each seed scenario by expanding the color regions in a DFS manner.
3. Filter out duplicate solutions with help of a hash-table.

Seed scenarios

I generate the seed scenarios as permutations of $k$ unique colors and $mn-k$ void elements (without repetition of the voids). Hence, the total number is $(nm)! / (mn-k)!$ For example, for a $1 \times 4$ grid and colors ${0, 1}$ with void denoted as $\square$ the seed scenarios are:

• $[0 1 \square \square]$
• $[0 \square 1 \square]$
• $[0 \square \square 1]$
• $[1 0 \square \square]$
• $[1 \square 0 \square]$
• $[1 \square \square 0]$
• $[\square 0 1 \square]$
• $[\square 0 \square 1]$
• $[\square 1 0 \square]$
• $[\square 1 \square 0]$
• $[\square \square 0 1]$
• $[\square \square 1 0]$

Seed growth / multicolor flood-fill

I assume the painting to be performed in a fixed ordering of the colors. The seed scenario always comes with the first color set as the current one. New solutions are generated then either by switching to the next color or by painting empty cells by the current color.

//PSEUDOCODE
buffer.push(seed_scenario with current_color:=0);
while(buffer not empty)
{
    partial_solution := buffer.pop();
    if (partial_solution.available_cells.count == 0)
        result.add(partial_solution);
    else
    {
        buffer.push(partial_solution.nextColor()); //copy solution and increment color
        buffer.pushAll(partial_solution.expand()); //kind-of flood-fill produces new solutions
    }
}

partial_solution.expand() generates a number of new partial solutions. All of them have one additional cell colored by the current color. It examines the current region boundary and tries to paint each neighboring cell by the current color, if the cell is still void.

partial_solution.nextColor() duplicates the current partial solution but increments the current painting color.

This simple seed growth enumerates all possible solutions for the seed setup. However, a pair of different seed scenarios can produce identical solutions. There are indeed many duplicates produced. So far, I do not know how to take care of that. So I had to add the third step that filters duplicates so that the result contains only distinct solutions.

Question

I assume there should be a way to get rid of the duplicates, since that is where the efficiency suffers the most. Is it possible to merge the seeds generation with the painting stage? I started to thing about some sort of dynamic programming, but I have no clear idea yet. In 1D it would be much easier, but the 4-connectivity in a 2D grid makes the problem much harder. I tried searching for solutions or publications, but didn't find anything useful yet. Maybe I am throwing in the wrong keywords. So any suggestions to my approach or pointers to literature are very much appreciated!

Note

I found Grid Puzzle Split Algorithm, but not sure if the answers can be adapted to my problem.

Further thoughts (update #1)

I started to think in the following direction. If there are two connected components, their union will be connected as well. So I could proceed in a divide-and-conquer way:

1. Generate all distinct 2-partitions (connectivity condition must hold of course).
2. For each solution from (1) paint one component with one of the available colors and recursively apply (1) to the second component using the remaining colors. Terminate each branch once all colors have been used for at least one cell.

This is a very rough idea, but I believe it should avoid duplicates. I will investigate further if I can prove it. But still, how to generate all distinct 2-partitions of a 2D grid efficiently remains an open question for me.

Answer 1

Two components

Here is an algorithm you can use to enumerate the ways to partition any graph (including a grid) into $k=2$ connected components, say a red component and a blue component. Let's define the "size" of such a partition to be the number of vertices in the red component.

The algorithm: generate all partitions of size 1; then generate all partitions of size 2; then all partitions of size 3; and so on.

Given all partitions of size $s$, you can enumerate all partitions of size $s+1$ as follows: pick a partition of size $s$, let $R$ denote the set of red vertices in that partition, pick a blue vertex $v \notin R$ that is adjacent to some red vertex in $R$; construct a new partition of size $s+1$ with red vertices $R' = R \cup \{v\}$ and blue vertices $V \setminus R'$; and test whether the blue vertices form a connected component.

The base case is that you can easily enumerate all partitions of size 1: each is just a single vertex, and you can choose any one vertex you want. (If you consider two partitions equivalent if one can be obtained from the other by swapping colors, and you only want to enumerate partitions up to equivalence, then it suffices to enumerate only those partitions where the first vertex is colored red. In that case, there is only one partition of size 1: the first vertex is red and the rest are blue.)

To make this run efficiently, I suggest you store a hashtable of all partitions of size $1$, a hashtable of all partitions of size $2$, and so on. The hash function will map a partition to a unique hashcode, by hashing the set of red vertices. This way you can efficiently test whether a partition generated using the above procedure is new or a duplicate, and avoid adding duplicates more than once. This will also allow you to enumerate all partitions of a given size.

To help make it more efficient to enumerate all vertices that are adjacent to some red vertex, I suggest you store each subset as a set of red vertices on the fringe and a set of red vertices on the interior. (The "fringe" are the red vertices in $R$ that are adjacent to at least one blue vertex; the interior are the rest of the red vertices.) This makes it easy to enumerate over all blue vertices that are adjacent to some red vertex in $R$ (by traversing the fringe and enumerating their neighbors).

With these methods, you can enumerate all such connected components in at most $O(N^2 2^N)$ time, where $N$ is the number of vertices in the graph ($N=mn$ in your example), and probably substantially less in practice.

Multiple components

We can generalize this to handle an arbitrary number $k\ge 2$ of connected components, as follows. First, pick a partition of the graph into 2 components, one red and one blue. Then, pick a way to partition the blue component into two connected components, say one violet and one cyan. Repeat $k-1$ times, in each step partioning the last component, until you have $k$ components. If you at each stage you enumerate over all choices, at the end you will have enumerated all ways to partition the graph into $k$ connected components.

(If you consider two partitions equivalent if one can be obtained from the other by permuting the colors, then it suffices to enumerate the ways to partition into two components up to equivalence.)

The running time of this algorithm will be very bad: it might be close to $k^N$. So, this will only be useful when the number $N$ of vertices in the graph is very small.