Algorithm to split a grid of squares into equally sized sections

I have a grid of squares, let’s say 12×12.

enter image description here

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

enter image description here

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.

enter image description here

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?