= Solution
Generate a row while respecting the forbidden symbols in each column. Selection returns an element together with the still-available elements:
``
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)]
``
The <invariant> of `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.
Back to article page
