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

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[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)
    
  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))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: