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

### 10 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))
```