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.


string aleph = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
 
function rfls(integer n, bool count_only=true)
    if n>length(aleph) then ?9/0 end if -- too big...
    if n=1 then return iff(count_only?1:{{1}}) end if
    sequence tn = tagset(n),     -- {1..n}
             vcs = repeat(tn,n), -- valid for cols
             vrs = repeat(tn,n), -- valid for rows
             res = repeat(tn,n)  -- (main workspace/one element of result)
    object result = iff(count_only?0:{})
    vcs[1] = {}     -- (not strictly necessary)
    vrs[1] = {}     --          """
    for i=2 to n do
        res[i] = i & repeat(0,n-1)
        vrs[i][i] = 0
        vcs[i][i] = 0
    end for
    integer r = 2, c = 2
    while true do
        -- place with backtrack:
        -- if we successfully place [n,n] add to results and backtrack
        -- terminate when we fail to place or backtrack from [2,2]
        integer rrc = res[r,c]
        if rrc!=0 then  -- backtrack (/undo)
            if vrs[r][rrc]!=0 then ?9/0 end if  -- sanity check
            if vcs[c][rrc]!=0 then ?9/0 end if  --      ""
            res[r,c] = 0
            vrs[r][rrc] = rrc
            vcs[c][rrc] = rrc
        end if
        bool found = false
        for i=rrc+1 to n do
            if vrs[r][i] and vcs[c][i] then
                res[r,c] = i
                vrs[r][i] = 0
                vcs[c][i] = 0
                found = true
                exit
            end if
        end for
        if found then
            if r=n and c=n then
                if count_only then
                    result += 1 
                else
                    result = append(result,res)
                end if
                -- (here, backtracking == not advancing)
            elsif c=n then
                c = 2
                r += 1
            else
                c += 1  
            end if
        else
            -- backtrack
            if r=2 and c=2 then exit end if
            c -= 1
            if c=1 then
                r -= 1
                c = n
            end if
        end if
    end while
    return result
end function
 
procedure reduced_form_latin_squares(integer n)
    sequence res = rfls(n,false)
    for k=1 to length(res) do
        for i=1 to n do
            string line = ""
            for j=1 to n do
                line &= aleph[res[k][i][j]]
            end for
            res[k][i] = line
        end for
        res[k] = join(res[k],"\n")
    end for
    string r = join(res,"\n\n")
    printf(1,"There are %d reduced form latin squares of order %d:\n%s\n",{length(res),n,r})
end procedure

reduced_form_latin_squares(4)
puts(1,"\n")
for n=1 to 6 do
    integer size = rfls(n)
    atom f = factorial(n)*factorial(n-1)*size
    printf(1,"Order %d: Size %-4d x %d! x %d! => Total %d\n", {n, size, n, n-1, f})
end for
