## 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.

Advertisements

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”.