If you’re used to the original versions and want to spice up your life a little bit, you can play Torque (Queens on a torus)…

This Queen Loves to Tango!

Torque, Twango, and Algebraically Addled Games

Courtney Gibbons
Hamilton College

Whenever I see a new game, I can’t resist thinking, “Oooh! Can I make this game less fun with algebra?” (Readers of this column know that less is more.)

There are a couple of LinkedIn games that are irresistible in this regard (thanks, LinkedIn Puzzle Editor Paolo Pascal): Queens and Tango.

Both Queens and Tango are played on a grid, and in both games, each cell has two options. In Tango, you can put a sun or a moon in each cell. In Queens, you can put a queen in a cell or put an $\times$ in the cell. Each game has a set of rules that can be interpreted as polynomials, and each daily puzzle has a unique solution. So, for either game, we’ll work with polynomials in the $n^2$ variables $x_{1,1}, \ldots, x_{n,n}$. The variable $x_{i,j}$ corresponds to the cell in the $i$-th row and $j$-th column, and a choice of values for all the cells will be a solution to a system of polynomials. In both games, we only have two choices per cell, which means the values need to solve $(x_{i,j} – a)(x_{i,j} – b)$ where $a$ and $b$ are constants. Our choice of constants will depend on how we decide to model the game. In what follows, we’ll take our constants—and all possible coefficients of polynomials—to live in the complex numbers $\mathbb{C}$. For the experts, this means we’re working in the polynomial ring $\mathbb{C}[x_{1,1}, \ldots, x_{n,n}]$. (If you’re an especially expert expert, try taking the coefficient ring to be a different algebraically closed field $k$!)

Our choice of coefficients will allow us to use the full power of Hilbert’s Nullstellensatz: the unique solution to the gameboard corresponds to exactly one set of equations of the form $x_{1,1}=a_{1,1}, \ldots, x_{n,n}=a_{n,n}$, where the right-hand side of each equation is a constant. We’ll find this solution with algebraic techniques!

Wondering what a Nullstellensatz is? That requires a brief trip to the turn of the 20th Century.

Hilbert’s Nullstellensätze

You probably already know one connection between algebra and geometry—the Fundamental Theorem of Algebra, which states that over the complex numbers $\mathbb{C}$ (or any algebraically closed field $k$), every nonconstant polynomial $f \in k[x]$ of degree $d$ factors uniquely into a product of linear polynomials,

$$f(x) = a_0(x-a_1)\cdots (x-a_d),$$

which means that the values $a_1, \ldots, a_d \in \mathbb{C}$ are all solutions to $f(x) = 0$. In fact, this is an if and only if statement because polynomial rings are Euclidean domains, meaning we have a division algorithm that guarantees each remainder will be smaller than the divisor in the sense of having smaller degree or being the zero polynomial (which has a complicated relationship with the notion of degree). So $f(x) = g(x)(x – a_i) + r$ for some $r \in \mathbb{C}$ if and only if $f(a_i) = r$.

David Hilbert worked to develop more of the dictionary between algebra and geometry. One of his most famous results is the Nullensatz (which I translate from German as “zeros placement theorem”), and it’s a much more general link between the algebraic structure of polynomials in a polynomial ring (an ideal) with the geometry of the simultaneous solutions to those polynomials (a variety). (See the notes for more Hilbert bangers.)

