Losing Tic-Tac-Toe

Stan Wagon’s Problem of the Week 1416 shows six black squares on a $6 \times 6$ grid and asks you to read them as queens on a chessboard. No three of them lie on a common queen-line, where a queen-line means a row, a column, or a line at $45^\circ$. The configuration is stuck: put a queen on any of the thirty empty squares and some queen-line acquires three. The right-hand board below adds one, and a diagonal duly picks up a third.

The problem then asks for the same thing one size up. It is worth being careful about what “the same thing” means, because the answer turns on it, and because the version as posed cannot be done.

The model

Number the squares $(i,j)$ with $i$ the row and $j$ the column, both running from $1$ to $n$. Every square lies on exactly four queen-lines, and each of the four is a level set of a simple function:

The third and fourth lines are the useful ones. A $45^\circ$ line looks like a geometric object, but “three squares lie on a common $45^\circ$ line” says nothing more than “three squares share a value of $i-j$”, or of $i+j$. Collinearity at $45^\circ$ is arithmetic. That is the whole reason this problem is finite and checkable: an $n \times n$ board has $n$ rows, $n$ columns, $2n-1$ diagonals and $2n-1$ anti-diagonals, so $14 \times 14$ has $82$ queen-lines and nothing else to consider.

Now fix a set $P$ of marked squares and impose the two conditions.

Safety. No queen-line contains three marks. Equivalently, every queen-line contains at most two.

Maximality. Adding a mark on any empty square creates three on some queen-line.

Maximality looks like the awkward one, since it quantifies over every empty square and every line through it. Safety tames it. Call a queen-line full when it carries exactly two marks, which by safety is as many as it may carry. Adding a mark at an empty square $c$ creates a three only if the new three includes $c$, since the old marks were already safe. So the new three lies on one of the four queen-lines through $c$, and that line must already hold two marks. Turning this round:

The quantifier over added queens is gone, replaced by a covering condition on $82$ lines. This is the form to think in, and the form to compute in.

Twelve on a $14 \times 14$ board is impossible

Wagon’s problem asks for twelve marks on a $14 \times 14$ board. No such configuration exists, and the reason is worth more than the answer.

Write $q = |P|$ for the number of marks. Call a row or column full if it holds two marks. Let $$U = \{\text{squares on no full row and no full column}\}.$$ Everything follows from one observation about $U$.

This is immediate from the definition, and it is the crux. The two conditions defining $U$ are independent, one about $i$ and one about $j$, so $U$ inherits a rigid rectangular shape no matter how the marks are scattered.

Step 1: $U$ is large

Let $q''$ count the marks alone in both their row and their column. Each full row holds two marks, and neither is one of those $q''$. So $2 \cdot (\text{full rows}) \le q - q''$, giving at most $(12 - q'')/2$ full rows out of fourteen, and therefore $$r \;\ge\; 14 - \frac{12 - q''}{2} \;=\; 8 + \frac{q''}{2},$$ with the same bound for $c$. At least eight rows and eight columns are non-full. Twelve marks are simply too few to make many rows full: each full row costs two of them.

Step 2: the extreme columns

Let $a < b$ be the first and last non-full columns, and $a' < b'$ the first and last non-full rows. Assume $b - a \ge b' - a'$; if not, rotate the board by $90^\circ$, which exchanges rows with columns and diagonals with anti-diagonals, leaving both conditions and every count intact. By the lemma, column $a$ carries $r$ squares of $U$ and so does column $b$: call them $C_a$ and $C_b$, with $|C_a \cup C_b| = 2r \ge 16$.

None of these squares sits on a full row or a full column. So each is either occupied by a mark or killed by a full $45^\circ$ line. Column $a$ is not full, so it holds at most one mark, and likewise column $b$: at most two of the $2r$ squares are occupied. Moreover an occupied one lies in a non-full row and a non-full column, which then hold no other mark, so it is alone in both and is counted by $q''$. At most $\min\{q'',2\}$ of the $2r$ squares are occupied.

Step 3: diagonals are inefficient

