# 15.2: Latin squares and Sudokus - Mathematics

15.2: Latin squares and Sudokus - Mathematics

This number can be simplified to 71 after taking more symmetries into account [18].

Arratia, R., DeSalvo, S.: Poisson and independent process approximation for random combinatorial structures with a given number of components, and near-universal behavior for low rank assemblies. arXiv preprint arXiv:1606.04642 (2016)

Arratia, R., DeSalvo, S.: Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example. Comb. Probab. Comput. 25(3), 324–351 (2016)

Colbourn, C.J.: The complexity of completing partial latin squares. Discrete Appl. Math. 8(1), 25–30 (1984)

Dahl, G.: Permutation matrices related to sudoku. Linear Algebra Appl. 430(8), 2457–2463 (2009)

DeSalvo, S.: Probabilistic divide-and-conquer: deterministic second half. arXiv preprint arXiv:1411.6698 (2014)

DeSalvo, S.: Improvements to exact Boltzmann sampling using probabilistic divide-and-conquer and the recursive method. arXiv preprint arXiv:1608.07922 (2016)

Devroye, L.: Nonuniform random variate generation. Handb. Oper. Res Manag. Sci. 13, 83–121 (2006)

Diaconis, P., Sturmfels, B., et al.: Algebraic algorithms for sampling from conditional distributions. Ann. Stat. 26(1), 363–397 (1998)

Duchon, P., Flajolet, P., Louchard, G., Schaeffer, G.: Boltzmann samplers for the random generation of combinatorial structures. Combin. Probab. Comput. 13(4–5), 577–625 (2004)

Felgenhauer, B., Jarvis, F.: Mathematics of sudoku i. Math. Spectr. 39(1), 15–22 (2006)

Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)

Fontana, R.: Fractions of permutations. an application to sudoku. J. Stat. Plan. Inference 141(12), 3697–3704 (2011)

Fontana, R.: Random latin squares and sudoku designs generation. arXiv preprint arXiv:1305.3697 (2013)

Fontana, R., Rapallo, F., Rogantin, M.P.: Markov bases for sudoku grids. In: Advanced Statistical Methods for the Analysis of Large Data-Sets, pages 305–315. Springer, (2012)

Godsil, C.D., McKay, B.D.: Asymptotic enumeration of latin rectangles. J. Comb. Theory Ser. B 48(1), 19–44 (1990)

Huber, M.L.: Perfect Simulation. Chapman & Hall/CRC Monographs on Statistics & Applied Probability. Taylor & Francis, (2015)

Jacobson, M.T., Matthews, P.: Generating uniformly distributed random latin squares. J. Comb. Des. 4(6), 405–437 (1996)

Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 51(4), 671–697 (2004). (electronic)

Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Soc, Providence (2009)

Newton, P.K., DeSalvo, S.A.: The shannon entropy of sudoku matrices. In: Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, page rspa20090522. The Royal Society (2010)

Nijenhuis, A., Wilf, H.S.: A method and two algorithms on the theory of partitions. J. Comb. Theory Ser. A 18, 219–222 (1975)

Nijenhuis, A., Wilf, H.S.: Combinatorial algorithms. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, second edition, 1978. For computers and calculators, Computer Science and Applied Mathematics (1978)

Random Struct. Algor. Exact sampling with coupled markov chains and applications to statistical mechanics. 9(1–2), 223–252 (1996)

Ridder, A.: Counting the number of sudoku’s by importance sampling simulation (2013)

Russell, E., Jarvis, F.: Mathematics of sudoku II. Math. Spectr. 39(2), 54–58 (2006)

Sloane, N.J.A.: Online Encyclopedia of Integer Sequences. Published electronically at http://www.oeis.org/

Stones, D.S.: The many formulae for the number of Latin rectangles. Electron. J. Comb. 17(1), Article 1 46 (2010)

van Lint, J.H., Wilson, R.M.: A Course in Combinatorics, 2nd edn. Cambridge University Press, Cambridge (2001)

Von Neumann, J.: Various techniques used in connection with random digits. Appl. Math Ser. 12(36–38), 1 (1951)

