The empty family has one choice, the empty selection:A selection from the whole family consists uniquely of a choice from its first member and a selection from the remaining family. This bijection proves the combining equation and completeness by induction. If a member family is empty, there are no selections. The base is
cp :: [[a]] -> [[a]]
cp = foldr extend [[]]
where
extend choices suffixes = [x:ys | x <- choices, ys <- suffixes][[]], not []: otherwise every Cartesian product would incorrectly be empty.For a nonnegative order, first enumerate every possible row and then every possible ordered selection of rows:Every one of the positions chooses one of symbols independently. Consequently the enumeration contains candidate squares for , each exactly once. The conventional order-zero extension produces one empty square. This is generation only; repeated symbols have not yet been rejected.
squares :: Int -> [[[Int]]]
squares n
| n < 0 = error "negative order"
| otherwise = cp (replicate n (cp (replicate n [1..n])))The following predicate also checks the square's shape; The row tests guarantee that each row has length and contains each allowed symbol once. Because
sort is the three-way sorting function from Question 2:valid :: [[Int]] -> Bool
valid rows =
let n = length rows
symbols = [1..n]
goodRows = all (\r -> sort r == symbols) rows
goodColumns = all (\j -> sort [r !! j | r <- rows] == symbols)
[0..n-1]
in goodRows && goodColumns
latin :: Int -> [[[Int]]]
latin = filter valid . squares&& tests this condition first, the later column indexing is safe for a finite total input. The column tests establish the remaining Latin-square condition. Filtering therefore retains precisely the valid squares; it does not remove any different ordering of rows, columns or symbols as an alleged symmetry duplicate.The generation count, before any validity test, is . It is at order three, at order four, and approximately at order five. Even an illustrative rate of one million complete candidates per second would require about 72 minutes at order four and about 9,444 years at order five, before accounting for the actual validity-checking cost. Thus order four is already expensive and order five is plainly impractical for this strategy; the exact threshold depends on the implementation and hardware, not just the mathematical count.
Candidate growth before filtering in two Latin-square generation strategies
. Original exact candidate counts, plotted on a base-ten logarithmic vertical axis. These are mathematical counts, not measured running times; pruning can avoid many invalid partial extensions as well. Details.
Choose each row from the permutations of the symbols:Every Latin square remains a candidate, because each of its rows is one of those permutations. Conversely every candidate has valid rows, so only its columns still need checking. There are candidates instead of : at order four, rather than more than four billion. The improvement is substantial but does not make exhaustive generation practical at arbitrary orders. One can replace
squaresRows :: Int -> [[[Int]]]
squaresRows n
| n < 0 = error "negative order"
| otherwise = cp (replicate n (perms [1..n]))
latinRows :: Int -> [[[Int]]]
latinRows = filter valid . squaresRowsvalid by a column-only test here, since row validity is guaranteed by construction.Generate a row while respecting the forbidden symbols in each column. Selection returns an element together with the still-available elements:The invariant of
select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- select xs]
row :: [Int] -> [[Int]] -> [[Int]]
row [] [] = [[]]
row remaining (used:otherColumns) =
[x:rest | (x,available) <- select remaining,
x `notElem` used,
rest <- row available otherColumns]
row _ _ = []
latinPruned :: Int -> [[[Int]]]
latinPruned n
| n < 0 = error "negative order"
| otherwise = build n (replicate n [])
where
build 0 usedColumns = [[]]
build remainingRows usedColumns =
[r:rest | r <- row [1..n] usedColumns,
rest <- build (remainingRows-1)
(zipWith (:) r usedColumns)]row is that remaining contains exactly the unused symbols of this row, while each member of the column list records symbols used by earlier rows. Selecting removes a symbol, so it cannot repeat in the current row; the membership test prevents a column repetition. A complete row uses every symbol once. Updating the column histories preserves the invariant for the next recursive call.Every complete generated square is therefore valid without a final filter. Conversely, take any valid target square: its next row passes every selection and column test, so induction keeps a branch constructing that target. Distinct choices from the initially distinct symbols cannot generate the same square twice. Dead-end partial squares may still be explored; the method promises to avoid constructing complete invalid squares, not to foresee every future dead end. Independent enumeration gives 1, 2, 12 and 576 squares at orders one through four.
Articles by others on the same topic
There are currently no matching articles.