A $45^\circ$ line meets a column once, so it kills at most one square of $C_a$ and one of $C_b$. Suppose one kills two, at $(y_1, a)$ and $(y_2, b)$. Going from column $a$ to column $b$ moves $b-a$ steps sideways, so $|y_2 - y_1| = b - a$. But $y_1$ and $y_2$ both lie in $[a', b']$, forcing $b - a \le b' - a'$. With the assumption of Step 2 this pins $b - a = b' - a'$, and then $y_1$ and $y_2$ are pinned to the ends: the line is a diagonal of the rectangle $[a',b'] \times [a,b]$. There is one such line of each slope, and every other $45^\circ$ line kills at most one of the $2r$ squares.

Let $L$ count the full diagonals and anti-diagonals. Now account for the $2r$ squares of $C_a \cup C_b$. At most $\min\{q'',2\}$ are occupied. The two rectangle diagonals kill at most two apiece, so at most four between them. Each of the remaining $L-2$ lines kills at most one. Hence $$2r \;\le\; \min\{q'',2\} \;+\; 4 \;+\; (L - 2),$$ so, using $r \ge 8 + q''/2$ from Step 1, $$L \;\ge\; 2r - 2 - \min\{q'',2\} \;\ge\; 16 + q'' - 2 - \min\{q'',2\} \;\ge\; 14 .$$ The $q''$ cancels, whichever value it takes.

Step 4: there are not enough diagonals

Each full diagonal uses two of the twelve marks, so there are at most six, and at most six anti-diagonals: $$L \;\le\; 6 + 6 \;=\; 12 .$$ Step 3 demands $L \ge 14$. This is a contradiction, so no such configuration exists. 0■

What the problem meant

The minimum number of marks on an $n \times n$ board is written $m_3(n)$. The full theorem of Cooper et al. gives $m_3(n) \ge n$ for every $n$ except $n \equiv 3 \pmod 4$, where one less may suffice. A twelve-mark configuration therefore forces $n \le 12$: the only board the exception could rescue is $13 \times 13$, and $13 \equiv 1 \pmod 4$. And $m_3(12) = 12$ exactly. So the honest reading of Wagon’s problem is a $12 \times 12$ board, not $14 \times 14$, and the provenance agrees: Gardner’s October 1976 column recorded placements on boards from $3 \times 3$ up to $12 \times 12$.² The alternative repair, fourteen marks on $14 \times 14$, is also impossible: $m_3(14) = 15$, so the smallest maximal configuration on that board carries fifteen marks.³

Here is a $12 \times 12$ answer.

It is prettier than the $6 \times 6$ case deserves. The twelve squares carry the full symmetry of the square, invariant under both reflections, under the half-turn, and under transposition. They form three nested rectangles: $$\{1,12\} \times \{1,12\}, \qquad \{3,10\} \times \{5,8\}, \qquad \{5,8\} \times \{3,10\},$$ the four corners, and two rectangles exchanged by transposition.

Maximality is visible rather than asserted. Draw every full line, and the empty squares have nowhere to hide.

The count is tight here

The pleasing part is that the argument that killed $14 \times 14$ does not merely permit $12 \times 12$, it is satisfied with nothing to spare. Run Step 1 through Step 3 with $n = 12$ and $q = 12$. No mark is alone in both its row and column, so $q'' = 0$, and there are six full rows, so $r = 6$. Step 3 then demands $$L \;\ge\; 2r - 2 - 0 \;=\; 10 .$$ Counting the figure: five full diagonals and five full anti-diagonals, so $L = 10$. Exactly ten. The configuration sits on the boundary of the inequality, which is why twelve marks fit on twelve columns and not on fourteen. On a $14 \times 14$ board the same marks would leave two more rows and two more columns non-full, the extreme columns would carry sixteen exposed squares instead of twelve, and the demand would climb to fourteen diagonals against a supply of twelve.

On computing

The proof above needs no machine. Finding the configuration does, and the two tasks want different tools.

The covering form of the Proposition translates directly into a constraint model. For each square a Boolean $x_{ij}$, and for each queen-line $\ell$ a Boolean $f_\ell$ meaning “$\ell$ is full”:

for cells in lines.values():                     # safety
    model.Add(sum(x[c] for c in cells) <= 2)

for key, cells in lines.items():                 # f <=> line is full
    model.Add(sum(x[c] for c in cells) >= 2).OnlyEnforceIf(f[key])
    model.Add(sum(x[c] for c in cells) <= 1).OnlyEnforceIf(f[key].Not())

for (i, j) in squares:                           # maximality
    through = [("row", i), ("col", j), ("dia", i-j), ("ant", i+j)]
    model.Add(x[(i, j)] + sum(f[k] for k in through) >= 1)

