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

Pages: 1 2

### 11 Responses to “Latin Squares”

1. Zack said

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

``````for i = 2:n
done = false

while !done
x = randperm(n) .- 1
done = true

for j = 1:n
if x[j] in A[1:(i-1),j]; done = false; break; end
end
end

A[i,:] = x
end

return A
``````

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

``````for i = 2:n
for j = 1:n
A[i,j] = mod(A[i-1,j] + 1, n)
end
end

return A
``````

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

2. Paul said

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

```import random
from pprint import pprint

def create_latin(dim):
frow = list(range(dim))
random.shuffle(frow)
labels = [frow]
for _ in range(dim-1):
frow = frow[1:] + [frow]
labels.append(frow)
random.shuffle(labels)
random.shuffle(list(zip(*labels)))
return labels

def assert_latin(arr2d):
n = len(arr2d)
sorted_nums = list(range(n))
for row in arr2d:
assert sorted(row) == sorted_nums
for col in zip(*arr2d):
assert sorted(col) == sorted_nums

latin = create_latin(5)
assert_latin(latin)
pprint(latin)
```
3. Zack said

@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

4. Paul said

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

5. Paul said

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

6. Zack said

@Paul. Many thanks!

7. Alex B. said

@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:

```labels = list(zip(*labels))
random.shuffle(labels)
```

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)

8. Paul said

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

9. Daniel said

Here’s a numpy-based solution in Python.

```import numpy as np

def latin_square(n):
arange = np.arange(n)
x = np.stack(tuple(np.roll(arange, x) for x in range(n)))
x[:, arange] = x[:, np.random.permutation(arange)]
x[arange, :] = x[np.random.permutation(arange), :]
return x

print(latin_square(5))
```

Output:

```array([[3, 1, 0, 2, 4],
[1, 4, 3, 0, 2],
[0, 3, 2, 4, 1],
[4, 2, 1, 3, 0],
[2, 0, 4, 1, 3]])
```
10. Daniel said

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

```x = np.stack(np.roll(arange, x) for x in range(n))
```
11. Stephane said

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?