# Sudoku of different sizes

Consider a sudoku game played not necessarily in a $10\times 10$ grid, but in some $n\times n$ grid of the following form:

         1 2 3 ... n
2 1
3   1
.    .
.     .
.      .
n         1


such that all cells in the first row are participating in a "subsquare"- ie an arrangement where the digits in $(p,q)$ and $(a,b)$ contain the same digit, and $(p,b) and (a,q)$ contain the same digit. In this construction the $1$ in the top left corner participates in all the $2 \times 2$ subsquares in specific question. For $n=4$, here is one such arrangement:

     1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1


For $n=5$ here is one such square:

      1 2 3 4 5
2 1 4 5 3
3 5 1 2 4
4 3 5 1 2
5 4 2 3 1


For $n=6$ here is one such arrangement:

     1 2 3 4 5 6
2 1 4 3 6 5
3 5 1 6 4 2
4 6 5 1 2 3
5 3 6 2 1 4
6 4 2 5 3 1


For $n=7$ here is one such arrangement:

      1 2 3 4 5 6 7
2 1 4 5 6 7 3
3 7 1 2 4 5 6
4 6 7 1 2 3 5
5 3 6 7 1 2 4
6 4 5 3 7 1 2
7 5 2 6 3 4 1


For $n=8$ here is one such arrangement:

       1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 7 1 8 4 2 5 6
4 8 7 1 2 3 6 5
5 6 8 2 1 7 3 4
6 5 2 7 8 1 4 3
7 2 5 6 3 8 1 2
8 4 6 5 7 4 2 1


For $n=9$ here is one such arrangement:

      1 2 3 4 5 6 7 8 9
2 1 4 8 6 5 3 9 7
3 7 1 2 4 8 9 5 6
4 6 7 1 9 2 8 3 5
5 9 8 6 1 3 2 7 1
6 4 9 3 7 1 5 2 8
7 8 5 9 2 4 1 6 3
8 5 6 7 3 9 4 1 2
9 3 2 5 8 7 6 4 1

-
I don't know what you mean when you write, "the 1 in the top left corner participates in all the $2\times2$ subsquares in specific question." –  Gerry Myerson Jul 25 '12 at 23:39
Since I don't understand the condition, I have to ask whether the transpose of your $5\times5$ example is also an example. If it is, then we have proved that it's not true that for $n=5$ there is only one square of this form. –  Gerry Myerson Jul 25 '12 at 23:42
So the 1 in the top left corner is involved in a two by two subsquare with every cell in the top row and leftmost column. That is what I meant. –  Xuan Huang Jul 25 '12 at 23:50
Sorry, I still don't understand. In any array of symbols with a 1 in the upper left corner, the 1 in the upper left corner is involved in all those $2\times2$ subsquares. What is different about the involvement, or the subsquares, in the kind of array you want? –  Gerry Myerson Jul 26 '12 at 0:27
Nothing. I was only trying to convey that there might be other subsquares that the cells in the top row are involved in as well, that don't contain any of the ones the diagonal. –  Xuan Huang Jul 26 '12 at 0:30

I don't understand the question. If all you want is a Latin square with all entries on the upper-left to lower-right diagonal equal, a construction is given in Section 3 of A J W Hilton, On double diagonal and cross latin squares, J London Math Soc 6 (1973) 679-689, which is on the web here. In fact, Hilton does much more: if $n$ is even, he gets the upper-right to lower-left diagonal to be constant as well, and if $n$ is odd, he gets that other diagonal to be constant with two exceptions.

EDIT: Here's an explicit construction for the case $n$ even. Find a 1-factorization of $K_n$. If $(a,b),(c,d),\dots,(m,n)$ is one of the 1-factors, then put the same symbol into the squares $(a,b),(c,d),\dots,(m,n)$ and also the squares $(b,a),(d,c),\dots,(n,m)$ (since after all as an edge in $K_n$, $(a,b)$ is the same as $(b,a)$. That leaves the diagonal free for the remaining symbol.

For example, let's do $n=6$. A 1-factorization is given by 12, 36, 45; 13, 24, 56; 14, 26, 35; 15, 23, 46; 16, 25, 34. (A 1-factor is just a list of edges that uses each vertex exactly once; a 1-factorization is a list of 1-factors that includes every edge in the graph exactly once; there is a simple construction that finds a 1-factorization of $K_n$ for $n$ even). So I'll put 2 at locations $(1,2),(3,6),(4,5)$ and $(2,1),(6,3),(5,4)$; I'll put 3 at $(1,3),(2,4),(5,6)$ and $(3,1),(4,2),(6,5)$; and so on; then finish it off with 1 down the diagonal.

