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. 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.

  • 1
    $\begingroup$ There are probably too many legal grids to generate all of them. Perhaps you would like instead to sample a grid? $\endgroup$ – Yuval Filmus Oct 9 '17 at 8:29
  • $\begingroup$ 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. $\endgroup$ – Robert Oct 9 '17 at 8:35
  • $\begingroup$ 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? $\endgroup$ – D.W. Oct 10 '17 at 3:50
  • $\begingroup$ 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 $\endgroup$ – Robert Oct 10 '17 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.