Algorithm to split a grid of squares into equally sized sections

Question

I have a grid of squares, let's say 12x12.

I want to split this grid into equal sections of 8 squares, which is 18 total sections.

There is no requirement for sections being convex or compact, and the less uniform the better.

First attempt

I pick a square to start a section. First the corners, then the edges, then the rest, (because it tends to give better and faster results). To generate the section, I iteratively and randomly pick neighboring squares to the section until there are 8 squares in the section. I then use an algorithm (similar to flood fill) to determine how many "holes" there are left in the grid.

If the number of holes is not one (if the section created a space that is not able to be filled by a section), the section is recreated, and repeat until the number of holes is one. This repeats for every section created. As you can imagine, this gets pretty slow when the grid size and section size is increased. Is there a faster and more elegant way to do this?

Answer 1

The requirement "the less uniform the better" is pretty vague, so there can be several different algorithms or heuristics to solve this task, all with different pros and cons. Hence I recommend you define some kind of metrics for non-uniformity first, to make the task less arbitrary.

Said that, the most simple algorithm which comes into my mind is the following:

1. Start with some trivial valid tiling. In the given example, using 2x4 tiles would work. Another idea (thanks to @KrisVanBael) is to combine squares by going from one row from left to right, then the next row from right to left, just like in the old arcade game centipede. This should be straightforward and O(N), where N = total number of squares. Here is such an example for tiles of size 5:

2. Apply modifications on this tiling of the following form: Randomly pick two neighbored tiles with at least two touching squares. Add one of those squares from tile 1 to tile 2 and the other one from tile 2 to tile 1. Or more general, take the space occupied by two neighbored tiles and fill it with two new tiles of the same size, but using different squares than before. Make sure this results in a configuration where the squares of each tile are still connected to each other (otherwise undo the modification).

For the above example, this could look like this:

Note modifications of this type can be implemented in an O(1) manner.

Now repeat step 2 until your metrics for non-uniformity reaches a certain threshold, or until your program reaches a certain time limit. Note each modification will keep the tiling always valid, so you can stop the algorithm whenever you want, always with a solution to return.