Battleship

Solitaire Battleship hides a fleet in a grid. A whole fleet of ships lies concealed on a square grid, each ship straight and one cell wide, and the solver must raise it from a handful of clues: how many ship cells sit in each row and each column, a few squares revealed in advance as ship or as water, and the roster of the fleet itself, so many ships of each length. Two rules govern every placement. Ships do not overlap, and ships do not touch, not even at a corner, so each is ringed by water. Meuffels and den Hertog gave the puzzle two integer programmes in the INFORMS Transactions on Education column, a cell-based one and a ship-based one, and showed the second to be far the faster. The ship-based model is the one worth knowing, because it turns a fiddly drawing problem into a clean question about which placements may coexist.

The position

The grid in Figure 24.1 is six by six. The fleet is one cruiser of length three, two destroyers of length two, and three single-cell submarines: ten ship cells in all. The numbers down the right give the ship cells in each row, $3, 1, 2, 1, 1, 2$ from the top, and the numbers along the bottom give them by column, $4, 0, 2, 1, 1, 2$ from the left. Three squares are revealed at the start: the two marked with water near the top and left, and the single ship cell shown in copper. Those three are exactly enough to force one fleet and no other.

The model

Variables

The ship-based model never reasons about a cell in isolation; it reasons about whole ships. Enumerate every way a single ship of a given length can sit on the grid, horizontally or vertically, in bounds. Each such placement is a fixed set of cells, and to it we attach a binary variable that is $1$ when that placement is used. A length-one ship has one placement per square; a longer ship has one per starting square and orientation that fits.

Constraints

Let the placements of length $\ell$ carry variables $y_g$, and let $x_{rc}$ stand for the number of chosen placements that cover cell $(r, c)$, a sum of placement variables. The fleet roster fixes how many placements of each length are used: $$\sum_{g \,\text{of length}\, \ell} y_g = S_\ell .$$ The row and column clues are covering constraints on the cells: $$\sum_{c} x_{rc} = R_r, \qquad \sum_{r} x_{rc} = C_c .$$ The no-touching rule is the elegant part. Two ship cells overlap or touch, in any direction including diagonally, exactly when both lie inside some two-by-two window of the grid. So it is enough to demand that across every two-by-two window, at most one placement contributes a cell: $$\sum_{g \,:\, g \,\cap\, W \neq \varnothing} y_g \le 1 \qquad \text{for each } 2 \times 2 \text{ window } W .$$ That single family of inequalities rules out overlap and every kind of contact at once. Finally the revealed squares fix their cells, $x_{rc} = 1$ for a given ship cell and $x_{rc} = 0$ for given water. There is no objective; any feasible point is a legal fleet.

The solver

The model goes to CP-SAT. The placements are built once, in Python, before the solver runs; this is the preprocessing the ship-based model trades for its small constraint count.

from ortools.sat.python import cp_model

def placements(R, C, length):
    cells = []
    for r in range(R):
        for c in range(C):
            row = [(r, c + k) for k in range(length)]
            col = [(r + k, c) for k in range(length)]
            if all(y < C for _, y in row):
                cells.append(frozenset(row))
            if length > 1 and all(x < R for x, _ in col):
                cells.append(frozenset(col))
    return cells

def battleship(R, C, fleet, rows, cols, ships, water):
    m = cp_model.CpModel()
    grids = []
    for length, count in fleet.items():
        opts = placements(R, C, length)
        group = [(cs, m.NewBoolVar("")) for cs in opts]
        m.Add(sum(v for _, v in group) == count)
        grids += group
    x = {(r, c): [] for r in range(R) for c in range(C)}
    for cells, v in grids:
        for cell in cells:
            x[cell].append(v)
    x = {cell: sum(vs) for cell, vs in x.items()}
    for r in range(R):
        m.Add(sum(x[r, c] for c in range(C)) == rows[r])
    for c in range(C):
        m.Add(sum(x[r, c] for r in range(R)) == cols[c])
    for r in range(R - 1):
        for c in range(C - 1):
            win = {(r, c), (r, c + 1), (r + 1, c), (r + 1, c + 1)}
            m.Add(sum(v for cells, v in grids if cells & win) <= 1)
    for cell in ships:
        m.Add(x[cell] == 1)
    for cell in water:
        m.Add(x[cell] == 0)
    s = cp_model.CpSolver()
    if s.Solve(m) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    return {cell for cell in x if s.Value(x[cell])}

On this position the solver returns the single fleet drawn in Figure 24.1: the cruiser standing in the left column, a destroyer lying across the top, a second destroyer standing at the right edge, and the three submarines scattered so that no two ships touch. The three revealed squares admit no other arrangement; the solution is unique.

Cells against ships

The same puzzle has a second integer programme, the one Meuffels and den Hertog set the ship-based model against. Its cell-based rival gives every square one of seven symbols, water or one of six ship pieces (a submarine, the four kinds of end, and a middle), and spends a thicket of implication constraints stitching those pieces into straight ships: a left end must be followed by a middle or a right end, and so on. It works, but on a thirty-by-twenty grid it did not finish in ten hours, while the ship-based model solved the same board in minutes. The lesson generalises past Battleship. When the legal objects of a puzzle are themselves constrained shapes, it is often cheaper to enumerate the shapes up front and let the solver choose among them than to rebuild each shape from cells inside the search. The placement that costs a list at the start saves a forest of constraints at the end. The same models, run twice and asked whether a second solution exists, are what let their authors strip a puzzle of redundant clues and certify that exactly one fleet remains, which is the test every Battleship in this book must pass.

Sources. The two integer programmes, and the two-by-two window that forbids ships from touching, follow W. J. M. Meuffels and D. den Hertog, Puzzle—Solving the Battleship Puzzle as an Integer Programming Problem, INFORMS Transactions on Education volume $10$, number $3$ ($2010$), pages $156$–$162$. Solitaire Battleship was devised by Jaime Poniachik and first appeared in $1982$ in the Argentine magazine Humor & Juegos; it reached a wider public at the inaugural World Puzzle Championship in New York in $1992$. The position solved here is a re-authored instance with a unique solution.