""" This module provides an implementation of the Method of Covers algorithm for pseudo-randomly constructing Latin Squares. This code is provided June 4, 2026 by its author Larry Trammell under the CC-BY license; generally, that means you can do pretty much anything you want with this as long as you cite credit when appropriate, and don't try to claim total ownership for yourself. See the application example at the end of this file. For license details see: https://creativecommons.org/licenses/by/4.0/ ----------- A utility class to provide data structures used by the Method of Covers as it randomly generates Latin Squares. An "availability list" maintains an unordered list of items that are "taken" and a list of items that are "occupied." Since every item is either taken or not, the two lists are packed unordered into a single fixed-length array that is partitioned into two sections. The "availability list" facilitates operations like "test all unoccupied cells in the row." A "cross-indexing list" reports the postion in the list where a specified item is stored. This facilitates operations like "find the location in the column where the symbol 2 is stored." """ # Use the numpy library to define "short integer" data type. import numpy as np # numeric data types # Copy utility from copy import deepcopy # Random variate generation from numpy.random import Generator, PCG64 #from numpy.random import Generator, MT19937 rg = Generator( PCG64() ) # A utility function to select a discrete number 0 <= val < lim, uniformly # and randomly. # def randix( lim ) : val = rg.choice(lim, shuffle=False) return val # ======================================================================== # # The "split list" utility class # # ======================================================================== class splitlist : 'A class that maintains cross-reference and selection information' # The constructor method reserves storage and size information. # def __init__(self, Nrc) : # Administrative parameters and special flags self.len = Nrc # size of storage lists self.short0 = np.short(0) # count initializer self.empty = np.short(-1) # flag to indicate "unused location" # Number of assigned cells in each xtaken list self.Ntaken = np.ndarray((Nrc), dtype=np.short) # Availability list self.xavail = np.ndarray((Nrc,Nrc), dtype=np.short) # Selection cross reference list self.xsort = np.ndarray((Nrc,Nrc), dtype=np.short) # Content cross reference list self.xref = np.ndarray((Nrc,Nrc), dtype=np.short) self.clear() # An initializer. It sets all cross-reference entries to "empty," all # "taken" counts to 0. # def clear(self) : # No symbols have been taken; that means all locations are available self.Ntaken.fill(self.short0) # All items are initially present in the "available" section for sublist in range(self.len) : for ix in range(self.len) : self.xavail[sublist,ix] = ix # No locations are swapped in selection cross reference self.xsort = deepcopy(self.xavail) # No contents are noted by content cross references self.xref.fill(self.empty) # Swap the contents of two locations in the availability array. # This is typically used internally to shift an item between the # "available" and "taken" sections of the availability list. # Content cross-references are not changed. # def swap ( self, sublist, item1, item2 ) : # Extract the elements currently stored at the given locations elem1 = self.xavail[sublist,item1] elem2 = self.xavail[sublist,item2] # Swap these items in availability storage self.xavail[sublist,item1] = elem2 self.xavail[sublist,item2] = elem1 # Swap these items in the selection cross reference self.xsort[sublist,elem2] = item1 self.xsort[sublist,elem1] = item2 # Move an item from the "available" section to the "taken" section # of the selection array. Update the cross references. # def assign ( self, sublist, item, value ) : # Cross reference the content of the new item self.xref[sublist,value] = item # Locate the split between "taken" and "available" items lastix = self.Ntaken[sublist] # Determine location of the element in availability list ix = self.xsort[sublist,item] # Swap locations if necessary to move item into taken section if ix != lastix : self.swap( sublist, lastix, ix ) # Relocate the partition between taken and available self.Ntaken[sublist] = lastix+1 # Release an item from the "taken" section back into the # "available" section. Update cross references. # def release ( self, sublist, item, value ) : # Remove the cross reference to the content value self.xref[sublist,value] = self.empty # Locate end of the "taken" items section of the sorting array lastix = self.Ntaken[sublist] - 1 # Locate the item to be released within availability list ix = self.xsort[sublist,item] # If the two locations are not the same, swap them if ix != lastix : self.swap( sublist, lastix, ix ) # Relocate the partition between taken and available self.Ntaken[sublist] = lastix # Use the content cross reference to test whether specified content # is already present in the "taken" section of the availability list. # Reports location index if the value is present, or "empty" otherwise. # def val_location ( self, sublist, value ) : # Test whether value is listed in the content cross-ref indx = self.xref[sublist, value] return indx # Randomly select an item from the available item section, without # changing status. If optional argument 'lim' is specified, limit # the search to this number of available cells; otherwise, any available # cell is eligible for selection. If no such cell is available, # return an "empty" flag; otherwise, return the contents of the # selected cell. A side effect is a partial shuffling of locations # within the sorted lists. # def select_avail ( self, sublist, lim=None ) : # If no range limit is specified, allow any available location av = self.len - self.Ntaken[sublist] if lim != None : if lim <= av : av = lim # Range of locations eligible for selection avstart = self.Ntaken[sublist] avlast = avstart + av - 1 # Special cases when no random sampling is required to extract item if av == 0 : return None if av == 1 : item = self.xavail[sublist,avstart] return item # Pick any eligible list location at random slot = randix(av)+avstart # Swap this item to the last selectable location so that it is # possible to skip it during follow-up searches. if slot != avlast : self.swap( sublist, slot, avlast ) item = self.xavail[sublist,avlast] return item # Randomly select an item from the "taken" item section, without # changing status. If optional argument 'lim' is specified, limit # the search to this number of occupied cells; otherwise, any # occupied cell is eligible for selection. If no occupied cell is # present, return an "empty" flag; otherwise, return the contents of # the selected cell. A side effect is a partial shuffling of locations # within the ordered cell lists. # def select_taken ( self, sublist, lim=None ) : # If no range limit is specified, allow any occupied location av = self.Ntaken[sublist] if lim != None : if lim < av : av = lim # Range of locations eligible to search avstart = 0 avlast = av - 1 # Special cases when no random sampling is required to extract item if av == 0 : return None if av == 1 : item = self.xavail[sublist,0] return item # Pick any eligible list item at random slot = randix(av) if slot != avlast : self.swap( sublist, slot, avlast ) item = self.xavail[sublist,avlast] return item # End of rlat_splitlist class definition # ======================================================================== # # The Method of Covers # # ======================================================================== # The Latin Square class, including the methods to populate it. # class rlatin : 'Defines a class that constructs a pseudo-random Latin square' # The constructor method reserves storage and size information. def __init__(self, Nrc, comp=2) : # Configuration parameters self.Nrc = Nrc if comp >= 0 : self.comp = comp # "Flag" constant for identifying incomplete content self.empty = np.short(-1) # Storage for the constructed Latin Square self.store = np.ndarray((Nrc,Nrc), dtype=np.short) # A cross-reference structure for assignments into rows self.rowxref = splitlist( Nrc ) # A cross-reference structure for assignments into columns self.colxref = splitlist( Nrc ) # Initialize storage optional # self.clear( ) # Set all internal storage values to the initial state. # def clear( self ) : self.store.fill( self.empty ) self.rowxref.clear() self.colxref.clear() # Attempt to randomly select an empty cell in the specified row such # that there is no conflict with symbol 'sym' in that column. If # found, return the column index of the available cell. Otherwise, # return an "empty" result. # def select_feasible_cell( self, row, sym ) : # How many empty cells are there in the row? lim = self.Nrc - self.rowxref.Ntaken[row] # Randomly check the open cells listed for this row while lim > 0 : col = self.rowxref.select_avail( row, lim ) # Is there no conflict in this column? test = self.colxref.xref[col,sym] if test == self.empty : return col lim -= 1 # Conflict... try another column # We failed to find a suitable cell. Report the failure. return self.empty # Resolve the symbol assignment conflict that is discovered in the # row when trying to find a location where 'sym' can be stored. # One of the three heuristics will succeed. There is no return value. # def Resolve( self, row, sym ) : # Apply the split-symbol heuristic col = self.Resolve_by_split( row, sym ) if col != self.empty : return # Apply the general cycle-tracing heuristic. # This always works, but has a potential to cause bias. self.Resolve_by_tracing( row, sym ) # Apply the split-symbol resolution strategy to the current row. # This heuristic attempts to move the 'current symbol C' out of a # column where it blocks assignments in the current row, into # a different column position where there is no conflict. Thus # the pattern - C becomes C - # D - D - # and a copy of current symbol C can now be placed diagonally to # the other without conflict to form the pattern # C - # D C # If this succeeds, return the index of the column where the # symbol assignment was successful. Otherwise, report an 'empty' # flag to indicate failure. # def Resolve_by_split( self, row, sym ) : # All empty cells in row are initiallly eligible for testing lim = self.Nrc - self.rowxref.Ntaken[row] # Test row locations where the cell is empty while lim > 0 : col = self.rowxref.select_avail( row, lim ) # See whether this column already has the current symbol present rowx = self.colxref.xref[col,sym] if rowx == self.empty : # Not present, try another column. lim = lim-1 continue # We found the current symbol in the column. Test the empty # cells in that row for feasibility. limx = self.Nrc - self.rowxref.Ntaken[rowx] while limx > 0 : colx = self.rowxref.select_avail( rowx, limx ) if self.colxref.val_location( colx, sym ) == self.empty : # No conflict at this location. Perform the split operation. self.rowxref.release( rowx, col, sym ) self.colxref.release( col, rowx, sym ) self.store[rowx,col] = self.empty self.rowxref.assign( row, col, sym ) self.colxref.assign( col, row, sym ) self.store[row,col] = sym self.rowxref.assign( rowx, colx, sym ) self.colxref.assign( colx, rowx, sym ) self.store[rowx,colx] = sym # Indicate success return col # No, column already has the symbol. Try another. limx = limx-1 # We couldn't apply the split heuristic here. Try another # empty slot from the current row. lim = lim-1 # If we fall through both loops, report failure. return self.empty # Resolve the conflict in the current row using the general tracing # method. This always works, but also causes the most bias damage. # def Resolve_by_tracing( self, row, sym ) : # This is a dummy placeholder symbol dummy = self.Nrc-1 col = self.rowxref.select_avail( row ) # Loop invariant: # row,col point to an empty cell where conflict might exist. while( True ) : # Check whether sym is already present somewhere in column rowx = self.colxref.xref[col,sym] # Check whether resolution has been reached if rowx == self.empty : # Resolved... Assign symbol and finish. self.rowxref.assign( row, col, sym ) self.colxref.assign( col, row, sym ) self.store[ row,col ] = sym break # Conflict is present in column. Remove conflicting symbol. # Replace it with temporary dummy. self.rowxref.release( rowx, col, sym ) self.colxref.release( col, rowx, sym ) self.store[ rowx,col ] = self.empty # Temporily block backtracking by replacing with dummy symbol self.rowxref.assign( rowx, col, dummy ) self.colxref.assign( col, rowx, dummy ) self.store[ rowx,col ] = dummy # Store the current symbol at the previous trace location self.rowxref.assign( row, col, sym ) self.colxref.assign( col, row, sym ) self.store[ row,col ] = sym # Select an empty row cell at random in conflict row colx = self.rowxref.select_avail( rowx ) # Remove the temporary dummy symbol self.rowxref.release( rowx, col, dummy ) self.colxref.release( col, rowx, dummy ) self.store[ rowx,col ] = self.empty # Advance to the next trace location row = rowx col = colx # We must depend on the algorithm correctness to guarantee # that this loop terminates. # Having just completed a cover for symbol sym1, pick a second # symbol sym2 randomly, and use the symbol pair to define a # circuit within the Latin Square layout. Trace this circuit, # And after visiting each cell, toggle the symbol content from # sym1 to sym2 or from sym2 to sym1. # def Toggle( self, sym1 ) : # Pick a second symbol from those used for previous covers if sym1 == 0 : return if sym1 == 1 : sym2 = 0 else : sym2 = randix( sym1 ) # Pick any start row randomly rowst = randix( self.Nrc ) # Find start column where sym1 is present in this row colst = self.rowxref.xref[rowst,sym1] # Current position is the start cell location row = rowst col = colst # Clear the start cell self.rowxref.release( row, col, sym1 ) self.colxref.release( col, row, sym1 ) self.store[ row,col ] = self.empty # Find sym2 within the current column rowx = self.colxref.xref[col,sym2] # Clear sym2 from the new cell self.rowxref.release( rowx, col, sym2 ) self.colxref.release( col, rowx, sym2 ) self.store[ rowx,col ] = self.empty row = rowx # Trace along circuit partition using selected symbols while( True ) : # Find sym1 within the current row colx = self.rowxref.xref[row,sym1] # Clear sym1 from the new cell self.rowxref.release( row, colx, sym1 ) self.colxref.release( colx, row, sym1 ) self.store[ row,colx ] = self.empty # Store sym1 back in the previous cell self.rowxref.assign( row, col, sym1 ) self.colxref.assign( col, row, sym1 ) self.store[ row,col ] = sym1 # Advance to the column to the newest cell col = colx # Find the next sym2 in the new column. rowx = self.colxref.xref[col,sym2] # Clear sym1 from the new cell self.rowxref.release( rowx, col, sym2 ) self.colxref.release( col, rowx, sym2 ) self.store[ rowx,col ] = self.empty # Toggle the contents of the previous cell. self.rowxref.assign( row, col, sym2 ) self.colxref.assign( col, row, sym2 ) self.store[ row,col ] = sym2 # Have we reached the start row? if rowx == rowst : # Replace contents of the final cells self.rowxref.assign( rowst, col, sym1 ) self.colxref.assign( col, rowx, sym1 ) self.store[ rowx,col ] = sym1 self.rowxref.assign( rowst, colst, sym2 ) self.colxref.assign( colst, rowst, sym2 ) self.store[ rowst,colst ] = sym2 return # Advance to the newest cell location. row = rowx # The trace always terminates when it reaches the initial # cell again. pass # Populate the contents of the Latin Square reserved storage with new # randomly-selected Latin Square contents. Do this by constructing # covers for unassigned storage cells, one cover at a time, each # cover determining one symbol assignment for every row. # def fill( self ): # Initialize all storage elements self.clear( ) # Build a cover for each symbol value for sym in range(self.Nrc) : # Find a symbol assignment location for each row for row in range(self.Nrc) : col = self.select_feasible_cell( row, sym ) if col != self.empty : # Store the symbol and cross reference position self.store[row,col] = sym self.rowxref.assign( row, col, sym ) self.colxref.assign( col, row, sym ) else : # Use conflict resolution to assign the symbol self.Resolve( row, sym ) pass # Perform a scrambling trace to counter bias for reps in range(self.comp) : self.Toggle( sym ) # End of rlsmoc.py class definition """ Test program, using default for bias compensation Copy to a separate python file, remove comment marks, and run it. """ #import rlsmoc as rls #Nsize = 7 #rl = rls.rlatin(Nsize) #rl.fill() #print(rl.store)