# Generating all legal starbattle grids

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.

Here is an example of 10 x 10 starbattle puzzle where k = 2.

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.

• There are probably too many legal grids to generate all of them. Perhaps you would like instead to sample a grid? – Yuval Filmus Oct 9 '17 at 8:29
• In reality I doubt I would ever use, or attempt to generate them all. However I would like to have a way to systematically make them that guarantees uniqueness (as compared to my randomized method). Ideally this will all be stuck in a python generator where I can just pull the next puzzle when it is needed. – Robert Oct 9 '17 at 8:35
• What is the role of the thick vs thin lines? How do they affect what counts as a valid solution? Are two cells separated by a thick line not considered adjacent, or something? – D.W. Oct 10 '17 at 3:50
• Thin lines simply define the boxes. The thick lines define the boundaries of the regions. As per the rules there must be k stars in each row, column and region. They do not affect the adjacency of the cells. You can try it out here to get a better feel for it. starbattle-puzzle.com/play-online – Robert Oct 10 '17 at 9:32