A Latin Square is in its reduced form if the first row and first column contain items in their natural order. The order n is the number of items. For any given n there is a set of reduced Latin Squares whose size increases rapidly with n. g is a number which identifies a unique element within the set of reduced Latin Squares of order n. The objective of this task is to construct the set of all Latin Squares of a given order and to provide a means which given suitable values for g any element within the set may be obtained.

For a reduced Latin Square the first row is always 1 to n. The second row is all Permutations/Derangements of 1 to n starting with 2. The third row is all Permutations/Derangements of 1 to n starting with 3 which do not clash (do not have the same item in any column) with row 2. The fourth row is all Permutations/Derangements of 1 to n starting with 4 which do not clash with rows 2 or 3. Likewise continuing to the nth row.

Demonstrate by:

 displaying the four reduced Latin Squares of order 4.
 for n = 1 to 6 (or more) produce the set of reduced Latin Squares; produce a table which shows the size of the set of reduced Latin Squares and compares this value times n! times (n-1)! with the values in OEIS A002860.


using Combinatorics
 
clash(row2, row1::Vector{Int}) = any(i -> row1[i] == row2[i], 1:length(row2))
 
clash(row, rows::Vector{Vector{Int}}) = any(r -> clash(row, r), rows)
 
permute_onefixed(i, n) = map(vec -> vcat(i, vec), permutations(filter(x -> x != i, 1:n)))
 
filter_permuted(rows, i, n) = filter(v -> !clash(v, rows), permute_onefixed(i, n))
 
function makereducedlatinsquares(n)
    matarray = [reshape(collect(1:n), 1, n)]
    for i in 2:n
        newmatarray = Vector{Matrix{Int}}()
        for mat in matarray
            r = size(mat)[1] + 1
            newrows = filter_permuted(collect(row[:] for row in eachrow(mat)), r, n)
            newmat = zeros(Int, r, n)
            newmat[1:r-1, :] .= mat
            append!(newmatarray, 
                [deepcopy(begin newmat[i, :] .= row; newmat end) for row in newrows])
        end
        matarray = newmatarray
    end
    matarray, length(matarray)
end
 
function testlatinsquares()
    squares, count = makereducedlatinsquares(4)
    println("The four reduced latin squares of order 4 are:")
    for sq in squares, (i, row) in enumerate(eachrow(sq)), j in 1:4
        print(row[j], j == 4 ? (i == 4 ? "\n\n" : "\n") : " ")
    end
    for i in 1:6
        squares, count = makereducedlatinsquares(i)
        println("Order $i: Size ", rpad(count, 5), "* $(i)! * $(i - 1)! = ", 
            count * factorial(i) * factorial(i - 1)) 
    end
end
 
testlatinsquares()
 