The Gunport Problem

Lay dominoes on a board, two cells at a time, until not one more will fit; the single cells left bare are the gunports. The name is Bill Sands’s, who saw in the holes the ports of a fortress wall through which a cannon might fire, and the game is to leave as many as the board allows. A packing in which no further domino fits is one whose empty cells never sit side by side, for two adjacent holes would themselves admit a domino. Fewer dominoes mean more holes, so to maximize the gunports is to cover the board as sparingly as a legal packing permits. Gardner carried the puzzle to a wide audience, and Chlond and Bosch made it a study in something an integer programmer learns slowly: that the same problem, written four different ways, can run in seconds or not finish in a week.

The puzzle

Recast the holes as tiles. Cover every cell of the $m \times n$ board with either a domino, lying across two neighbouring cells, or a monomino, a single cell standing for a gunport, and forbid two monominoes from touching edge to edge. The monominoes are exactly the holes of a maximal domino packing, and the puzzle is to place as many of them as possible. With $H$ holes the board carries $(mn - H)/2$ dominoes, so the most holes and the fewest dominoes are one and the same target.

How many holes a board allows has a clean partial answer. Sands proved that when either side is a multiple of three the holes number exactly $mn/3$, laid out by a simple repeating stripe. For the remaining boards Murray Pearce conjectured the rest: when $m$ and $n$ leave the same nonzero remainder on division by three the optimum is $(mn-4)/3$ holes, and when their remainders differ it is $(mn-2)/3$. The conjecture has resisted proof but holds wherever it has been checked, and the program below is one way to check it.

The model

Variables

Three families of placements tile the board. For a horizontal domino let $h_{rc} = 1$ when its left cell is $(r, c)$; for a vertical one let $v_{rc} = 1$ when its top cell is $(r, c)$; and let $\mu_{rc} = 1$ when cell $(r, c)$ is a monomino, a hole.

Cover, and keep the holes apart

Every cell is filled exactly once, by the monomino sitting on it or by one of the up to four dominoes that could reach across it: $$\mu_{rc} + h_{rc} + h_{r,\,c-1} + v_{rc} + v_{r-1,\,c} = 1 ,$$ each domino term present only where it fits inside the board. The packing is maximal precisely when no two holes are neighbours, which two short inequalities enforce along each axis: $$\mu_{rc} + \mu_{r,\,c+1} \le 1, \qquad \mu_{rc} + \mu_{r+1,\,c} \le 1 .$$ Maximizing $\sum_{rc} \mu_{rc}$ then asks for the most holes, and that is the whole model. The naming is the lesson: an earlier formulation indexes a separate variable for each of $\lfloor mn/2 \rfloor$ possible dominoes and crawls, unable even to finish an eight-by-eight board, while this monomino view, with a handful of variables per cell, clears far larger boards in seconds. Same puzzle, better coordinates.

The solver

from ortools.sat.python import cp_model

def max_holes(m, n):
    M = cp_model.CpModel()
    mono = {(r, c): M.NewBoolVar("")
            for r in range(m) for c in range(n)}    # a hole at (r, c)
    h = {(r, c): M.NewBoolVar("")
         for r in range(m) for c in range(n - 1)}   # domino (r,c)-(r,c+1)
    v = {(r, c): M.NewBoolVar("")
         for r in range(m - 1) for c in range(n)}   # domino (r,c)-(r+1,c)
    for r in range(m):
        for c in range(n):
            cover = [mono[r, c]]
            if c < n - 1: cover.append(h[r, c])
            if c > 0:     cover.append(h[r, c - 1])
            if r < m - 1: cover.append(v[r, c])
            if r > 0:     cover.append(v[r - 1, c])
            M.Add(sum(cover) == 1)
            if c < n - 1: M.Add(mono[r, c] + mono[r, c + 1] <= 1)
            if r < m - 1: M.Add(mono[r, c] + mono[r + 1, c] <= 1)
    M.Maximize(sum(mono.values()))
    s = cp_model.CpSolver()
    s.Solve(M)
    return round(s.ObjectiveValue())

The five-by-five board admits seven holes, the example Sands drew; the seven-by-seven admits fifteen, shown in Figure 29.1; and the eleven-by-eleven, the largest the article pictures, admits thirty-nine. Each agrees to the cell with the Sands and Pearce counts, the program confirming on every board tested what the conjecture only promises in general.

Reading the reformulation

The article’s real subject is not the holes but the coordinates. One model asks, for every cell and every candidate domino, whether that domino lies there, and drowns; another asks only, for every cell, which of a few local tiles covers it, and flies. The variables encode the same boards and the same optimum, yet one search tree is searchable and the other is not. Choosing what the binary variables stand for, before writing a single constraint, is often the difference between a model that solves and one that merely compiles, and the gunport puzzle, harmless on a small board and intractable on a large one, is a vivid place to feel the gap.

Sources. The formulations follow Martin J. Chlond and Robert Bosch, The Gunport Problem, INFORMS Transactions on Education volume $6$, number $2$ ($2006$), pages $37$–$43$. The puzzle is Bill Sands’s, The Gunport Problem, Mathematics Magazine volume $44$ ($1971$), pages $193$–$196$, popularised by Martin Gardner (collected in The Colossal Book of Short Puzzles and Problems, Norton, $2006$); the closed-form counts for boards with no side divisible by three are Murray Pearce’s conjecture, reported there. The hole counts $7$, $15$, and $39$ for the five-, seven-, and eleven-square boards, and their agreement with the Sands–Pearce formula across every board tested, are reproduced here. The monomino model maximizes the holes; the article’s prose for this final formulation says “minimized” where its own model file, and the puzzle, maximize, a slip corrected silently above.