In abstract algebra, an ideal is a subring that is closed under scalar multiplication from the ring; in the case of a polynomial ring, that means the zero polynomial is in the ideal and you can add or subtract polynomial multiples of elements of the ideal together and stay in the ideal. The largest ideals that are not the whole ring (in the sense that including one more element from outside the ideal would force the ideal to become the ring) are called maximal ideals. In the ring $\mathbb{C}[x]$, $\langle x – 2\rangle$ (the polynomial multiples of $x-2$) is a maximal ideal because if you consider an ideal $I$ containing $\langle x-2 \rangle$ and $p(x)$ where $p(x)$ is not in $x-2$, that means there exists a nonzero polynomial $q(x)$ and a nonzero complex number $r$ for which $p(x) = q(x)(x-2) + r$. But once $0 \not = r \in \mathbb{C}$ is in $I$, the scalar multiplication property gives us that any polynomial is in $I$; indeed, given $f(x)$, $f(x) = r\cdot (r^{-1}f(x)) \in I$. In $\mathbb{C}[x_1,\ldots,x_n]$, maximal ideals take the form $\langle x_1 – a_1, x_2 – a_2, \ldots, x_n – a_n \rangle$ where each $a_i \in \mathbb{C}$.

The Nullstellensatz generalizes the relationship between zeros and linear factors by associating points with maximal ideals. It states that $(a_1, a_2, \ldots, a_n) \in \mathbb{C}^n$ is a simultaneous zero for the members of $I \subseteq \mathbb{C}[x_1,\ldots,x_n]$ if and only if $I \subseteq \langle x_1 – a_1, x_2 – a_2, \ldots, x_n – a_n \rangle$.

There are lots of versions of the Nullstellensatz. Here are some from the Princeton Companion to Mathematics (from IV.4 on Algebraic Geometry):

• Specialized to two polynomials. The polynomials $f$ and $g$ in $\mathbb{C}[x_1,\ldots,x_n]$ have the same zeros in $\mathbb{C}^n$ if and only if they have the same irreducible factors (a generalization of the Fundamental Theorem of Algebra).
• Arithmetically for two polynomials. Two polynomials $f$ and $g$ with integer coefficients in $\mathbb{C}[x_1,\ldots,x_n]$ have the same zeros modulo $m$ for every $m$ if and only if $f = \pm g$.
• Weakly. The polynomials $f_1,\ldots,f_m$ have no common zeros in $\mathbb{C}[x_1,\ldots,x_n]$ if and only if there exist polynomials $g_1,\ldots,g_m \in \mathbb{C}[x_1,\ldots,x_d]$ for which $g_1f_1 + g_2f_2 + \cdots + g_mf_m = 1$.
• Not Weakly (i.e., the usual statement). Let $f_1,\ldots,f_m,$ and $h$ be polynomials in $\mathbb{C}[x_1,\ldots,x_n]$. Evaluating at a point $(a_1,\ldots,a_n) \in \mathbb{C}^n$, we have $h(a_1,\ldots,a_n) = f_i(a_1,\ldots,a_n)$ for all $i$ if and only if there exist polynomials $g_1,\ldots,g_m \in \mathbb{C}[x_1,\ldots,x_n]$ and a positive integer $r$ for which $g_1f_1 + g_2f_2 + \cdots g_mf_m = h^r$. (Why the exponent in the strong version of the Nullstellensatz? Loosely, algebra detects repeated roots via repeated factors, but geometry alone cannot tell if a root is repeated.)
• Effectively. Suppose $f_1,\ldots,f_m$ are polynomials of degree at most $d$ in $\mathbb{C}[x_1,\ldots,x_n]$ (where $d \geq 3$, $n \geq 2$). If $f_1\ldots,f_m$ have no common solutions, then there exist polynomials $g_1,\ldots,g_m \in \mathbb{C}[x_1,\ldots,x_n]$ for which $g_1f_1 + g_2f_2 + \cdots g_mf_m = 1$ and $\deg(g_i) \leq d^n – d$.

Now it’s time for some games (and fun).

Queens

Queens is played on any $n \times n$ board, and the board is divided up into different contiguous regions (color-coded and outlined). You must place exactly one queen in each row, column, and region in such a way that there are queens in the cells directly above, below, left, right, or sharing one corner with another queen.

