NOW SpinRite 6.1 – Fast and useful for spinning and solid state mass storage!

Latin Squares Workbench
Experiments in Latin Square manipulation for the “Off The Grid” project.
Latin Square:  An n x n square array filled with n different letters, numbers or
symbols, each occurring exactly once in each row and exactly once in each column.
What is this all about?
During the early development of the “Off The Grid” personal cipher system we needed to acquire a working understanding of the characteristics of Square Latin manipulation. It was known from the extensive literature about the characteristics and nature of Latin Squares that if was possible to “permute” any Latin Square in a number of ways which would not alter the Square's fundamental “Latinness”. For example, if you think about it for a second you'll see that the “only one of each type of symbol in any row and column property” of every Latin Square will be preserved if any row or column is exchanged with another. In fact, all of the following manipulations preserve any Square's “Latinness”:

Note that what's not here are other, presumed possible, LS configurations that might be unreachable through these transformations (this remains to be determined and is one of the goals of this work). Such “unreachable” Squares might be found, for example, by employing a brute force recursive backtrack searching to find all possible Squares.

(Note that a full recursive backtracking search is what I ultimately determined would be necessary — and is what I'm doing for the “Off The Grid” system — since the JavaScript device below allowed us to demonstrate and explore that it was not, in fact, possible to reach all possible Latin Squares through permutations of a base starting Square.)

This page was created to aid the empirical and experimental exploration of Latin Square generation. Its goal is to answer the question of how complex a “unique scrambling” we are able achieve, and which transformations are useful and which, if any, are not.

It's clear that there are n! ways of reordering the columns and n! ways of reordering the rows. However, quick experimentation with smaller Squares (such as a 3x3 which can be selected through the user-interface) quickly reveals that the combination of unique color patterns available though combining row and column reordering is not (n!•n!) but instead is (n!•(n-1)!).

There are also n! ways of swapping symbols (colors) among themselves.

Finally, if each cell in the array is represented as a tuple of the form (r,c,s) where 'r' is the cell's row, 'c' is the cell's column, and 's' is the symbol at the (r,c) location, then the entire Square's essential “Latinness” is preserved if any two elements of every tuple are exchanged. For example, if the 'c' and 's' elements were exchanged, the cell's symbol would specify the column and the cell's column would specify the symbol. In other words, the cell's column number would be stored into the column specified by that cell's symbol; e.g. if the cell in column 2 contained a 5, then a 2 would be stored into column 5. The workbench below supports and allows for experimentation with all of these transformations.

Collectively, this generates a potentially huge variety of different Latin Squares. Using just simple row, column and symbol exchanges, we can produce (n!•(n-1)!•n!) combinations. For a small order 6 (n=6) Latin Square, such as the experimental one below, that's 62,208,000 reordering arrangements.

But here's the BIG question: Are ALL of the Latin Squares resulting from combinatorial rearrangements distinct and unique? And how can we be sure we didn't miss any? For example, in preliminary experiments with the tuple exchanger transformations, alternating between the c↔s and r↔s exchanges cycled through many six intermediate Squares before returning to the starting configuration ~ but only in some starting grid configurations. Might it be that mixing in the otherwise simplistic c↔r exchange would extend this further?

So the question to be answered is: What algorithm can be designed using these transformations to yield the largest number of possible unique Latin Squares? And how large is that number relative to the total number of possible Latin Squares?





Non-Obvious Latin Square Workbench Concepts

The LS Workbench displays the colors of the grid squares, but it also tracks the individual identities of the squares as they move through the grid. In other words, in its default “Color” display mode, all of the Red grid squares show a '1' with the numbers being numeric representations of each color. But in the “Indent” display mode, you'll notice that each color is individually numbered within its color. This is useful for tracking instances where transformations do not result in color changes, but are nevertheless changing the identities of the grid's objects  . . . or where extensive transformations may return to a previously seen coloration, but with different instances of the same colors in each location.

The Workbench keeps track of every grid color and identity configuration it has seen, and it memorizes these individually. The “fraction like” numbers sticking out of the sides of the grid displays show the location of the current pattern in the history memory above the '/' and the total size of the history memory below the '/'. The upper pair of numbers reflects the status of the color-only memory and the lower pair shows the status of the color+identity memory. Finally, the number pairs are highlighted with red or green (respectively) whenever a new and unique pattern entry is made to the history memory

The equality of the snapshot scratchpads is continually shown with equals, not equals, and a green three-bar “equivalence” symbols. Not equals is shown whenever the displayed color patterns are not identical, equals is shown when the displayed colors are identical but the underlying identities of the colors are not. And the three-bar “equivalance” symbol is shown when both the colors and identities are identical. Consequently, for example, the three-bar equivalence symbol will be shown immediately after copying the main grid into one of the snapshots since they will be completely identical at that point.

The Workbench is 100% “touch friendly” and is delightful to work with on any touch-enabled device. But it is less easily manipulated with a mouse. Consequently, the Rows, Columns, and Colors can be selected with a keyboard by pressing the letters associated with the rows, columns, and colors.

Workbench User-Interface Guide
latin-squares-1 The “Reset” button restores the primary Latin Square to its “base” state where the first row is numbered 1, 2, 3, ... and each successive row is rotated one column to the right. This is guaranteed to produce a very simple Latin Square and is the starting state for all subsequent manipulations. latin-squares-6 If each cell of the grid is addressed as an (r,c,s) tuple, the “Latinness” of the Square is preserved when any pair of those tuple elements are exchanged. Exchanging the 'r' & 'c' elements swaps the row and column (which is what the row↔col button does). This button exchanges the columns and symbols.
latin-squares-2 The large alphabetic buttons can be clicked to select its respective row or column. The respective keyboard keys perform the same function. The contents of any pair of rows or columns can be exchanged by first selecting one, which will show it selected, then clicking the second, which will exchange the contents of the row or column. latin-squares-7 Similar to the button above, this performs the somewhat complex “Latinness” preserving operation of exchanging the symbol and row elements of the Latin Square's (r,c,s) tuples. Note that 'r' stands for row, 'c' for column, and 's' for the symbol located at the 'r' and 'c' intersection.
latin-squares-3The Latin Square grid is labelled with distinctive colors and numbers. As with row and column selection/swapping the keyboard may be used for quicker interaction. Any two sets of grid symbols may be exchanged by first selecting one, then the other. latin-squares-8The Latin Squares Workbench contains three “Snapshot” scratchpads. The horizontal left and right pointing arrows copy the current Latin Square grid configuration back and forth between its respective snapshot and the Latin Square.
latin-squares-4Latin Square complexity increases quickly as the size of the square increases, the workbench can be set to manipulate 3x3, 4x4, 5x5, and 6x6 size Latin Squares. latin-squares-9The up and down pointing arrows copy the snapshot scratchpads between themselves. This can be useful handy during complex hunts for intermediate Latin Square configurations.
latin-squares-11 This button toggles the workbench's display mode. When set to “Color”, the cell numbering corresponds to its color. When set to “Ident” the numbers track the cell's individual identity within its color group as it is moved around the Square. notequalsThe Equals, Not Equals and Equivalence (three green bars) symbols continuously reflect whether each of the snapshot scratchpads is identical to the main Latin Square. “Equivalence” means that not only are all of the colors identical, but the individual cells within a color are also identical.
latin-squares-5 Empties the Workbench's memory of all previous color and cell identity patterns. The current pattern becomes the first new pattern in the Workbench's pattern configuration history. latin-squares-5 The upper bold number of the n/m fraction is the associated grid pattern's location within in the Workbench's pattern memory and the lower non-bold number is the total number of pattern entries in the grid memory. The upper pair of numbers shows the color-pattern memory and the lower pair shows the more specific color+identity memory. The respective numbers are highlighted (in  red  for the upper pair and  green  for the lower pair) whenever a new grid pattern is being seen for the first time and a new entry is made into the pattern memory.
latin-squares-5 Flips (reflects) a Latin Square about its major diagonal axis (from upper left to lower right) preserves its “Latinness”. (Preliminary experimentation reveals that this reflecting does not help to create unique Latin Squares since the mirroring can be easily reversed through row and column exchanges.

Off The Grid Resource Pages:

Jump to top of page
Gibson Research Corporation is owned and operated by Steve Gibson.  The contents
of this page are Copyright (c) 2024 Gibson Research Corporation. SpinRite, ShieldsUP,
NanoProbe, and any other indicated trademarks are registered trademarks of Gibson
Research Corporation, Laguna Hills, CA, USA. GRC's web and customer privacy policy.
Jump to top of page

Last Edit: Aug 12, 2011 at 14:18 (4,698.07 days ago)Viewed 4 times per day