What is a Latin Squares?

A Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column.

Latin square example

Not a Latin square

Not a Latin square

Latin square example

Another Example

Latin Square applications

• Error correcting codes - Latin squares that are orthogonal to each other have found an application as error correcting codes in situations where communication is disturbed by various types of noise.

• Mathematical puzzles - Sudoku puzzles are a special case of Latin squares; any solution to a Sudoku puzzle is a Latin square.

How to generate Latin Squares arrays

• By hand, is very easy to find at least one Latin Square for any n.

• Algebraically with finite fields.

• Exhaustive computing

Simple algorithm to enumerate Latin Squares of lenght n.

• Write an algorithm to generate all the permutations for Latin Squares.
• Write an algorithm to determine if an arrays meets the Latin Square property.

Backtracking

Instead of using an algorithm to generate all the permutations. We will use backtracking to eliminate branches of computations and speed things a little bit more.

The backtracking algorithm work as follows:

1. Start with an array of length n with 1 in position 0
2. Add an number to the next position that is not in the same row and column
3. If the sub array meets the Latin Square property move forward using step 2.
4. Otherwise
   • If there is a number available to try in the same position try it and goto step 3
   • Otherwise move one position back.

Python implementation of the backtracking algorithm

ls_list = []

while current > start:
    #find next
    row_s = current/n
    latin_square[current] += 1
    while ls[current] in ls[row_s*n:current] and ls[current] < n:
        latin_square[current]+=1

    if ls[current] > n:
        #back track
        ls[current] = 0
        current-=1
    elif checkLatin(ls, current,n):
        if current < size-1:
            current+=1
        else:
            ls_list.append(ls[:])   

Python simple implementation of a function to check the Latin property

def checkLatin(ls, current, n):
        row = current/n
        column = current % n

        for i in range(row):
                if ls[i * n + column] == ls[current]:
                        return False

        return True

How to parallelize?

We can start by computing the set of all permutations of size for the first row of the LS

• Divide set in equal parts among the processes and have the complete the search.

• Have one process, the master, send one sub Latin Square to the other processes, the slaves. Once the slaves finish their computation, send back the results and wait for another sub Latin Square.

• For this application we will prefer to divide the set in equal parts, because each sub permutation will have the same solution spance.

A parallel approach: Divide the problem in n!/nprocs.

if rank == 0:
        perm_list = [perm for perm in itertools.permutations([i+1 for i in range(n)])]
else:
        perm_list = None

perm_list = comm.bcast(perm_list, root=0)
        
n1, n2 = computeIndices(len(perm_list), num_procs, rank)

# Compute LS sub problems
for i in range(n1, n2):
        latin_square = list(perm_list[i]) + [0] * (size - n)
        ls_list += completeLatinSquare(latin_square, current, start)

if rank == 0:
        for i in range(num_procs-1):
                ls = comm.recv(source=MPI.ANY_SOURCE, tag=MPI.ANY_TAG, status=stat)
                ls_list += ls
        
        # Save, display the results HERE
else:
        comm.send(ls_list, dest=0)  

Compute Indices Utility

def computeIndices(size, nprocs, rank):
        portion = size  / nprocs
        residue = size % nprocs
        
        if rank <= residue:
                n1 = rank * (portion+1)
        else:
                n1 = rank * portion + residue

        n2 = n1 + portion
        if rank < residue:
                n2 += 1

        return n1, n2

References

Wikipedia, http://en.wikipedia.org/wiki/Latin_square

MPI4py, http://mpi4py.scipy.org/

Python, www.python.org