1. Introduction#

Galaxies is a logic puzzle described as follows: given a grid of squares with dots representing stars, player needs to divide the grid into regions called galaxies, satisfying the following conditions:

• The grid is completely covered by galaxies.
• Galaxies do not overlap.
• Each galaxy must and only contains one star in the center as its core.
• Each galaxy must be centrally symmetric with respect to the star in the center.

Reference: Wikipedia

Below is an example of a 10×18 Galaxies puzzle and its solution

2. Modeling the puzzle#

• $n_R$ is the number of rows in the grid
• $n_C$ is the number of columns in the grid
• $n_G$ is the number of galaxies (equal to the number of stars in the grid)
• $C_g$ is the set of cells with coordinates $(i, j)$ containing the centers of galaxy $g$
• $F_g$ is the set of cells that can possibly belong to galaxy $g$
• $P_{ijg}$ is the set of all paths from $(i, j)$ to the center of galaxy $g$

For example, in the figure below, with $g$ being the galaxy containing the black star, $C_g$ contains all cells in blue border rectangle, $F_g$ contains all cells in red border region and green line is a path from orange cell to the center of galaxy $g$.

• $V_p$ is the set of cells that belong to path $p$
• $n_p = |V_p|$ is the number of cells in path $p$

2.1. Decision variables#

For each cell $(i, j)$ in the grid and a galaxy $g$ ($0 \leq g < n_G$), we define a variable $x(i,j, g)$ such that

$$x(i, j, g) = \begin{cases} 1 & \text{if galaxy } g \text{ contains cell } (i, j) \\ 0 & \text{otherwise} \end{cases}$$

2.2. Constraints#

• The grid is completely covered by galaxies, and the galaxies do not overlap. These two constraints are equivalent to the following constraint: each cell in the grid must belong to, and only belong to, one galaxy.

$$\sum_{g = 0}^{n_G - 1}{x(i, j, g)} = 1, \\ \forall 0 \leq i < n_R, 0 \leq j < n_C$$

• Each galaxy contains its core

$$x(i, j, g) = 1, \\ \forall 0 \leq g < n_G, (i, j) \in C_g$$

• Each galaxy must be centrally symmetric with respect to the star in the center

$$x(i, j, g) = x(u_{ijg}, v_{ijg}, g), \\ \forall 0 \leq g < n_G, (i, j) \in F_g$$

Where $(u_{ijg}, v_{ijg})$ is the cell symmetric to cell $(i, j)$ with respect to the center of galaxy $g$

Note: The above conditions are sufficient to solve small Galaxies puzzles (7×7, 8×8, ...). However, when solving larger puzzles (10×10 or larger) we encounter a problem where the galaxy can be divided into many separate small pieces.

• The cells within a galaxy must be connected. This condition is equivalent to the following: for any two cells belonging to the same galaxy, there must exist at least one path between them such that all cells on this path also belong to that galaxy.

  To linearize this condition, we introduce additional intermediate variables $t_{ijgp}$ for each galaxy $g$, cell $(i, j) \in F_g$ and each path $p \in P_{ijg}$ satisfying

  $$t_{ijgp} = \begin{cases} 1 & x(u, v, g) = 1, \forall (u, v) \in V_p\\ 0 & \text{otherwise } \end{cases}$$

  In other words, the variable $t_{ijgp}$ equals 1 if cell $(i, j)$ is connected to the center of galaxy $g$ through path $p$. Using geometric method we can represent the variables $t$ through the variables $x$ by the following constraint:

  $$\begin{cases} \sum\limits_{(u, v) \in V_p}{x(u, v)} \geq n_p \cdot t_{ijgp} \\ \sum\limits_{(u, v) \in V_p}{x(u, v)} + 1\leq t_{ijgp} + n_p\\ \end{cases} \\ \forall 0 \leq g < n_G, (i, j) \in F_g, p \in P_{ijg}$$

  Finally, the original condition can be linearized as follows:

  $$x(i, j, g) \leq \sum\limits_{p \in P_{ijg}}{t_{ijgp}}, \\ \forall 0 \leq g < n_G, (i, j) \in F_g$$

• Additionally, to reduce the search space of the problem, we can add the condition that cells not in $F_g$ will not belong to galaxy $g$

$$x(i, j, g) = 0, \\ \forall 0 \leq g < n_G, (i, j) \notin F_g$$

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#

The highlight of this puzzle is the last two conditions, each of which has a different effect but shares a common point: if not carefully considered, we can easily overlook them. To avoid this situation, we need to think carefully about the problem and try solving different many cases to detect any issues (if any)

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

Happy modeling!