Two details earn their keep. The second $f$ constraint is redundant for correctness, since $f$ appears only positively in the third block, but making $f$ a genuine indicator rather than a one-way implication is what lets the solver propagate; without it the $14 \times 14$ case does not resolve in reasonable time. And the whole model rests on reading the $45^\circ$ lines as level sets of $i \pm j$, which is what makes the line index finite.

Solved for $n=12$ and $q=12$, this returns the configuration above in about a third of a second. Its output can be checked against the published values of $m_3(n)$ for $n = 3, \ldots, 12$, namely $4, 4, 6, 6, 8, 9, 10, 10, 12, 12$, and it reproduces all ten, including the irregular $m_3(8) = 9$.

The contrast with the proof is the lesson. A solver reports that twelve marks on $14 \times 14$ is infeasible after half a minute of search, and that verdict covers one board and explains nothing. Four paragraphs of counting dispose of every even board at once, and say why: the squares that escape the full rows and columns form a rectangle, the two extreme columns of that rectangle expose $2r$ of them, and $45^\circ$ lines can only pick them off one at a time.

Lines of any slope

Queen-lines are a convention. Drop it, and say three squares are in a row when their centres lie on one straight line of any slope, so that $(1,1)$, $(2,3)$ and $(3,5)$ now count. Both conditions move at once. Safety tightens, since triples the queens game ignored are now fatal. Maximality loosens, since an empty square can be caught by any line through it rather than by four. Nothing so far says which effect wins.

The Proposition survives word for word, with “line” now meaning a maximal set of three or more collinear squares. The problem stays finite, though no longer small: a $14 \times 14$ board carries $1582$ such lines, and only $74$ of them are queen-lines.

Both boards above pass into the new game unchanged. No three of Wagon’s six queens are collinear on any slope, and every empty square of the $6 \times 6$ board is collinear with two of them; the machine confirms the same for the twelve marks on $12 \times 12$. Neither solution leaned on the convention.

The impossibility proof does not survive. Its engine was scarcity: in the queens game a full line needs two marks already aligned on a row, a column or a $45^\circ$ line, and twelve marks can make at most six full diagonals and six full anti-diagonals. Here every pair of marks spans a full line. Twelve safe marks carry $\binom{12}{2} = 66$ of them, all distinct, since a shared line would hold three marks. And Step 3 dies with the scarcity: a line meeting both extreme columns of $U$ is no longer forced to climb one row per column, so it need not be a diagonal of the bounding rectangle, and tilted lines can kill exposed squares two at a time. The count never gets started.

The conclusion reverses with it. Twelve marks fit on a $14 \times 14$ board once every slope is in play.

The structure rhymes with the $12 \times 12$ answer. The four corners return, and in place of two nested rectangles an octagon rings the centre, $\{6,9\} \times \{7,8\}$ and $\{7,8\} \times \{6,9\}$, exchanged by transposition. Verification is the direct kind: none of the $220$ triples of marks is collinear, and each of the $184$ empty squares is collinear with two marks. Eight of those squares, the orbit of $(2,5)$ under the symmetries of the board, are caught by tilted lines alone. That is the theorem of the earlier sections showing through: had every empty square sat on a full queen-line, these twelve marks would contradict the count of Steps 1 to 4.

The minimum for this game is tabulated as OEIS A277433. For $n = 3, \ldots, 12$ it runs $4, 4, 6, 6, 8, 8, 8, 8, 10, 10$, against $4, 4, 6, 6, 8, 9, 10, 10, 12, 12$ for the queens game: never larger, despite the harder safety condition. The extra lines help more than they hurt, and the queens bound $q \ge n$ is not merely unproved here but false, since eight marks suffice on $10 \times 10$. The exact values stop at $12 \times 12$, completed by Aichholzer, Eppstein and Hainzl, who also prove that fewer than order $n^{2/3}$ marks can never suffice. Twelve is the best known count for both $13 \times 13$ and $14 \times 14$, so the octagon configuration is best known rather than best possible.⁴

The constraint model is the one already given; only the table of lines changes, $1582$ lines of every slope in place of the $82$ queen-lines. Asked for twelve marks carrying the full symmetry of the square, the solver produces the octagon in a tenth of a second.

The sixteen symmetric solutions