Yordzhev, K.: On the number of disjoint pairs of s-permutation matrices. Discrete Appl. Math. 161(18), 3072–3079 (2013)

Yordzhev, K.: Random permutations, random sudoku matrices and randomized algorithms. arXiv preprint arXiv:1312.0192, (2013)

## Latin Squares

J. Dénes , A.D. Keedwell , in Annals of Discrete Mathematics , 1991

### (5) Complete sets of column orthogonal latin squares and affine planes

K. Vedder (1983) has defined two latin squares A = [aij] and B = [bij] of the same order n to be column orthogonal if, for each fixed pair of integers j, k, we have aij = bik for at most one value of i. He has given the following example of a set of four mutually column- orthogonal latin squares of order 3 defined on the symbol set <1, 2, 3, 4>:

Such a set of n squares of order n−1 based on a set of n symbols and with one of the symbols omitted from each square of the set, he has called a complete set of mutually column orthogonal latin squares of type n−1. He has proved the following theorem. (Compare Theorem 1.1 of this Chapter and its corollary.)

A complete set of mutually column orthogonal latin squares of type n−1 is equivalent to a projective (or affine) plane of order n.

Proof. We designate the various parallel classes of the affine plane by the capital letters A, E, B1, B2, …, Bn−1 as in Theorem 1.1 of this Chapter. Let the lines of these parallel classes be labelled as follows: a1, a2, …, an are the lines of the class A eo,e1, …, en−1 are the lines of the class E bj1, bj2, …, bjn are the lines of the class Bj. Every point P(h, i) of the plane can then be identified with a set of n+1 numbers (h, i, ℓ1, ℓ2, …, ℓn−1) describing the n+1 lines eh, ai, b1ℓ1, b2ℓ2, …, bn−1ℓn−1 with which it is incident, one from each of the n+1 parallel classes.

We construct a set of column orthogonal latin squares A1, A2, … An in the following way. The columns of the i-th square Ai are defined by the n lines through the point (0, i). Let bjℓ be one of these lines and suppose that it contains the points (1, i1), (2, i2), …, (n−1, in−1). Then the j-th column of the square Ai is the column vector (i1, i2, …, in−1) T . Since each of the n points on the line bjℓ is incident with a different line of the parallel class A, the set 1, i2, …, in−1> is the set of natural numbers <1, 2, …, n>. Also, since two lines bjℓ and bkm of distinct parallel classes have exactly one point in common which is the point (0, i) if and only if bjℓ and bkm define two columns of the same square Ai, each square is latin and columns of distinct squares agree in at most one row. That is, the squares form a complete set of mutually column orthogonal latin squares of type n−1, as required.

From the method of construction, it is clear that if j≠k then the j-th column of square Ai agrees in exactly one place with the k-th column of each other square, while on the other hand the j-th columns of each pair of the squares do not agree in any place. A complete set of mutually column orthogonal latin squares which has this property will be called normalized. It is easy to see that any complete set can be so normalized and then, by reversing the construction described above, we complete the proof of our theorem.

Vedder has shown that, from a normalized complete set of mutually column orthogonal latin squares of type n−1, we can construct a set of n−1 mutually column orthogonal nxn latin squares and conversely. He has called a set of the latter type a complete set of mutually column orthogonal latin squares of type n.

Let A1, A2, …, An be a normalized complete set of mutually column orthogonal latin squares of type n−1. We form an nxn latin square Bj (j = 1, 2, …, n−1) by taking as the columns of Bj, the j-th columns of A1, A2, …, An respectively each headed by its missing symbol. The fact that these missing symbols are all different follows from the construction of Theorem 5.1 . The fact that each of the squares Bj is latin follows from the fact that no two j-th columns agree in any place. Hence, the squares B1, B2, …, Bn−1 form a complete set of mutually column orthogonal latin squares of type n. This construction is illustrated for the case n = 4 in Figure 5.1 .

In general, complete sets of mutually orthogonal latin squares need not be mutually column orthogonal (the complete set of m.o.l.s. which represents the Hughes Plane of order 9 given in the next section is a counterexample). However, Vedder has shown that orthogonal latin squares which are constructed by the automorphism method of H. B. Mann (see H. B. Mann (1942) or page 234 of [DK]) are necessarily column orthogonal also. In particular:

