Combinatorics

Section 16.1 Latin squares and Sudokus

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.

Notice that in the above example, we placed the numbers \(1, 2, 3\text{,}\) 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\text{.}\)

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.

It has recently been proved (using computers) that a Sudoku puzzle with 16 or fewer squares pre-filled cannot be completed uniquely. This is a theorem by Gary McGuire (1967—), Bastian Tugemann, and Gilles Civario (1972—), published in \(2014\) in Experimental Mathematics. The published version is available online by subscription to the journal, but a preprint is freely available on the widely-used “ar\(\chi\)iv” scientific preprint server hosted by Cornell University. However, there are tens of thousands of (non-isomorphic) ways of pre-filling 17 entries of a Sudoku puzzle, that have a unique completion. Gordon F. Royle (1962—) built a web page with a complete list of those that were known at the time. His work on this was used by McGuire, Tugemann, and Civario in their paper. The original web page was inaccessible at the most recent editing of this book, but there is a copy available through the Wayback Machine's archive of the internet.

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\text{.}\) For example, changing every \(1\) to a \(2\) and every \(2\) to a \(1\text{.}\)

• Interchanging any two rows.

• Interchanging any two columns.

• Making all of the rows into columns, and all of the columns into rows.