A solver can do better than produce an answer. Asked to enumerate rather than to find, it reports that the twelve-mark solutions with the full symmetry of the square number exactly sixteen, lists them in the same tenth of a second, and every one of the sixteen passes the direct check of triples and coverage.

The count is not merely observed, it can be proved, and most of the proof is done by hand. The symmetries of the board split its $196$ squares into orbits. An orbit seeded on the main diagonal, at $(d,d)$ with $d \le 7$, has size four; every other orbit has size eight, with a unique seed $(a,b)$ satisfying $a < b \le 7$. A fully symmetric solution is a union of orbits, and twelve splits as $4+8$ or $4+4+4$. The second dies at once: three diagonal orbits put six marks on the main diagonal, and any three of those are collinear. So every solution is one diagonal orbit and one ring, which leaves $7 \times \binom{7}{2} = 147$ candidates. What remains is finite checking, and no solver is needed for it: run the cross-product test over the $147$, and $64$ fail safety, $67$ more fail maximality, and the sixteen of the figure survive. The CP-SAT enumeration returns the same sixteen, so the census rests on nothing deeper than integer arithmetic that agrees with itself twice.

The catalogue has its own small structure. Four diagonal orbits occur, seeded at $(1,1)$, $(2,2)$, $(4,4)$ and $(7,7)$, the last being the central block $\{7,8\} \times \{7,8\}$. Nine distinct rings partner them, the corners taking six, the block only two, and the ring seeded at $(3,6)$ alone is compatible with all four diagonal choices.

The census also travels back to the queens game, where the paper began. On the $12 \times 12$ board the same orbit argument leaves $6 \times \binom{6}{2} = 90$ candidates, and the queen-line test passes exactly eight. The solution of the earlier section is the second; the eighth builds on the central block $\{6,7\} \times \{6,7\}$, the same germ as number 16 above. Five of the six diagonal orbits appear, and only the seed $(5,5)$ partners no ring at all. The CP-SAT enumeration over queen-lines returns the same eight.

Wagon’s twelve and fourteen were the right numbers for a game one convention away, and the game repays the widening sixteen times over.

Appendix: the programs

Every computed claim in this paper rests on the programs below: the table of lines, the model with its enumeration, a check that trusts nothing but cross products, the census of the sixteen, and the one-predicate substitution that makes it a census of the eight. They need ortools and the standard library, and the checks only the standard library.

from itertools import combinations, product
from math import gcd
from ortools.sat.python import cp_model

A line of any slope is recorded as its maximal run of grid squares, walked once from its first square along a primitive direction, and kept when it holds three or more. On $14 \times 14$ this yields the $1582$; restricting the directions to $(0,1)$, $(1,0)$ and $(1,\pm 1)$ recovers the queens game.

def grid_lines(n: int) -> list[list[tuple[int, int]]]:
    dirs = [(0, 1), (1, 0)]
    for dx in range(1, n):
        for dy in range(1, n):
            if gcd(dx, dy) == 1:
                dirs += [(dx, dy), (dx, -dy)]
    lines = []
    for dx, dy in dirs:
        for i, j in product(range(1, n + 1), repeat=2):
            if 1 <= i - dx <= n and 1 <= j - dy <= n:
                continue                # not the start of this line
            chain, ci, cj = [], i, j
            while 1 <= ci <= n and 1 <= cj <= n:
                chain.append((ci, cj))
                ci, cj = ci + dx, cj + dy
            if len(chain) >= 3:
                lines.append(chain)
    return lines

The model is the one from the queens game with the bigger table, plus the two reflections that generate the symmetry group, and a callback that collects every solution instead of stopping at the first. The indicator constraints make $f$ a function of the marks, so sixteen assignments mean sixteen configurations, not double counting.