To model queens, we’ll say that a queen takes the value $a = 1$ and the absence of a queen takes the value $b = 0$, so each cell’s value will satisfy $x_{i,j}^2 – x_{i,j} = 0$. The rules for the rows and columns are straightforward: each row and column sums to $1$ since it must have exactly one queen: $$\mathrm{row}_i(x_{1,1}, \ldots, x_{n,n}) = 1 – \sum_{j = 1}^n x_{i,j},$$ and $$\mathrm{col}_j(x_{1,1}, \ldots, x_{n,n}) = 1 – \sum{i = 1}^n x_{i,j}.$$

In principle, the adjacency rules should satisfy something like $$1 – \sum_{k = -1}^1 \sum_{\ell = -1}^1 x_{i+k,j+\ell},$$ but some of those indices are undefined if $i$ or $j$ is $1$ or $n$. For instance, our formula for the top left cell is $$1 – x_{0,0} – x_{0,1} + x_{0,2} + x_{1,0} + x_{1,1} + x_{1,2} + x_{2,0} + x_{2,1} + x_{2,2},$$ which involves five nonexistent variables! To take care of the (literal) edge cases, we introduce a little toggle function:

$$
e_{i+k,j+\ell} =
\begin{cases}
0 & \text{ if } k = \ell = 0 \text{,} \\
1 & \text{ else if } 1 < i+k < n \text{ and } 1 < j + \ell < n \text{,} \\
0 & \text{ otherwise.}
\end{cases}
$$
for $k, \ell \in \{-1,0,1\}$. Note that $e_{i,j} = 0$ deliberately to ensure the $i,j$-th cell and its neighbors satisfy the polynomial
$$\mathrm{adj}(x_{1,1}, \ldots, x_{n,n}) = 1 – \left(\sum_{k = -1}^1 \sum_{\ell = -1}^1 e_{i+k,j+\ell} x_{i+k,j+\ell}\right).$$

Now $\mathrm{adj}_{1,1}(x_{1,1}, \ldots, x_{n,n}) = 1 – x_{1,1} – x_{1,2} – x_{2, 1} – x_{2,2}$.

Each game involves different regions, so we have to set those up every time we play. Our example game above involves the blue region $$x_{1,4}+x_{2,3}+x_{2,4}+x_{2,5}+x_{3,5} – 1,$$ and the other regions are similar but tedious to enumerate.

Once we have them, though, we can use our favorite numerical solver to find the maximal ideal corresponding to our board, just like we did for sudoku.

Tango

For Tango, the rules are

1. Fill the grid so that each cell contains either a sun or a moon.
2. No more than 2 suns or moons may be next to each other, either vertically or horizontally.
3. Each row and column must contain the same number of suns and moons.
4. Cells separated by $=$ must be of the same type.
5. Cells separated by $\times$ must be of the opposite type.

The first three rules tell us about any board, and we can infer that we need to play on a board where $n = 2k$ for some $k$. For our cell equations $(x_{i,j} – a)(x_{i,j} – b)$, there’s a nice symmetry if you let $a = 1$ and $b = -1$ so that each row and column sums to zero. (Shout-out to Prof. Josh Grochow for suggesting these values to simplify many of the equations.) Three sequential cells (either in a row or column) can sum to $\pm 1$, which we can reduce to $x_{i,j}x_{i,j+1} + x_{i,j}x_{i,j+2} + x_{i,j+1}x_{i,j+2} + 1$ for $1 \leq i \leq n-2$ (or the equivalent for columns).

The clues for any specific Tango game are the placements of the $=$ or $\times$ symbols on the border between cells and some initial suns and moons. For $=$ and $\times$, the equations $x_{i_1,j_1} – x_{i_2,j_2}$ force two cells to be the same and $x_{i_1,j_1} + x_{i_2,j_2}$ force two cells to be different. Initial suns and moons give polynomials of the form $x_{i,j} – 1$ (for a sun) or $x_{i,j} + 1$ (for a moon).

