Finding all partitions of a grid into k connected components


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 computation 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.