Creation/computation of "Two not touch" puzzles

Question

This is a mathematical and algorithmic question, so I hope it is not flagged for failing to be a pure mathematical question.

The puzzle "Two not touch" (or Star Battle) consists of a $10 \times 10$ grid array fully tiled with irregularly shaped contiguous regions, for instance:

The task is to place (20) stars in the grid cells such that:

• There are exactly two stars in each row
• There are exactly two stars in each column
• There are exactly two stars in each contiguous tiled region
• No two stars "touch," that is, are adjacent vertically, horizontally, or on diagonally adjacent squares

My question isn't about how to solve such a puzzle. It is instead how to algorithmically/mathematically create a valid puzzle that has a (single) unique solution, as such puzzles ensure.

I have little doubt that the first step is to randomly assign two cells (for "virtual stars"... where the solution stars must fall) in each row and each column in a blank (un-tiled) grid, obeying the "not touch" constraint. This is quite a simple algorithm.

Next comes drawing the tiled regions. It is fairly straightforward to draw contiguous regions that bound just two of the virtual stars.

Question: How does one ensure that the tiled regions admit just a single unique puzzle solution?

Answer 1

Here is an outline of an algorithm which would generate such grids, although I make no claims as to how efficient it might be.

1. Start with an empty $n \times n$ grid.

2. "Seed" the grid by assigning some of the cells a value between 1 and $n$.

3. Determine whether the grid allows a solution to an "Expansionist Star Battle", which is Star Battle but you also have to determine the regions as you solve it (where rather than depicting the regions using walls, all cells with the same value are part of the same region).

4. From step 3, identify any backbone components of the solution.

5. If the backbone is the entire grid (both regions and stars), then you have a unique solution and you can erase the stars and the remaining grid is the puzzle.

6. Add the backbone components to the grid. Also fix some of the region assignments in the found solution.

7. Take this new grid and go back to step 3.

8. If at any point you have no solutions, or if you have assigned every cell to a region and you don't have a unique solution, then erase some of the cells and go back to step 3.

This algorithm relies on having a reasonably efficient method for (a) solving "Expansionist Star Battle" (though not necessarily proving its uniqueness) and (b) identifying any fixed parts of its solution, both of which are probably computationally quite hard. I suspect that you can have a setup that starts by doing everything quite approximately and heuristically (e.g. it applies some strict deduction to find the forced parts of the solution, some kind of greedy approach to prove that a solution exists at all, and assigns cells to regions based on some randomised closeness criteria), then when it starts hitting a point where it's not making progress switches to a more sophisticated constraint programming method.