16.1: Latin Squares and Sudokus

Last updated
Save as PDF

Page ID: 60155

Joy Morris
University of Lethbridge

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

You can think of a Latin square as a Sudoku puzzle that can be of any (square) size, and does not have the requirement that every value appear in each of the outlined smaller subsquares.

Definition: Latin Square

A Latin square of order \(n\) is an \(n \times n\) array whose entries are elements of a set \(N\) of cardinality \(n\), with the property that every element of \(N\) appears exactly once in each row and each column.

Example \(\PageIndex{1}\)

Here is a Latin square of order \(4\):

\[ 1 \; \; 2 \; \; 3\; \; 4 \\ 4 \;\; 1 \; \; 2 \; \; 3 \\ 3 \; \; 4 \; \; 1\; \; 2 \\ 2 \; \; 3\; \; 4 \; \; 1 \]

Solution

Notice that in the above example, we placed the numbers \(1\), \(2\), \(3\), and \(4\) in the first row, in that order. For each subsequent row, we shifted the numbers one place to the right (wrapping around). This same technique (placing the numbers from \(1\) through \(n\) across the first row) will work to construct a Latin square of order \(n\).

So you might think (with reason) that Latin squares aren’t very interesting. However, even knowing that there is a Latin square of every possible order and they are easy to construct, there remain some interesting related questions.

Some of these questions are related to Sudokus. If we fill in some entries of a Latin square, are there conditions on these entries that guarantee that this can be completed to a full Latin square? Are there conditions under which we can be sure that a partial Latin square has a unique completion to a full Latin square?

Some of these questions have easy answers that are not what we are really looking for. For example, if we give you all but one entry of a Latin square (or Sudoku), then if it can be completed at all, the completion will be unique. However, some interesting mathematical work has been done on these problems, both for Latin squares and for Sudokus.

There are no known examples in which a Sudoku puzzle with \(16\) or fewer squares pre-filled, can be completed uniquely. However, there are tens of thousands of (non-isomorphic) ways of pre-filling \(17\) entries of a Sudoku puzzle, that have a unique completion.

Looking only at “non-isomorphic” examples is important, because there are many ways of creating Latin squares (or Sudoku puzzles) that are essentially the same. The following operations take a Latin square to another Latin square that is structurally essentially the same:

Permuting of the symbols used in the set \(N\). For example, changing every \(1\) to a \(2\) and every \(2\) to a \(1\).
Interchanging any two rows.
Interchanging any two columns.
Making all of the rows into columns, and all of the columns into rows.

Exercise \(\PageIndex{1}\)

1) Prove that interchanging two rows of a Latin square, yields a Latin square.

2) Complete the following Latin square. Is the completion unique?

\( 1 \; \; \_ \; \; 4\; \; \_\; \\ \_ \; \; 1 \; \; \_\; \; \_\; \\ \_ \; \; \_ \; \; \_\; \; 3\; \\ \_ \; \; \_ \; \;\_\; \; \_\; \\ \)

3) Use the method described at the start of this chapter to create a Latin square of order \(5\). What \(3\) of the operations listed above that change a Latin square to an isomorphic Latin square, are required to arrive at the following result?

\( 5 \; \; 1 \; \; 4\; \; 2\; \; 3 \\ 1 \; \; 3 \; \; 5\; \; 4\; \; 2\\ 4 \; \; 5 \; \; 2\; \; 3\; \; 1\\ 2 \; \; 4 \; \; 3\; \; 1\; \; 5 \\ 3 \; \; 2 \; \; 1\; \; 5\; \; 4 \)

4) Show there are exactly two different Latin squares of order \(3\) whose first row is \(1\), \(2\), \(3\).

5) Show there are exactly twelve different Latin squares of order \(3\) whose entries are the numbers \(1\), \(2\), \(3\).

[Hint: Use Problem \(4\).]

6) There are four different Latin squares of order \(4\) whose first row is \(1\), \(2\), \(3\), \(4\) and whose first column is also \(1\), \(2\), \(3\), \(4\). That is, there are only four ways to complete the following Latin square:

\( 1 \; \; 2 \; \; 3\; \; 4\; \\ 2 \; \; \_ \; \; \_\; \; \_\; \\ 3 \; \; \_ \; \; \_\; \; \_\; \\ 4 \; \; \_ \; \;\_\; \; \_\; \\ \)

Find all four.

[Hint: Each of the possibilities for the second entry of the second row can be completed in only one or two ways.]