I am trying to generate a type of logic puzzle called starbattles. The puzzles consist of an nxn grid that is divided into n distinct regions. The rules of the puzzle are to place stars in the grid such that there are k stars in each column, row, and region of the puzzle. No stars may be adjacent to one another either vertically, horizontally, or diagonally.
I have been trying to come up with an iterative way of generating all potential starbattle grids, on which I can then use a backtracking based solving algorithm I wrote to verify that there exists a solution and that solution is unique, to confirm that a legal puzzle has been created. I am at a loss for how I can generate more that a small subset of all possible region divisions.
At the moment my approach consists of picking n random points on the grid, and then using a randomized flood fill to allocate the regions. This works and I can generate legal puzzles using it, however I feel there has to be a systematic way of generating all legal grids.