-
You misunderstood the question entirely. The question was to find a proof by construction for the statement that for all $n \ge 3$, there is a way to fill in the partial latin square at the top of the page. –  Xuan Huang Jul 26 '12 at 1:22
Did you look at the reference I gave? –  Gerry Myerson Jul 26 '12 at 2:08
I have seen the reference before. In the mean time, could you tell me what exactly you mean by a one-factorization? And by $K_n$? –  Xuan Huang Jul 26 '12 at 3:10
I have seen the reference before. In the mean time, could you tell me what exactly you mean by a one-factorization? And by $K_n$? –  Xuan Huang Jul 26 '12 at 3:42
@DanielleHuang I'm confused: you have 7 graph-theory tags, including questions where you specifically refer to $K_n$. How is the definition already supplied in the answer not sufficient? –  Erick Wong Jul 26 '12 at 4:56

The adjectives to describe these Latin squares are: reduced (meaning the first row and column are in order) and unipotent (meaning the main diagonal is fixed).

We will show that reduced unipotent Latin squares of order $n$ are equivalent to Latin squares of order $n-1$ that admit a special type of "transversal" along the main diagonal. A transversal of a Latin square is a collection of $n$ symbols containing one entry from each row, each column and each possible symbol.

Through a process, known as prolongation, from a Latin square of order $n$ with main diagonal $1,2,\ldots,n$ we can generate a Latin square of order $n+1$ with a transversal along the main diagonal. We delete the main diagonal, replace it with a new fixed symbol, after which there is a unique completion to $(n+1) \times (n+1)$ Latin square. This equivalence is illustrated (in reverse) below:

  1 2 3 4 5       . . . . .
2 1 4 5 3       . 1 4 5 3       2 4 5 3
3 5 1 2 4  <->  . 5 1 2 4  <->  5 3 2 4
4 3 5 1 2       . 3 5 1 2       3 5 4 2
5 4 2 3 1       . 4 2 3 1       4 2 3 5


(We can relabel the symbols as desired.) Moreover, and importantly, this process is reversible.

Given any Latin square with a transversal, we can permute the rows and symbols to construct a Latin square with $1,2,\ldots,n$ along the main diagonal. Hence, we have the following.

Theorem: A reduced unipotent Latin square of order $n$ exists if and only if there exists a Latin square of order $n-1$ with a transversal.

Thus, the asked question is exactly equivalent to:

Question: For which orders $n$, does there exist a Latin square of order $n-1$ that has a transversal?

There's probably a zillion ways to answer the above question. One way I find particularly quick, is to note that orthogonal Latin squares exist for all orders except $2$ and $6$. Any fixed symbol in one Latin square corresponds to a transversal in any orthogonal mate. We can use the OP's example for order $7$ to find a Latin square with a transversal of order $6$. There is only one Latin square of order $2$ (up to row/column/symbol permutations), and it doesn't have a transversal (which is why you didn't find a reduced unipotent Latin square of order $3$).

Hence, we have the following theorems.

Theorem: There exists a Latin square of order $n$ with a transversal for all orders $n \geq 1$ except $n=2$.

Theorem: There exists a reduced unipotent Latin square of order $n$ for all orders $n \geq 1$ except $n=3$.

A(nother) proof was given by McKay, McLeod, Wanless for $n \geq 5$ (among many other relevant results). We will give a constructive proof below:

Proof: If two Latin squares (of orders $n$ and $m$) have transversals along the main diagonal, then so does their direct product (which will have order $nm$).

For odd $n$, the Cayley table of $\mathbb{Z}_n$ has a transversal along the main diagonal. Examples of orders $2^2$ and $2^3$ are given by the OP. Combining these results, we can construct a Latin square of order $n$ with a transversal whenever $n \not\equiv 2 \pmod 4$.

Next, we will complete the proof by finding a transversal in a Latin square of order $2n$ for odd $n$ formed from switches in the Cayley table of $\mathbb{Z}_2 \times \mathbb{Z}_n$ for odd $n$. (Note that the Cayley table of $\mathbb{Z}_2 \times \mathbb{Z}_n \cong \mathbb{Z}_{2n}$ does not have transversals, so some switching is necessary.)

This will be largely a "proof by example", since it would be considerable effort to cross all the t's and dot all the lowercase j's.

Step 1: Using two transversals in the Cayley table of $\mathbb{Z}_n$, we generate a selection of $2n$ entries in the Cayley table of $\mathbb{Z}_2 \times \mathbb{Z}_n$ as follows:

