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. |
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?
|
|
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.
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() | 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. |
Last Edit: Aug 12, 2011 at 14:18 (5,057.43 days ago) | Viewed 10 times per day |