A complete set of m.o.l.s. based on the addition group of a nearfield and constructed by the automorphism method (using multiplications) is a complete set of mutually column orthogonal latin squares of type n.

If $L_n$ is the number of Latin squares of order $n$, and $R_n$ is the number of reduced Latin squares of order $n$, then $L_n = n!(n-1)! R_n.$ The factor $n! (n-1)!$ comes about by counting:

Given any Latin square of order $n$, there is a unique permutation of the columns so that the first row is in order ($1,2,ldots,n$), after which there is a unique permutation of the rows which fixes the first row so that the first column is in order.

In the other direction, given a reduced Latin square of order $n$, if we permute the rows except the first and permute the columns, we generate $n! (n-1)!$ distinct Latin squares of order $n$.

So, every reduced Latin square corresponds to $n! (n-1)!$ (not necessarily reduced) Latin squares, and every (not necessarily reduced) Latin square gives exactly one reduced Latin square.

As such, computing $L_n$ is effectively the same as computing $R_n$. While there are many formulae for the number of Latin squares, computationally they're only effective up to $n=11$. With the current best counting technique (Sade's method), as hardware improves, we might see $L_<12>$ in our lifetimes.

As far as I know, Sade's method is the only method which has been used for $n geq 10$.

For orders $n leq 9$, it is possible to generate main class representatives for each main class, computing their main class size using nauty, the sum of which equals $L_n$ (not an easy task for $n=9$ [I'm not sure if anyone has actually done it this way] representatives can be downloaded on Brendan McKay's website for $n leq 8$).

It possible to use Doyle's formula to compute the number of $6$-line Latin rectangles, which, for $7$ columns, is equal to $L_7$ (ref.).

Birken, Marcia and Coon, Anne C. (2008) Discovering Patterns in Mathematics and Poetry, Amsterdam, Rodopi.

Fishwick, Duncan (1964) ‘On the Origin of the Rotas-Sator Square.’ The Harvard Theological Review, vol. 57, no. 1, 1964, pp. 39–53. http://docshare02.docshare.tips/files/16340/163404657.pdf

Glaz, Sarah (2012) ‘Mathematical Pattern Poetry.’ Bridges 2012 Conference Proceedings http://m.archive.bridgesmathart.org/2012/bridges2012-65.pdf

Coxson, G. E. ‘JoAnne Growney’s Poetry-With-Mathematics Blog — An Appreciation,’ Journal of Humanistic Mathematics, Volume 2 Issue 2 (July 2012), pages 140-150. DOI: 10.5642/ jhummath.201202.12. Available at: https://scholarship.claremont.edu/jhm/vol2/iss2/12

Hix, H. L. (2000) Rational Numbers, Truman State University Press

Lajeunesse, Lisa (2019) ‘Graeco-Latin Square Poems.’ Bridges 2019 Conference Proceedingshttp://archive.bridgesmathart.org/2019/bridges2019-35.pdf

May D. (2020) ‘Poems Structured by Mathematics’. In: Sriraman B. (eds) Handbook of the Mathematics of the Arts and Sciences. Springer, Cham.

Motoyama, Hiroshi (2001) Theories of the Chakras. New Age Books, Delhi

Plato, Timaeus and Critias, tr. Desmond Lee (1965). Penguin Classics, Middlesex

Researchers in combinatorial design theory and areas of statistics such as design and analysis of experiments. The book may also be of interest to amateur mathematicians interested in magic squares, in designing games tournaments and/or in latin squares related to Sudoku puzzles

Chapter 1: Elementary properties

• 1.1 The multiplication table of a quasigroup
• 1.2 The Cayley table of a group
• 1.3 Isotopy
• 1.4 Conjugacy and parastrophy
• 1.5 Transversals and complete mappings
• 1.6 Latin subsquares and subquasigroups

Chapter 2: Special types of latin square

• 2.1 Quasigroup identities and latin squares
• 2.2 Quasigroups of some special types and the concept of generalized associativity
• 2.3 Triple systems and quasigroups
• 2.4 Group-based latin squares and nuclei of loops
• 2.5 Transversals in group-based latin squares
• 2.6 Complete latin squares

Chapter 3: Partial latin squares and partial transversals

• 3.1 Latin rectangles and row latin squares
• 3.2 Critical sets and Sudoku puzzles
• 3.3 Fuchs’ problems
• 3.4 Incomplete latin squares and partial quasigroups
• 3.5 Partial transversals and generalized transversals

Chapter 4: Classification and enumeration of latin squares and latin rectangles

• 4.1 The autotopism group of a quasigroup
• 4.2 Classification of latin squares
• 4.3 History of the classification and enumeration of latin squares
• 4.4 Enumeration of latin rectangles
• 4.5 Enumeration of transversals
• 4.6 Enumeration of subsquares

Chapter 5: The concept of orthogonality

• 5.1 Existence questions for incomplete sets of orthogonal latin squares
• 5.2 Complete sets of orthogonal latin squares and projective planes
• 5.3 Sets of MOLS of maximum and minimum size
• 5.4 Orthogonal quasigroups, groupoids and triple systems
• 5.5 Self-orthogonal and other parastrophic orthogonal latin squares and quasigroups
• 5.6 Orthogonality in other structures related to latin squares

Chapter 6: Connections between latin squares and magic squares

• 6.1 Diagonal (or magic) latin squares
• 6.2 Construction of magic squares with the aid of orthogonal latin squares
• 6.3 Additional results on magic squares
• 6.4 Room squares: their construction and uses

Chapter 7: Constructions of orthogonal latin squares which involve rearrangement of rows and columns

## Latin Squares

A Latin square of order n is an array of n symbols in which each symbol occurs exactly once in each row and exactly once in each column. See the interactivity Teddy Town for some examples of Latin squares.

Construct some Latin squares for yourself and see how many different arrangements you can find for each value of n. Two Latin squares are essentially the same, the mathematical term is isomorphic, if one can be transformed into the other by re-naming the elements or by interchanging rows or interchanging columns.

For example the coloured discs in this illustration form a Latin square of order 3. This Latin square is isomorphic to the square with the symbols B, R and G and to the square with symbols 1, 2 and 3.

Latin squares of all orders $m> 2$ can be constructed using modular arithmetic as in this example for $m=5$. The entry $S_$ in row $i$ column $j$ is given by $S_=i+j$ (mod $5$), where this is defined to be the remainder when the sum $i+j$ is divided by $5$.

For example the entry in the 4th row and 3rd column is given by $S_<4,3>=4+3$ (mod $5$) $=7$ (mod $5$) $=2$.

The same arrays can be found by simply cycling the elements so this method becomes more useful when solving problems involving combinations of two Latin squares.

Two Latin squares are said to be orthogonal if they can be combined cell by cell so that each cell consists of a different pair of symbols.

The two Latin squares of order 3, given in paragraph three above are not orthogonal because in the first row and first column the combination is B1 and the same combination occurs in the second row and second column. However the Latin squares on the right are orthogonal.

Try making orthogonal Latin squares for yourself using the honour cards (Ace, King, Queen, Jack) from a standard pack of playing cards. First ignore the suits altogether and concentrate on arranging the 4 by 4 array so that each row and column has an Ace, a King, a Queen and a Jack in it, or equivalently so that no row or column has two Aces, or two Kings etc. Note down the arrangement.

Now concentrate on the suits and ignore the pictures and note down the arrangement of the suits. Because each card is different, that is all the combinations are different, for example Ace of Spades, Ace of Hearts, Ace of Diamonds and Ace of Clubs, the Latin square of 'suits' is necessarily orthogonal to the Latin square of 'pictures'.

In 1783 Euler made a conjecture about orthogonal Latin squares and it took nearly 200 years for mathematicians to prove that orthogonal Latin squares exist for all orders except 2 and 6.

How many different solutions can you find to the following problem that was originally posed by Euler?

"Arrange 25 officers, each having one of five different ranks and belonging to one of five different regiments, in a square formation 5 by 5, so that each row and each file contains just one officer of each rank and just one from each regiment."

The corresponding problem with 36 officers of six different ranks and belonging to six different regiments cannot be solved although for 49 officers it is easy to solve as shown above.

## 15.2: Latin squares and Sudokus - Mathematics

Construction III.1.1 - Let b1 ,b2 . bn be the elements of a finite field GF(n) where n = p k . Let b1 be the multiplicative identity ( = 1) and bn be the additive identity ( = 0) of GF(n). For e = 1,2, . n-1 define the n × n array L (e) = (aij (e) ) by taking aij (e) = (be × bi ) + bj, where the operations on the right are in the field. The resulting squares form a complete set of MOLS of order n.

Homework: Construct complete sets of MOLS of orders 8 and 9 and then put them into standard form

Proof: We must show that each L is in fact Latin and that any pair of them are orthogonal.

We first show that L (e) is a Latin square. Suppose L (e) had the same element appear in row i twice, then aij (e) = aik (e) . So, we would have be × bi + bj = be × bi + bk so, by using field properties we have bj = bk , and therefore j = k. Thus, all the elements in the same row are distinct. Similarly, ( fill in the details ) we can show that all the elements in a column are distinct. Thus, L (e) is a Latin square for any value of e.

Now consider two squares L (e) and L (f) . Suppose that (aij (e) , aij (f) ) = (akm (e) , akm (f) ) which implies, aij (e) = akm (e) and aij (f) = akm (f) . This leads to two equations, be × bi + bj = be × bk + bm and bf × bi + bj = bf × bk + bm. Subtracting the second from the first and then using the distributive laws gives, (be - bf ) × bi = (be - bf ) × bk and since ef, be - bf0 and we may conclude that bi = bk , so i = k. Using this in the first of our original equations, permits us to conclude that bj = bm and so j = m. We have shown that the ordered pairs are unique and so the squares are orthogonal.

Notice that in this construction the first square has ij-th entry equal to bi + bj , so that this first square is an isotope of the addition table of the field. Also notice, in the examples you have worked out, that each of the other squares in the set is just a row permutation of the first square ( try to prove this for homework ). MOLS that are related in this way are said to be based on the original square. This construction thus gives a set of MOLS based on the additive group of a field (an elementary abelian p-group).

Research question: What is the largest number of MOLS in a set based on a cyclic group of non-prime order? (For prime order the cyclic group is the additive group of a field and so a complete set exists, but for non-prime orders in general the answer is not known.)

As we will see later in the term, there are complete sets of MOLS which do not arise from this construction. Also, there are methods of constructing sets of MOLS which do not guarantee complete sets as this construction does.

### Affine Planes from MOLS

Let L1, L2, . Lq-1 be a complete set of MOLS of order q and A a q × q matrix containing q 2 distinct symbols. We define sets of size q (lines of the affine plane) on this set of q 2 symbols (points of the affine plane) in the following way: There are q sets which are the rows of A, and q sets which are the columns of A. The remaining q 2 - q sets are formed by taking each Li in turn, superimposing it on A and taking as sets the elements of A which correspond to a single symbol in the Li.

As an example consider the set of 3 MOLS of order 4: Now, let A be the matrix, The lines of the affine plane are: <1,2,3,4> <5,6,7,8> <9,10,11,12> <13,14,15,16> <1,5,9,13> <2,6,10,14> <3,7,11,15> <4,8,12,16>- from the rows and columns, and
<1,6,11,16> <2,5,12,15> <3,8,9,14> <4,7,10,13> <1,7,12,14> <2,8,11,13> <3,5,10,16> <4,6,9,15> <1,8,10,15> <2,7,9,16> <3,6,12,13> <4,5,11,14>- from the Latin squares.

Exercise: Construct two affine planes from the 2 MOLS of order 3.

We can also reverse the construction and produce a complete set of MOLS from an affine plane in the following way:

Let be an affine plane of order n. For each parallel class of lines of , arbitrarily label with the digits 1. n each line of the parallel class. Now select two parallel classes. The lines contained in these parallel classes will be used to index rows and columns of the Latin squares, so label one of the classes R and the other C. The n 2 points of intersection of the lines in R and C are associated with pairs of numbers, the number of the line in R and the number of the line in C. Now, for each parallel class in other than R or C, we will form a Latin square in the following way: If P is a parallel class, we have already labeled all the lines in P. The n 2 points of intersection of the R and C lines must all lie on the n labeled lines in P. In the cell of the square corresponding to one of the intersection points we place the label of the line in P which passes through this point. It is easy to see that the square produced this way is a Latin square of order n. This procedure is repeated for each of the parallel classes other than R or C, giving n-1 Latin squares.

To see that they are mutually orthogonal, consider two such squares and suppose that when superimposed there are two cells containing (a,b). Since the two cells of the first square received the label a, the two points which correspond to the cells must have been on the same line (labeled a) of the parallel class corresponding to the first square. Since these same cells have the label b in the second square, the two points must also be on the line labeled b contained in a different parallel class. This is impossible by axiom A1, so we see that these squares must be mutually orthogonal.

By Construction III.1.1 and the above construction we see that an affine plane of order n always exists if n is a prime or prime power, i.e., the order of a finite field. The only theorem that we have which rules out some affine planes is the following:

Theorem VIII.1.4 - [Bruck-Ryser Thm.] If n 1 or 2 mod 4 then an affine (projective) plane of order n does not exist unless n is the sum of two integral squares.

This theorem implies that there does not exist an affine (projective) plane of order 6, a result we could have inferred since no pair, let alone a complete set, of MOLS of order 6 exists. Notice that, since 10 = 9 + 1, this theorem says nothing about the existence of a projective plane of order 10. An extremely long computer search has finally proved that this plane does not exist (see note at the end of the chapter). The smallest open case is n = 12 which the Bruck-Ryser theorem does not cover and then n = 18, which since 18 = 9 + 9, the theorem says nothing about. The only known orders are primes and prime powers, although alternate constructions exist which give projective planes which are not isomorphic to those produced by the Latin square construction. Instant fame and recognition will be the reward of the mathematician who settles the question of the existence of projective planes of composite order.

There are several interesting research questions concerning nets. For instance, what conditions on a net are sufficient and necessary for the net to be extended to an affine plane? What conditions are needed so that a net which can be extended to an affine plane can be extended in only one way?

The following is a standard proof for this fact. I outline the logic with a series of questions.

If $A$ is a latin square, you get another one by the process of renaming the entries. In this way you can put $A$ into a kind of a standard form $A_$ that has $(1,2,ldots,n)$ as its first row.

$A=left(egin 2&1&33&2&11&3&2end ight),$ then we can put this into standard form by putting a '1' wherever there is a '2' and a '2' wherever there is a '1' and get $A_=left(egin 1&2&33&1&22&3&1end ight)$

Lemma: If $A$ and $B$ are orthogonal latin squares, then so are $A_$ and $B_$.

You prove this! It is not difficult. Let me illustrate with an example. The above LS $A$ is orthogonal to the Latin square $B=left(egin 2&3&13&1&21&2&3end ight),$ because the pairs of entries are (2,2),(1,3),(3,1) on the first row, (3,3),(2,1),(1,2) on the second and (1,1),(3,2),(2,3) on the last. The standard form of $B$ is (check this as a way of understanding what standard form means) $B_=left(egin 1&2&32&3&13&1&2end ight).$ As a check that you understand orthogonality I invite you to verify that $A_$ and $B_$ are, indeed, orthogonal.

So if $A^<(1)>, A^<(2)>,ldots A^<(k)>$ are mutually orthogonal latin squares, then by the lemma we can assume that they all are in the standard form. Therefore the first rows contain the pairs $(i,i),i=1,2,ldots,n$ for all the pairs of latin squares. Let us then look at the position of 2 on the first column of $A^<(1)>$. Let's say that this happens on row $j$, so $A^<(1)>_=2$.

Question #1: Why is it illegal to have $A^<(i)>_=2$ for any $i=2,3,ldots,k$?

Question #2: Why is it illegal to have $A^<(i)>_=1$ for any $i=2,3,ldots,k$?

Question #3: Why is it illegal to have $A^<(i)>_=A^<(ell)>_$ for any two indices $i$ and $ell$ such that $2le i<ellle k$?

Question #4: Why do the answers to the previous questions imply $k<n$?

Prove the lemma (unless it is done in the book) and answer the questions! Good luck!