## Latin Squares

### June 18, 2019

A latin square of order *n* is a square matrix with *n* rows and *n* columns, with each entry in the matrix containing an integer from 0 to *n* − 1, arranged so that no row or column contains duplicate integers. Here is a sample latin square of order 10:

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

Your task is to write a program that generates latin squares of order *n*. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Interesting problem. Here is my take on it, using Julia 1.0:

using Random

function main(n::Int64)

A = Array{Int64}(undef, n, n)

x = Array{Int64}(undef, n)

A[1,:] = randperm(n) .- 1

end

Now, if we don’t really care about having each row of the LS as a random sequence of numbers and we just care about it being distinct from the previous rows, we can use a fairly simpler function:

function main2(n::Int64)

A = Array{Int64}(undef, n, n)

A[1,:] = randperm(n) .- 1

end

Either way, we can obtain a latin square, A, which can be quite handy as an auxiliary tool for building games like Sudoku. Cheers

In Python. I used Latin squares before in statistics for faster convergence in multidimensional random sampling.

@Paul. That’s intriguing. Could you please elaborate on this? Are you optimizing for a particular metric / heuristic in this kind of sampling? If so, what? I’m asking because I’ve played around with multi-dimensional sampling too over the years. Cheers

@Zack. I will dig in my old files and see if I have a nice example. In the meantime you can read the Wikipedia page on “Latin hypercube sampling”.

@Zack. I put an example on ideone. To run it you should have numpy, scipy, pyDOE and matplotlib installed.

@Paul. Many thanks!

@paul. I think you may have a bug in the randomisation. If I understand correctly you’re doing a transpose and randomise on the shuffled list, so that each row (although appearing in random order) is not a simple rotation of the first row.

In that case, you need to do something like:

Otherwise random.shuffle is shuffling an unreferenced list (returned by the list() call), and not labels, which you’re then returning.

(My apologies if I’ve misunderstood)

@Alex B: I understand your concerns. I had them too. However, after checking if the result is a latin square I thought I did it right. But you are right the last shuffle doesn’t work and your suggestion works fine. Thanks.

Here’s a numpy-based solution in Python.

Output:

Line 5 in my preceding solution can be simplified by removing the call to “tuple”.

All the solutions presented here are valid but are not truly “random”. Just swapping rows and columns keeps some symmetry: for example, from the big Latin Square at the top of the page, pick up two consecutive numbers from the first rows, for example, 23 and 21 of the second row. Just below these numbers are 8 and 3. Now, on any row, find 23 and 21 (which most probably won’t be consecutive) and from each number, in its column, find 8 (for 23) and 3 (for 21), you will see that they are on the same row! So, is it possible to build a Latin Square without this property and how would you do it?