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.