Square achievement game on an n x n grid

Square achievement game on an n x n grid

Definitions and mathematical statement

For an integer $n\ge1$, the board is the set of cells $[n]\times[n]$, initially empty. Two players, called $O$ and $X$, alternate turns, with $O$ moving first. On each turn the player claims one previously unoccupied cell by placing their own symbol there; a claimed cell never changes owner, and passing is not allowed.

A winning set is \[ \{(i,j),(i+t,j),(i,j+t),(i+t,j+t)\}, \qquad t\ge1,\quad 1\le i,j\le n-t. \] These are four cell positions at the corners of an axis-parallel square. The first player to own all four members of any winning set wins immediately. If every cell is filled and neither player has completed a winning set, the game is drawn. Squares of every positive integral side length are allowed; general rectangles and tilted squares are not winning sets.

Determine the outcome under optimal play for each $n$: a forced win for $O$, a forced win for $X$, or a draw. A strategy specifies a legal move for every game history where the player is to move. A forced win must succeed against every sequence of legal opposing moves before the opponent wins. A drawing strategy guarantees avoidance of defeat.

The existence of a completely filled board without a winning square only shows that some play can end in a draw; it does not prove that either player can force that play against optimal opposition. The task therefore concerns strategies and the order of moves, not merely binary colourings.

Short English statement

Who can force a win, or a draw, when players alternately claim grid cells and try to complete the corners of an axis-parallel square?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Literature update and local scope.

Jenrich's primary preprint [R1] reports drawing defences for the second player on the $3\times3$ and $4\times4$ boards and a winning strategy for the first player on $5\times5$. Therefore the historical catalogue wording must not be interpreted as a current claim that these outcomes have never been determined. Here we independently prove the $n\le3$ outcomes and the general strategy-stealing obstruction to a second-player forced win. We do not certify the larger computer-assisted strategy trees in [R1].

Second cannot have a forced win on any board size.

This is a finite strong positional game with the same winning sets for both players; owning an extra cell cannot invalidate one's winning set. Suppose the second player had a winning strategy $S$. The first player initially claims an arbitrary spare cell, then simulates playing second according to $S$ against the opponent's actual moves. The simulated second-player cells are always a subset of the first player's actual cells; the opponent's cells are the same in both games. If $S$ requests the spare cell already owned, mark it in the simulation and claim another free cell as the new spare. Otherwise play the requested cell normally.

The opponent cannot win first, since the same sequence would defeat $S$ in the simulated game. A simulated winning set is already an actual winning set, so the first player wins by that stage or earlier. If no free spare can be chosen, the actual board is full and the simulation has only the old spare left; a guaranteed win by $S$ then lies already in the actual first player's cells, again implying an earlier win. This contradiction rules out a second-player forced win. Finite backward induction ensures that the remaining possibilities are a first-player win or a draw; thus first can always avoid defeat.

An explicit second-player defence for $n=3$.

Pair the following cells, leaving $(1,1)$ unpaired: \[ \{(1,2),(1,3)\},\quad \{(2,1),(2,2)\},\quad \{(2,3),(3,2)\},\quad \{(3,1),(3,3)\}. \] After each opposing move into a pair with empty partner, claim that partner. If its partner is already owned by the defender, or the unpaired cell was played, claim any available cell. The invariant is that a pair never becomes wholly owned by the opponent: the first opposing occupation is immediately answered unless the partner was already protected. Extra defensive claims cannot harm this invariant.

There are exactly five winning squares. The upper-right unit square contains the first pair; both left unit squares contain the second; the lower-right unit square contains the third; the side-two square contains the fourth. Hence the first player can never complete a square against this strategy. Coupled with first player's general non-losing strategy, this proves a draw for $n=3$. For $n=1$ no winning square exists. For $n=2$ the only winning set is the whole board and neither player can own its four cells, so these are draws too.

Independent exact computation.

The script scripts/check_attempt_batch_algebra_2026_10_01.py checks the pairing against all five squares and runs exact minimax on the $3\times3$ board. A state records disjoint bitmasks of the player to move and the opponent. A move completing a square scores $+1$ immediately; otherwise its score is the negative of the swapped successor state's value. A full board without a winner scores zero. Maximizing over all legal moves is exhaustive backward induction. The initial value computed is zero, consistent with the explicit strategy proof. No larger-board search was run in this attempt.

Verification and first remaining task.

The winning sets checked have equal horizontal and vertical side lengths; allowing all rectangles would change the game and invalidate the five-set calculation. A draw-colouring alone would not prove a defence; the pairing gives legal responses to every history. The unpaired cell and arbitrary-response cases are covered by the invariant, including when the board becomes full. The remaining independent task is to verify the reported $n=4,5$ strategies and their application to larger boards while respecting immediate opponent wins; this is not supplied merely by embedding a subboard.

Final status of this attempt.

UNRESOLVED as an independent complete strategy audit. Outcomes for $n\le3$ and exclusion of second-player forced wins are proved. Reported stronger results are attributed to [R1], not claimed as new discoveries or silently ignored.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3049 (OPG-37228), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Square achievement game on an n x n grid. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/a_game_on_an_n_x_n_grid.

• R1 Thomas Jenrich, Guaranteed successful strategies for a square achievement game on an $n$ by $n$ grid, arXiv:1109.2341, 2011. Primary preprint and description of the SQRGAME2 certificates; abstract checked 1 October 2026. https://arxiv.org/abs/1109.2341.