Starbattle

Aboard is ruled into a grid and carved into regions, and stars are to be set on it. The rule is a quota repeated three ways: each row, each column, and each region must hold the same fixed number of stars, one in the gentle version and two in the one the newspapers print. To that is added a separation rule, that no two stars may touch, not even at a corner. The board comes with the regions already drawn, and from the quotas and the separation the unique arrangement of stars is to be found. It is the easiest of the apps in Hartmann’s second collection, and a tidy meeting of constraints already seen elsewhere in this book.

Quotas and separation

The quotas are plain sums. The separation is the same observation that placed ships in the Battleship chapter: two cells touch, orthogonally or diagonally, exactly when they share a two-by-two square, so forbidding two stars in any two-by-two block forbids them from touching at all.

Variables

One binary to a cell, $$x_{ij} = 1 \iff \text{a star stands on cell } (i, j) .$$

Constraints

Let $S$ be the quota, one or two. Each row, column and region carries exactly $S$ stars, and each two-by-two window carries at most one: $$\sum_j x_{ij} = S \ (\forall i), \qquad \sum_i x_{ij} = S \ (\forall j), \qquad \sum_{(i,j) \in A_k} x_{ij} = S \ (\forall k),$$ $$x_{ij} + x_{i,j+1} + x_{i+1,j} + x_{i+1,j+1} \le 1 ,$$ the last for every $i, j$ in range, with $A_k$ the cells of region $k$. There is nothing to optimise; a well-drawn board has one arrangement meeting all four.

from ortools.sat.python import cp_model

def solve_starbattle(grid, S):
    n = len(grid)
    regions = {}
    for i in range(n):
        for j in range(n):
            regions.setdefault(grid[i][j], []).append((i, j))
    m = cp_model.CpModel()
    x = {(i, j): m.NewBoolVar("")
         for i in range(n) for j in range(n)}
    for i in range(n):
        m.Add(sum(x[i, j] for j in range(n)) == S)
        m.Add(sum(x[j, i] for j in range(n)) == S)
    for cells in regions.values():
        m.Add(sum(x[c] for c in cells) == S)
    for i in range(n - 1):
        for j in range(n - 1):
            m.Add(x[i, j] + x[i, j + 1]
                  + x[i + 1, j] + x[i + 1, j + 1] <= 1)
    s = cp_model.CpSolver()
    s.Solve(m)
    return {c for c in x if s.Value(x[c])}

The grid passed in carries a letter per cell, its region; the solver reads the regions off it. Here is a six-by-six board with one star to a line and six regions, lettered A to F: $$\begin{array}{cccccc} C & C & A & A & A & A \\ B & C & C & C & A & E \\ B & D & F & C & A & E \\ B & D & F & C & A & E \\ D & D & F & F & F & E \\ D & F & F & E & E & E \end{array}$$ With $S = 1$ the four rules leave exactly one placement, no two stars in contact, one in every row, column and region: $$\begin{array}{cccccc} \cdot & \cdot & \cdot & \cdot & \star & \cdot \\ \star & \cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \star & \cdot & \cdot \\ \cdot & \star & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot & \star \\ \cdot & \cdot & \star & \cdot & \cdot & \cdot \end{array}$$ A count confirms the placement is alone. The harder game the puzzle pages favour, sometimes billed as Two Not Touch, only raises the quota to $S = 2$ on a larger board; the model does not change a line, since $S$ was a parameter from the start, and the separation and region rules carry over untouched.

What the puzzle adds over the placement puzzles earlier in the book is the region quota, an exact count over an irregular set of cells, sitting beside the orderly row and column counts. The board’s drawing is therefore part of the data, not decoration: redraw the regions and the same grid poses a different puzzle. With Starbattle the two collections of smartphone apps are nearly all accounted for, the lone holdout a knight’s tour, whose subtour-elimination model the travelling-salesman chapters have already told.

Sources. The Starbattle app is modelled by Sönke Hartmann, Puzzle—More Logic Puzzle Apps Solved by Mathematical Programming, INFORMS Transactions on Education volume $20$, number $1$ ($2019$), pages $49$–$55$, which gives the row, column, region and two-by-two constraints used here. The six-by-six board and its regions are the present chapter’s own, drawn so that the four rules admit exactly one placement, which an independent solution count confirms. The two-by-two separation device is the one used for ships in this book’s Battleship chapter. The puzzle is widely sold as Star Battle or Two Not Touch; Hartmann credits the app to Falk Kühnel, Alexander Kylburg and Patrick Albertini of Paragraph Eins (Germany).