Star Battle

Star Battle is an object placement logic puzzle where solvers must place stars in a grid with marked regions such that each row, column, and region has a specified number of stars without the stars touching each other, even diagonally.

Background

Star Battle was invented by Hans Eendebak as a new genre debuting at the 2003 World Puzzle Championships.[1]

Puzzle Application

Star Battle grids often use rectangular grids that are subdivided into regions. The general premise involves placing stars such that two squares with a star do not share an edge or vertex. The number of stars per row, column, and region may vary and are thus often referred to as an N-Star Battle where N is the stars per row, column, or region. The most common version is a 2-Star Battle on a 10x10 grid.

Strategy

Solve strategies often involve marking squares that have stars as well as regions that do not have stars. This is useful to note squares that can not have stars due to the adjacency rules or sometimes the counts per row, column, or region.

The shapes of smaller regions or linear regions can help eliminate locations of stars from the start or even locate locations of stars. Due to the adjacency and count rules respectively, a 2x2 region can have at most one star, and a region all in the same row prevents stars from appearing in any other square in the same row (and vice versa, swapping rows for columns).

As spaces that do not contain stars are marked, it may be possible to divide regions into regions of size 2x2 of less, each of which may only contain at most one star as well. In particular, if you know that a star must be in one of two adjacent positions in a row, then you may rule out four squares having stars: the same row positions in the two adjacent columns. Similarly, if you know that a star must be in one of three adjacent positions in a row, then you may rule out two squares having stars. And vice versa, swapping rows for columns.

If N regions, when taken together, span more than N rows or columns, then the additional squares cannot contain any stars. Conversely if N regions, when taken together, span less than N rows or columns, then the remaining squares cannot contain any stars.

One interesting mathematical fact is that for a 4N x 4N grid, with N stars, there are only two solutions. (Incidentally, one of the 2003 WPC puzzles turned out to be this, which is understandable given that the theory had not been explored yet.)

Notable Examples

Played Straight

• Battle of the Network Stars (MIT Mystery Hunt 2019) (web) - Disguised version of Star Battle in which the regions are based on the network starred.

Notable Twists

• ⭐ BATTLE STAR ⭐ (Teammate Hunt 2020) (web) - Described as a "reverse star battle" in which solvers mark regions to satisfy star battle constraints and other logic puzzle rules.
• Make Your Own Star Battle (Galactic Puzzle Hunt 2023) (web) - Part of the "make your own" puzzles involving creating Star Battle boards, some of which not having unique solutions.