$$\begin{array}{c} \begin{array}{|ccccc|} \hline \mathbf{\large 1} & 2 & 3 & 4 & 5 \\ 2 & 3 & \mathbf{\large 4} & 5 & 1 \\ 3 & 4 & 5 & 1 & \mathbf{\large 2} \\ 4 & \mathbf{\large 5} & 1 & 2 & 3 \\ 5 & 1 & 2 & \mathbf{\large 3} & 4 \\ \hline \end{array} \\ \begin{array}{|ccccc|} \hline 1 & \mathbf{\large 2} & 3 & 4 & 5 \\ 2 & 3 & 4 & \mathbf{\large 5} & 1 \\ \mathbf{\large 3} & 4 & 5 & 1 & 2 \\ 4 & 5 & \mathbf{\large 1} & 2 & 3 \\ 5 & 1 & 2 & 3 & \mathbf{\large 4} \\ \hline \end{array} \end{array} \rightarrow\begin{array}{|ccccc|ccccc|} \hline \mathbf{\large 1} & 2 & 3 & 4 & 5 & 1' & 2' & 3' & 4' & 5' \\ 2 & 3 & \mathbf{\large 4} & 5 & 1 & 2' & 3' & 4' & 5' & 1' \\ 3 & 4 & 5 & 1 & \mathbf{\large 2} & 3' & 4' & 5' & 1' & 2' \\ 4 & 5 & 1 & 2 & 3 & 4' & \mathbf{\large 5'} & 1' & 2' & 3' \\ 5 & 1 & 2 & 3 & 4 & 5' & 1' & 2' & \mathbf{\large 3'} & 4' \\ \hline 1' & \mathbf{\large 2'} & 3' & 4' & 5' & 1 & 2 & 3 & 4 & 5 \\ 2' & 3' & 4' & \mathbf{\large 5'} & 1' & 2 & 3 & 4 & 5 & 1 \\ 3' & 4' & 5' & 1' & 2' & \mathbf{\large 3} & 4 & 5 & 1 & 2 \\ 4' & 5' & 1' & 2' & 3' & 4 & 5 & \mathbf{\large 1} & 2 & 3 \\ 5' & 1' & 2' & 3' & 4' & 5 & 1 & 2 & 3 & \mathbf{\large 4} \\ \hline \end{array}.$$

This gives a $2p \times 2p$ Latin square with a selection of $2p$ entries with one representative from each row and column, but more than one copy of some symbols. But, importantly, exactly two symbol representatives from each set $\{i,i'\}$, which is why the next step works.

Step 2: We then "break" the symbol repeats by performing intercalate switches in the Latin square as follows:

$$\rightarrow \begin{array}{|ccccc|ccccc|} \hline \mathbf{\large 1'} & 2 & 3 & 4 & 5 & 1 & 2' & 3' & 4' & 5' \\ 2 & 3 & \mathbf{\large 4} & 5 & 1 & 2' & 3' & 4' & 5' & 1' \\ 3 & 4 & 5 & 1 & \mathbf{\large 2} & 3' & 4' & 5' & 1' & 2' \\ 4 & 5 & 1 & 2 & 3 & 4' & \mathbf{\large 5'} & 1' & 2' & 3' \\ 5 & 1 & 2 & 3 & 4 & 5' & 1' & 2' & \mathbf{\large 3'} & 4' \\ \hline 1 & \mathbf{\large 2'} & 3' & 4' & 5' & 1' & 2 & 3 & 4 & 5 \\ 2' & 3' & 4' & \mathbf{\large 5'} & 1' & 2 & 3 & 4 & 5 & 1 \\ 3' & 4' & 5' & 1' & 2' & \mathbf{\large 3} & 4 & 5 & 1 & 2 \\ 4' & 5' & 1' & 2' & 3' & 4 & 5 & \mathbf{\large 1} & 2 & 3 \\ 5' & 1' & 2' & 3' & 4' & 5 & 1 & 2 & 3 & \mathbf{\large 4} \\ \hline \end{array}.$$

In the above example, we switched

1  1'  ->  1' 1
1' 1       1  1'


in rows $1$ and $6$ and columns $1$ and $6$. We keep switching until we run out of symbol repeats. Importantly, we perform switches in which (a) symbols $i$ are switched with $i'$, and (b) exactly one cell in the $2n$ entries is affected.

$$\rightarrow \begin{array}{|ccccc|ccccc|} \hline \mathbf{\large 1'} & 2 & 3 & 4 & 5 & 1 & 2' & 3' & 4' & 5' \\ 2 & 3 & \mathbf{\large 4'} & 5 & 1 & 2' & 3' & 4 & 5' & 1' \\ 3 & 4 & 5 & 1 & \mathbf{\large 2} & 3' & 4' & 5' & 1' & 2' \\ 4 & 5' & 1 & 2 & 3 & 4' & \mathbf{\large 5} & 1' & 2' & 3' \\ 5 & 1 & 2 & 3 & 4 & 5' & 1' & 2' & \mathbf{\large 3'} & 4' \\ \hline 1 & \mathbf{\large 2'} & 3' & 4' & 5' & 1' & 2 & 3 & 4 & 5 \\ 2' & 3' & 4 & \mathbf{\large 5'} & 1' & 2 & 3 & 4' & 5 & 1 \\ 3' & 4' & 5' & 1' & 2' & \mathbf{\large 3} & 4 & 5 & 1 & 2 \\ 4' & 5 & 1' & 2' & 3' & 4 & 5' & \mathbf{\large 1} & 2 & 3 \\ 5' & 1' & 2' & 3' & 4' & 5 & 1 & 2 & 3 & \mathbf{\large 4} \\ \hline \end{array}$$

Step 3: Permute the rows of the Latin square so that a transversal appears on the main diagonal.

Step 4: Prolong the Latin square, then permute the symbols to taste. End proof.

-