def all_symmetric(n: int, q: int) -> list[list[tuple[int, int]]]:
    model = cp_model.CpModel()
    board = list(product(range(1, n + 1), repeat=2))
    x = {c: model.NewBoolVar(f"x{c}") for c in board}
    through = {c: [] for c in board}
    for k, line in enumerate(grid_lines(n)):
        f = model.NewBoolVar(f"f{k}")
        s = sum(x[c] for c in line)
        model.Add(s <= 2)                       # safety
        model.Add(s >= 2).OnlyEnforceIf(f)      # f <=> line is full
        model.Add(s <= 1).OnlyEnforceIf(f.Not())
        for c in line:
            through[c].append(f)
    for c in board:                             # maximality
        model.Add(x[c] + sum(through[c]) >= 1)
    model.Add(sum(x.values()) == q)
    for i, j in board:                          # dihedral symmetry
        model.Add(x[(i, j)] == x[(j, i)])
        model.Add(x[(i, j)] == x[(n + 1 - i, j)])

    sols: list[list[tuple[int, int]]] = []
    class Collect(cp_model.CpSolverSolutionCallback):
        def on_solution_callback(self) -> None:
            sols.append(sorted(c for c in board if self.Value(x[c])))
    solver = cp_model.CpSolver()
    solver.parameters.enumerate_all_solutions = True
    solver.Solve(model, Collect())
    return sols

No verdict rests on the model. The checker re-derives both conditions from cross products alone, safety over the triples of marks and coverage over the empty squares. A checker that cannot fail proves nothing, so it was first fed mutilated configurations, a mark removed and a mark added, and rejected both.

def collinear(p: tuple[int, int], q: tuple[int, int],
              r: tuple[int, int]) -> bool:
    return ((q[0] - p[0]) * (r[1] - p[1])
            == (q[1] - p[1]) * (r[0] - p[0]))

def is_solution(n: int, marks: list[tuple[int, int]]) -> bool:
    safe = not any(collinear(*t) for t in combinations(marks, 3))
    empty = (c for c in product(range(1, n + 1), repeat=2)
             if c not in set(marks))
    covered = all(any(collinear(p, q, c)
                      for p, q in combinations(marks, 2))
                  for c in empty)
    return safe and covered

Last, the census. The symmetry argument in the text reduces the count of fully symmetric solutions to $147$ candidates, one diagonal seed and one ring seed, and this loop scores them with the checker alone. It returns the sixteen seed pairs in a few hundredths of a second, with no solver in sight, and the figure of sixteen is drawn from its output rather than the solver’s. Two derivations that meet exactly are worth more than one derivation trusted twice.

def census(n: int = 14) -> list[tuple[int, tuple[int, int]]]:
    m = n + 1
    def orbit(i: int, j: int) -> set[tuple[int, int]]:
        return {(i, j), (j, i), (m - i, j), (j, m - i),
                (i, m - j), (m - j, i), (m - i, m - j), (m - j, m - i)}
    return [(d, (a, b))
            for d in range(1, n // 2 + 1)
            for a in range(1, n // 2 + 1)
            for b in range(a + 1, n // 2 + 1)
            if is_solution(n, sorted(orbit(d, d) | orbit(a, b)))]

The queens game takes the same census. Substitute the queen-line test below for collinear inside is_solution and run census(12): ninety candidates, and the eight of the figure come back.

def queen_collinear(p, q, r) -> bool:
    return (len({p[0], q[0], r[0]}) == 1
            or len({p[1], q[1], r[1]}) == 1
            or len({p[0] - p[1], q[0] - q[1], r[0] - r[1]}) == 1
            or len({p[0] + p[1], q[0] + q[1], r[0] + r[1]}) == 1)

---

1. A. S. Cooper, O. Pikhurko, J. R. Schmitt and G. S. Warrington, Martin Gardner’s minimum no-3-in-a-line problem, American Mathematical Monthly 121 (2014) 213–221; arXiv:1206.5350. The elementary argument above is their Section 4, which follows an incomplete argument of John Harris in a letter to Gardner of 7 June 1975. Consulted 16 July 2026.↩︎

2. M. Gardner, Mathematical Games, Scientific American, October 1976; reprinted in Penrose Tiles to Trapdoor Ciphers, MAA, 1997, chapter 5. The range of boards is reported in the history section of Cooper et al. Consulted 16 July 2026.↩︎

3. Cooper et al. could print only the bounds $14 \le m_3(14) \le 16$; the exact value was computed in 2014 by Rob Pratt by integer linear programming, and is recorded, with values up to $n = 29$, as OEIS sequence A219760. Consulted 23 July 2026.↩︎

4. OEIS sequence A277433, values and best-known bounds as revised 3 July 2026. O. Aichholzer, D. Eppstein and E.-M. Hainzl, Geometric dominating sets, Computational Geometry 108 (2023), article 101913; arXiv:2203.13170: the $\Omega(n^{2/3})$ lower bound, and optimal configurations up to $12 \times 12$. Consulted 23 July 2026.↩︎