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.
Programming Praxis 
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.
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[0]] 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)@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.
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]])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?