"""
Random latin square generator using the Method of Circuts.
Model implementation in Python using simple search for symbol conflicts.
Larry Trammell -- May 2020

This supports the document "Direct Construction of Random Latin 
Squares by the Method of Circuits" and is publicly distributed
under the Creative Commons CC-BY-4.0 license.
"""

# Define row-column dimensions of square to be constructed
Nrc = 10

# Python system imports
import random as rnpy            # core random number generator
import numpy as np               # compact numeric data types
from copy import deepcopy        # data replicator for initialization 

"""
Conflict resolution operations
"""

# Find a column term that conflicts with a newly inserted term.
# If found, return the row index for the conflicting symbol. If not
# found, return artificial flag value -1.
def findConflictInCol(A, iviol, jviol, sym1) :
    Nrc=len(A)
    irow = -1
    for itest in range(Nrc) :
        if itest == iviol :  continue
        if A[itest,jviol] == 0 :  continue
        if A[itest,jviol] == sym1 :
            irow = itest
            break
    return irow
    
# Find a row term that conflicts with a newly inserted term. 
# If found, return the column index for the conflicting symbol.
# if not, return the artificial flag value -1.
def findConflictInRow(A, iviol, jviol, sym2) :
    Nrc=len(A)
    jcol = -1
    for jtest in range(Nrc) :
        if jtest == jviol :  continue
        if A[iviol,jtest] == 0 :  continue
        if A[iviol,jtest] == sym2 :
            jcol = jtest
            break
    return jcol

"""
Main generator sequence
"""
        
print("Generating a Latin Square of size ", Nrc,"x",Nrc)

# Initialize an empty square
A = np.zeros((Nrc,Nrc), dtype=np.short)

# Initialize feasible symbols sets for rows and cols
row = [ ]
for j in range(Nrc) :
    row.append( np.short(j+1) )
rowavail = [ ]
for i in range(Nrc) :
    rowavail.append( set(row) )
colavail = deepcopy(rowavail)

# Assigning symbols to layout cells in row-column lexical order. 
for i in range(Nrc) :
    for j in range(Nrc):

        # Check for row-column feasible symbols at this new location
        avail = rowavail[i] & colavail[j]

        if len(avail) > 0 :
            # FEASIBLE. Assign a randomly-selected feasible symbol.
            sel=rnpy.sample(avail,1)
            symbol1 = sel[0]
            A[i,j] = symbol1
            rowavail[i].remove(symbol1)
            colavail[j].remove(symbol1)
        else :
            # CONFLICT. Insert a randomly-selected row-feasible SYMBOL1 
            sel=rnpy.sample(rowavail[i],1)
            symbol1 = sel[0]
            A[i,j] = symbol1
            rowavail[i].remove(symbol1)

            # Randomly select a column-feasible replacement SYMBOL2
            sel=rnpy.sample(colavail[j],1)
            symbol2 = sel[0]

            # Begin conflict resolution at the newly-assigned cell.          
            iviol = i
            jviol = j
            while(True) :

                # Locate row of the violating symbol in column jviol
                iviol = findConflictInCol(A, iviol, jviol, symbol1)            
                if  iviol == -1 :
                    # If no conflict, resolution is complete
                    break

                # Remove SYMBOL1 from this circuit location
                rowavail[iviol].add(symbol1)

                # Replace with SYMBOL2
                A[iviol,jviol] = symbol2
                colavail[jviol].remove(symbol2)
                if symbol2 in rowavail[iviol] :
                    rowavail[iviol].remove(symbol2)

                # Locate column of the violating symbol in row iviol
                jviol = findConflictInRow(A, iviol, jviol, symbol2)            
                if  jviol == -1 :
                    # If no conflict, resolution is complete
                    break

                # Remove SYMBOL2 from this circuit location
                colavail[jviol].add(symbol2)

                # Replace with SYMBOL1
                A[iviol,jviol] = symbol1
                rowavail[iviol].remove(symbol1)
                if symbol1 in colavail[jviol] :
                    colavail[jviol].remove(symbol1)
            pass
        pass
    pass
        
print("\nCompleted square ")
print(A)

#print("\nVerify row and column sums")
#rowsum = [0]*Nrc
#colsum = [0]*Nrc
#for i in range(Nrc) :
#    for j in range(Nrc) :
#        rowsum[i] = rowsum[i]+A[i,j]
#        colsum[j] = colsum[j]+A[i,j]
#print("rowsum :", rowsum)
#print("colsum :", colsum)