In the board above, we know that in row 1 we’ve got suns in columns 1 and 2, we can quickly deduce that row one, column 3 must be a moon, so $x_{2,3} + 1$ must be in the maximal ideal corresponding to the solution to this board! Our deduction corresponds to reducing the neighbors rule polynomial $x_{1,1}x_{1,2} + x_{1,1}x_{1,3} + x_{1,2}x_{1,3} + 1$ using the clues $x_{1,1} – 1$ and $x_{1,2} – 1$. (One way to do this reduction is to use the clues to eliminate the variables $x_{1,1}$ and $x_{1,2}$ by setting them both equal to $1$, and that leaves us with $2x_{1,3} + 2$, which we can scale in our ideal to $x_{1,3} + 1$.)

As before, we can toss our board rule polynomials and clue polynomials into a numerical solver that will do all these reductions for us to find the unique maximal ideal corresponding to the unique solution.

If Paolo Pascal were to accidentally let through a puzzle with no solutions or nonunique solutions (he would never!), our techniques would find no or multiple solutions, respectively, by returning the zero ideal (no solutions) or the intersection of the maximal ideals corresponding to each different solution, in which case we could use primary decomposition to detangle those ideals and see the different solutions!

Now with some topologies (my apologies!)

Introducing Torque and Twango

If you’re used to the original versions and want to spice up your life a little bit, you can play Torque (Queens on a torus) by identifying $x_{i,j}$ using the residues of $i$ and $j$ modulo $n$ (denoted $i \% n$, $j \% n$), so that $x_{0,0}$ refers to $x_{n,n}$, $x_{0,1}$ refers to $x_{n,1}$, and $x_{1,1}$ still refers to itself. (We slightly abuse the term “residue” here and use the complete residue system $1,\ldots,n$ instead of $0,\ldots,n-1$.) Now we no longer need the toggle function; instead, we have $$\mathrm{adj}_{i,j}(x_{1,1}, \ldots, x_{n,n}) = 1 – \sum_{k = -1}^1 \sum_{\ell = -1}^1 x_{i+k \% n,j+\ell \% n}.$$

Were I a games editor, I would be excited about the possibility to extend color-regions across the borders…

Playing Torgo (Tango on a torus) is less interesting if your board is $6 \times 6$ or smaller. That’s because when the neighbor rules are extended to cross the boundaries, three together across a boundary is equivalent to three together in the normal board. It gets more interesting at $n = 8$; to adapt the game, we add two more rules per row and column: $$x_{i,j}x_{i,j+1 \% n} + x_{i,j}x_{i,j+2 \% n} + x_{i,j+1 \% n}x_{i,j+2 \%n} + 1$$ for $n-2 \leq i \leq n$ (and the equivalent for the columns).

But for any $n$, playing Twango (Tango with a twist; i.e., Tango on a Möbius strip) is fun! You can pick the left and right sides to glue together (with the usual half twist) or the top and bottom sides. If we glue the left and right sides, we need to add two more equations per row to handle the weird relations across the twisted border, $$x_{i,n-1}x_{i,n} + x_{i,n-1}x_{n-i,1} + x_{i,n}x_{n-i,1} – 1,$$ and $$x_{i,n}x_{n-i,1} + x_{i,n}x_{n-i,2} + x_{n-i,1}x_{n-i,2} – 1.$$

 

Were I a games editor, I would enjoy the possibility of adding $=$ and $\times$ clues to the boundary.

Footnotes

Hilbert’s greatest hits. For other Hilbert bangers, see a fairly comprehensive list here. My favorites?

• Hilbert’s Basis Theorem paired with its existential (and controversial!) proof (for those who would prefer their mathematics with less theology, there is a constructive proof via Gröbner bases that came later)
• Hilbert’s Syzygy Theorem concerning the nontrivial relations (among relations, among relations…) among a system of polynomials in $n$ variables.

Kudos

• Shout-out to my office neighbor at Hamilton, Prof. Saber Ahmed, who has been subjected to many games of Tango and Queens, Torque, Torgo, Twango, Kleingo, Kleens, and versions of these and other games on weird shapes along with random musings about the geometry of the solutions to random subsets of games.