Complete the Square Game

Question

I recently downloaded a game to my TI NSPIRE CX called Complete the Square. http://www.ticalc.org/pub/nspire/lua/games/. Players take turns placing stones on a six-by-six board. One player has blue stones, the other player has red stones. Only one stone may be put on a square. Players continue in this fashion, placing stones until one person's stones form the four corners of a square. That player is the winner. My question is this: Is it possible to completely fill up the board so that the game ends in a draw? Clearly this is true for a 2x2 board, and, with a little thought, one can see it is also true for a 3x3 board. Is there and easy way to determine whether or not an non board can be a draw? What about NxM boards? I think this question might have something to do with graph theory, so I shall file it as such, but feel free to move it if you believe it belongs elsewhere. I ask this question because I wanted to find a winning strategy, and one must clearly exist if the game can never end in a draw. Furthermore, it must be a 1st player win, because if there existed a second player winning strategy, the 1st player could make a random move for his first turn and then follow the second player strategy for the rest of the game.

Answer 1

We mostly know the answer to this question, but not quite.

I'm going to ignore the condition that in an actual complete-the-square game, the number of red and blue stones at the end should be equal or off by one. Instead, we can just look for an arbitrary coloring of the grid that avoid squares whose corners are the same color. If one exists, then it will generally be balanced or nearly balanced, and we can probably make it balanced by fiddling with it a little. (After all, very unbalanced colorings should have lots more squares whose corners are the same color.)

---

Here's one result that's relatively easy to prove: if $M + 2N \le 36$ (or, by symmetry, if $N + 2M \le 36$) then a squareless coloring exists on an $M \times N$ board. For example, a squareless coloring exists on a $12 \times 12$ grid.

To create such a coloring, start with the following coloring of the integers $1, 2, \dots, 34$ (found by Chvátal in 1970) $$ \color{blue}{1}\,\color{red}{2}\,\color{blue}{3}\,\color{red}{4}\,\color{red}{5}\,\color{red}{6}\,\color{blue}{7}\,\color{blue}{8}\,\color{blue}{9}\,\color{red}{10}\,\color{blue}{11}\,\color{red}{12}\,\color{red}{13}\,\color{blue}{14}\,\color{red}{15}\,\color{red}{16}\,\color{red}{17}\,\color{blue}{18}\,\color{blue}{19}\,\color{blue}{20}\,\color{red}{21}\,\color{blue}{22}\,\color{blue}{23}\,\color{red}{24}\,\color{blue}{25}\,\color{red}{26}\,\color{red}{27}\,\color{red}{28}\,\color{blue}{29}\,\color{blue}{30}\,\color{blue}{31}\,\color{red}{32}\,\color{blue}{33}\,\color{blue}{34} $$ in which no arithmetic progression of length $4$ has the same color. Next, label the squares of the grid by integers in the following pattern:

\begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & \cdots \\ 3 & 4 & 5 & 6 & 7 & \cdots \\ 5 & 6 & 7 & 8 & 9 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}

In this labeling, a $d \times d$ square whose top left corner is labeled $a$ will contain the labels $a+d, a+2d, a+3d$ in its other corners. So if we transfer the coloring of the integers to a coloring of the grid by using this labeling, then no square will be monochromatic, showing us how to get a draw.

(The condition $M+2N \le 36$ guarantees that we only need the integers $1,2,\dots,34$ for the labeling. This is important because there's no coloring of the integers $1,2,\dots,35$ with the same property.)

---

For square grids, we further know that (again, ignoring the number of stones of each color) a draw is possible on a $14 \times 14$ grid, but not on a $15 \times 15$ grid. Unfortunately, there's no construction as "nice" as the one above: it's just that in this paper, the $14 \times 14$ and $15 \times 15$ questions are verified by SAT solver.

This still leaves open the question of what happens when we play on long and thin rectangles. For example, on a $3 \times N$ board, a draw is possible for all $N$: just extend the coloring \begin{array}{ccccc} \color{red}{\bullet} & \color{blue}{\bullet} &\color{red}{\bullet} &\color{blue}{\bullet} &\cdots \\ \color{red}{\bullet} & \color{blue}{\bullet}&\color{red}{\bullet} &\color{blue}{\bullet} &\cdots \\ \color{blue}{\bullet} & \color{red}{\bullet} &\color{blue}{\bullet} &\color{red}{\bullet} &\cdots \end{array} as far as you like. Is this possible on a $4 \times N$ board? Quite possibly. On a $13 \times N$ board? Almost certainly not.