1. Introduction#

Star Battle is a logic puzzle defined as follows: given an $m×n$ grid divided into regions, players must fill the grid with stars that satisfy the following requirements:

• Each row, column, and region contains a specified number of stars.
• No two stars can be adjacent (in any direction).

Below is an example of a 10x10 Star Battle puzzle, with 2 stars in each row, column, and region

2. Modeling the puzzle#

Some symbols used in this problem

• $n_R$ is the number of rows in the grid
• $n_C$ is the number of columns in the grid
• $n$ is the number of stars to be placed in each row, column, and region
• $S$ is the set of regions
• $C_s$ is the set of cells $(i, j)$ belonging to region $s \in S$
• $N_{ij}$ is the set of neighboring cells of cell $(i, j)$ (including diagonals)
• $f_{ij}$ is the number of neighboring cells of cell $(i, j)$ (including diagonals)

2.1. Decision variables#

For each cell $(i, j)$ in the grid, we define a variable $x(i,j)$ such that

$$x(i, j) = \begin{cases} 1 & \text{if cell } (i, j) \text{ contain a star } \\ 0 & \text{otherwise} \end{cases}$$

2.2. Constraints#

• Each row contains exactly $n$ stars

$$\sum\limits_{j = 0}^{n_C - 1}{x(i, j)} = n, \\ \forall 0 \leq i < n_R$$

• Each column contains exactly $n$ stars

$$\sum\limits_{i = 0}^{n_R - 1}{x(i, j)} = n, \\ \forall 0 \leq j < n_C$$

• Each region contains exactly $n$ stars

$$\sum\limits_{\forall (i, j) \in C_s}{x(i, j)} = n, \\ \forall s \in S$$

• No two stars can be adjacent (in any direction).

  This condition can be rephrased as follows: if cell $(i,j)$ is filled with a star, then all cells adjacent to cell $(i,j)$ cannot be filled with a star.

  $$x(i, j) = 1 \Rightarrow \sum\limits_{\forall (p, q) \in N_{ij}}{x(p, q)} = 0, \\ \forall 0 \leq i < n_R, 0 \leq j < n_C$$

  Linearizing the above condition using geometric method, we obtain the following constraint, which is the one used in the model.

$$f_{ij} \cdot x(i, j) + \sum\limits_{\forall (p, q) \in N_{ij}}{x(p, q)} \leq f_{ij}, \\ \forall 0 \leq i < n_R, 0 \leq j < n_C$$

2.3. Objective function#

This problem does not have an objective function, as we are not aiming to minimize or maximize any value. Our goal is simply to find a feasible solution. Technically, when programming, we can set the objective function to a constant (I often choose 0)

3. Conclusion#

For more Star Battle puzzles and variations, please refer to Krazydad. The Python code for Star Battle modeling is available at Tung-hehe.

Happy modeling!