Is a Sudoku a Cayley table for a group?

Question

I want to know if the popular Sudoku puzzle is a Cayley table for a group.

Methods I've looked at: Someone I've spoken to told me they're not because counting the number of puzzle solutions against the number of tables with certain permutations of elements, rows and columns, the solutions are bigger than the tables, but I can't see why because I don't know how to count the different tables for a group of order 9, and then permute the rows, columns and elements in different ways. Also I believe the rotations/reflections will matter in comparing these numbers too. It would also be nice if there was a way to know if the operation is associative just from the table.

Answer 1

A Cayley table for a group can never be a sudoku. Assume you have a $9 \times 9$ Cayley table for a group of order $9$, and say your identity element is at index $1 \le i \le 9$. Then row $i$ and column $i$ are symmetric to each other because they correspond to multiplication with the identity. In particular, if you look at the $3\times3$ sub-square containing the element of coordinates $(i,i)$, this square has duplicates (because it contains symmetric elements of row $i$ and column $i$). So the table isn't a Sudoku.

If you allow to swap the rows or columns, this is possible. Take the table of $G = \mathbb{Z}/9\mathbb{Z}$ (I wrote $0$ instead of $9$ for convenience): $$ \begin{array}{r|lllllllll} +&0&1&2&3&4&5&6&7&8\\ \hline 0&0&1&2&3&4&5&6&7&8\\ 1&1&2&3&4&5&6&7&8&0\\ 2&2&3&4&5&6&7&8&0&1\\ 3&3&4&5&6&7&8&0&1&2\\ 4&4&5&6&7&8&0&1&2&3\\ 5&5&6&7&8&0&1&2&3&4\\ 6&6&7&8&0&1&2&3&4&5\\ 7&7&8&0&1&2&3&4&5&6\\ 8&8&0&1&2&3&4&5&6&7\\ \end{array}$$

And swap the rows in order $0,3,6,1,4,7,2,5,8$, to obtain the Sudoku

$$ \begin{array}{r|lll|lll|lll} +&0&1&2&3&4&5&6&7&8\\ \hline 0&0&1&2&3&4&5&6&7&8\\ 3&3&4&5&6&7&8&0&1&2\\ 6&6&7&8&0&1&2&3&4&5\\ \hline 1&1&2&3&4&5&6&7&8&0\\ 4&4&5&6&7&8&0&1&2&3\\ 7&7&8&0&1&2&3&4&5&6\\ \hline 2&2&3&4&5&6&7&8&0&1\\ 5&5&6&7&8&0&1&2&3&4\\ 8&8&0&1&2&3&4&5&6&7\\ \end{array}$$

Answer 2

It is easy to construct a Sudoku that cannot be a Cayley table. Not even if you label the rows and columns independently from each other. Consider the following. $$ \begin{array}{ccc|ccc|ccc} 1&2&3&4&5&6&7&8&9\\ 4&5&6&7&8&9&1&3&2\\ 7&8&9&1&2&3&4&5&6\\ \hline 2&3&1&5&6&4&9&7&8\\ 5&6&4&8&9&7&2&1&3\\ 8&9&7&2&3&1&6&4&5\\ \hline 3&1&2&6&4&5&8&9&7\\ 6&4&5&9&7&8&3&2&1\\ 9&7&8&3&1&2&5&6&4 \end{array} $$ My argument only needs the two first rows. The rest were filled in just to leave no doubt about the fact that those two rows form a part of a complete Sudoku.

We see that we get the second row from the first by applying the permutation $\sigma=(147)(258369)$ to it. This is all we need to prove that this is not a Cayley table. If in a Cayley table the first row has $a$ as the common left factor and the second row has $b$ as the common left factor, we get the second row from the first by multiplying everything from the left by $c:=ba^{-1}$. If $n=\operatorname{ord}(c)$ then the permutation $\sigma$ bringing the first row to the second will then only have cycles of length $n$ as the cycles act transitively on right cosets $Hx$, $H=\langle c\rangle, x\in G$.

But our $\sigma$ has cycle type $(3,6)$. This already gives two obvious contradictions:

• the lengths of the cycles vary, and
• $\sigma$ has order six, so cannot be an element of a group of order nine.

Answer 3

Another approach: We are considering a group of order $9 = 3^2$ so a prime squared. It is well known that groups of order $p^2$ must be abelian. (abelian = commutative) Now a soduku can never represent an abelian group, as it is never symmetric. (Symmetric as in matrices, that means symmetric wrt. the diagonal.)