Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique

Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Section 3.3 of [Generalised 2-designs with Block Size 3(Andy L. Drizen)] describes a method of generating Latin Squares of order n attributed to Jacobson and Matthews. The purpose of this task is to produce a function which given a valid Latin Square transforms it to another using this method.

part 1

Use one of the 4 Latin Squares in reduced form of order 4 as X0 to generate 10000 Latin Squares using X(n-1) to generate X(n). Convert the resulting Latin Squares to their reduced form, display them and the number of times each is produced.

part 2

As above for order 5, but do not display the squares. Generate the 56 Latin Squares in reduced form of order 5, confirm that all 56 are produced by the Jacobson and Matthews technique and display the number of each produced.

part 3

Generate 750 Latin Squares of order 42 and display the 750th.

part 4

Generate 1000 Latin Squares of order 256. Don't display anything but confirm the approximate time taken and anything else you may find interesting

F#

The Functions

<lang fsharp> // Jacobson and Matthews technique for generating Latin Squares. Nigel Galloway: August 5th., 2019 let R=let N=System.Random() in (fun n->N.Next(n)) let jmLS α X0=

 let X0=Array2D.copy X0
 let N=let N=[|[0..α-1];[α-1..(-1)..0]|] in (fun()->N.[R 2])
 let rec randLS i j z i' j' z'=
   X0.[i,j']<-z'; X0.[i',j]<-z'
   match X0.[i',j']=z' with
    true->X0.[i',j']<-z; X0
   |false->randLS i' j' z' (List.find(fun n->X0.[n,j']=z')(N())) (List.find(fun n->X0.[i',n]=z')(N())) (if (R 2)=0 then let t=X0.[i',j'] in X0.[i',j']<-z; t else z)
 let i,j=R α,R α
 let z  =let z=1+(R (α-1)) in if z<X0.[i,j] then z else 1+(z+1)%α
 let i',j',z'=let N=[0..α-1] in (List.find(fun n->X0.[n,j]=z) N,List.find(fun n->X0.[i,n]=z) N,X0.[i,j])
 X0.[i,j]<-z; randLS i j z i' j' z'

let asNormLS α=

 let n=Array.init (Array2D.length1 α) (fun n->(α.[n,0]-1,n))|>Map.ofArray
 let g=Array.init (Array2D.length1 α) (fun g->(α.[n.[0],g]-1,g))|>Map.ofArray
 Array2D.init (Array2D.length1 α) (Array2D.length1 α) (fun i j->α.[n.[i],g.[j]])

let randLS α=Seq.unfold(fun g->Some(g,jmLS α g))(Array2D.init α α (fun n g->1+(n+g)%α)) </lang>

The Task

part 1

<lang fsharp> randLS 4 |> Seq.take 10000 |> Seq.map asNormLS |> Seq.countBy id |> Seq.iter(fun n->printf "%A was produced %d times\n\n" (fst n)(snd n)) </lang>

Output:

[[1; 2; 3; 4]
 [2; 3; 4; 1]
 [3; 4; 1; 2]
 [4; 1; 2; 3]] was produced 2920 times

[[1; 2; 3; 4]
 [2; 4; 1; 3]
 [3; 1; 4; 2]
 [4; 3; 2; 1]] was produced 2262 times

[[1; 2; 3; 4]
 [2; 1; 4; 3]
 [3; 4; 2; 1]
 [4; 3; 1; 2]] was produced 2236 times

[[1; 2; 3; 4]
 [2; 1; 4; 3]
 [3; 4; 1; 2]
 [4; 3; 2; 1]] was produced 2582 times

part 2

<lang fsharp> randLS 4 |> Seq.take 10000 |> Seq.map asNormLS |> Seq.countBy id |> Seq.iteri(fun n g->printf "%d(%d) " (n+1) (snd g)); printfn "" </lang>

Output:

1(176) 2(171) 3(174) 4(165) 5(168) 6(182) 7(138) 8(205) 9(165) 10(174) 11(157) 12(187) 13(181) 14(211) 15(184) 16(190) 17(190) 18(192) 19(146) 20(200) 21(162) 22(153) 23(193) 24(156) 25(148) 26(188) 27(186) 28(198) 29(178) 30(217) 31(185) 32(172) 33(223) 34(147) 35(203) 36(167) 37(188) 38(152) 39(165) 40(187) 41(160) 42(199) 43(140) 44(202) 45(186) 46(182) 47(175) 48(161) 49(179) 50(175) 51(201) 52(195) 53(205) 54(183) 55(155) 56(178)

part 3

<lang fsharp> let q=Seq.item 749 (randLS 42) for n in [0..41] do (for g in [0..41] do printf "%3d" q.[n,g]); printfn "" </lang>

Output:

 16  7 41 15 17 40 12  9 10  5 19 29 21 18  8 22  3 36 23 31 11 38 13 30  2 33  6 42 39 14 32 20 28 35 26  1 34 37 27 24  4 25
 38 25 36 32 40 29 35 27  8 26 31 15  9  7 16 11  4  3 12 20 23 33  5 24 41 14 30 34 42 17 39 18 37 22 21 13  1 10  6 19  2 28
  8 34 27 25 21 31  1 23 37 36 26 13 22 24 35 17 10 40 41 30 42  7 15  2 18  3 29 11 32  4 38 39  9  5 16 14 28 12 20 33 19  6
 33 35 13 34 15 24  4 29 41 27  3 17 10 26 39 23 30 32  1 38 16 25 37 14  6 28 19  9 40  5 18  7 42 11 31 20 12 22  2 21  8 36
  2 42 20  1  7 26 11 10 39 41 34 22 40 23 24 29 14 17  5 33 38 30  6 13  3 16 18 19 31 15 28 21 36 37 32 27  8  4 25  9 35 12
 25 33 14 40 28 30 31 24 29  4  8 20 26 38 12 35  2 39 16  6 13 21 18 17  5 41 23  3 36  7 34 22 27  1 10 42 11 19 15 32 37  9
 17 22 35 28 30 18 21  2 15 39  5 40 27 13  1 34 38 37 26 23 41 36  4  3 11  6 20  8  9 10 12 24 31 25  7 29 16 32 42 14 33 19
 14  9 19  7 26 15 10  4 36 25 22 23 39 16  2 40 18  1 38 13 21 37 34 31 35 24 12 27 11  3  5  6 17 20 41 33 32 29  8 30 28 42
  5 27 24 13  2 36 25 30 23  9  6 14 35 15 42 39 16 26 21 34 33 31  3  1 29 12 38 17 37 19 40  4  7  8 22 41 20 28 32 10 18 11
 19 41 28 26  8 10 30 35 18 33 15 27 25 21 29 42 23 12 17  2  5  1 38  6 20  7 34  4 13 36 24 31 14  3 11 32 39 40  9 22 16 37
 41 10  3 19 22  9 27 40  1 29 16 42 33 39 34  7 37 20 11 12  4 18 35  8 28 26 36  5 17 30 25 32  6 15 24 21 13 23 14  2 38 31
 42  3 16 36 33 21 20 14 31 22  9 38 29 19 37 13 28 10 35 18 39 26 25 27  4 30 15 23 41 24 11  1 40  7  5 17  6  2 12  8 34 32
 23 31 34 41 38 33  3 28  4  1 30 25  6  2 20 14 13 24  8 42  7 12 39 32 22 29  5 37 15  9 27 10 35 36 19 40 17 18 16 11 26 21
 37 16 30 11  4 32 42 33 13  6 14  2 15 27 18 31 20 41 39 40  9 24 36  5 10  8  1 26  3 34 22 28 38 19 29 23 21 25 35 12 17  7
  1 19 26 22 16 25 36 39  3 23 41 37 34  6 17 32 40 21 10 27 12  9 31  7 13  4 24 29  8 11  2  5 15 18 35 28 30 20 33 38 42 14
 11 13 23 30 25 41  6 31 14 32 27 36 19 17 10 33 21 15  7  5  8 28 16 35 34 42 40  2 38 39  9 26 20 24 37  4 18  3 22  1 12 29
 24 17 29 38 23 39 32  5 11 15 35 12  8 10 40  1 22 25  2 36 28  4 42 21  9 20  3 31 16 41 13 30 19 34 33 18 27  6  7 37 14 26
 36  4  6 24 12 20  2 34 40 11 32  9 28  8 38 21  5 31 42 17 14 29 19 22 25 15  7 18 30 26  1 13 16 41 23 39 37 33  3 35 10 27
 20 39  2 12 32  7 22  3 17 10 37  6 18 40 27  5 42 35 28  4 24 14 33 29 30 31 26 13 19 23 36 41  1 21  9 11 15  8 34 16 25 38
 35 18 37  6  5 13 29  8 24 19 38 34 12 31 21 10 33  7  3 41 15 42 20 11 27 40 16 14 23  1  4  2 22 32 28  9 25 30 26 39 36 17
 10 32  9 33 39 19 41 38 35 18 28 26 14 30  7  4  1 22 37 21 31 40 27 15 42 34  2 25  5 12 23 36  8  6 17  3 29 24 11 13 20 16
 13 28 39  2 31  8  9 37 21 16 40 19 42 36 41  3 12 14 20 10 17 34  1 33 32 35 25 30 18 38 15 11 24 23  6 26  4  5 29  7 27 22
  7 40 12 39 18  3 16 21 42 17  1 32  5 33 13  6 41  8 29 14 34 35 24 36 38 25 31 28 26 27 20 37 23  2 30 10 22  9 19  4 11 15
  4 21  7 17 35 34 19 25 12 42 11  1 30 28 36 26 32 23 14 29  2 20  8 41 24 27 22 15 10 18 37  9 39 38 13  6  3 16 31 40  5 33
 34 23 42 14 41 27 37  6  9 31  4  5  7  1 25 16 35 30 33 11 19  3 26 12 17 38  8 20 24 13 29 15 32 28 40 22  2 39 18 36 21 10
 30  6 21  9 20 17  5 32 38 13 12 28 16 35 22 36 34 29 40 39 25 15 14 37 33 11  4 41  1  2 19  3 26 27 42  8 10  7 23 31 24 18
  6 38  8 10 42 35 13  1 16 37 21  3 11 34 32 20 29 18 25 22 36  5 30 26 39 23 28 12  2 31  7 19 33 40 14 24  9 41 17 27 15  4
 29 15  1 21 14 11 26 17 30 38 10 33 36 20  4 18 39 16 31  3 35  2 32 28 19 13 42  7 12  8  6 40  5  9 25 37 24 27 41 23 22 34
 21 36 32  8  6 23 15 19  2 14 18  4  3 11  5 28 26 13 34 25 30 17  7 42 16 22 39 40 29 37 33 12 41 10 27 31 35 38 24 20  9  1
 39 20 31 29 19  4 38 16 27 30 24 11  2  3 33 15  8 28 18 37 10 13  9 23 36  1 17 22 25 32 26 35 12 42 34  7 40 14 21  5  6 41
 12 11 17 42  9  2 14  7 22 24 25 31 38 41 15 19 36 33 32 28  1 10 29 40 23 18 37 39  6 21 35 27  3 16  8 30  5 26  4 34 13 20
 18 29 33 16 27 42 40 26  7  8 39 24 41  5 30 38  6  9 13  1 32 22  2 34 12 37 11 10 35 20 14 17 21  4 15 19 23 36 28 25 31  3
 28  2  4 18 11  5 23 20 25 35 42 30 31 14  3  9 24 27 19  7 22  6 12 10  1 32 41 36 21 33 16 34 29 13 39 15 38 17 37 26 40  8
  3 26 11 35 24 37 17 36  6  7 13 41  4 32  9  2 31 34 22 15 29  8 40 18 21  5 27  1 14 16 10 38 25 33 20 12 19 42 39 28 30 23
 31  5 22 27 10  6  8 13 34  2 33  7 32 42 26 12 19  4 15  9 40 16 28 38 37 39 35 24 20 29 17 23 11 14  3 25 41 21 36 18  1 30
 15 24  5 37  3 28  7 22 19 34 20 18 17 12 23  8 25 11 36 16 27 41 10  4 31  2  9 32 33 42 21 14 13 29 38 35 26  1 30  6 39 40
 27 37 25  5 13 16 24 41 28  3  2 10 23  4 14 30 11 38  6 19 26 32 21 20 40  9 33 35 34 22 42  8 18 17 12 36 31 15  1 29  7 39
 26 30 10  3 36 22 33 11  5 20 29 21 13 25 31 37 17  2  9 35 18 27 23 39 14 19 32 16 28  6  8 42  4 12  1 38  7 34 40 15 41 24
 32  8 18 31  1 14 34 12 33 28 17 39 37  9 19 27  7  5 30 24 20 23 11 25 15 36 21  6 22 40 41 16 10 26  4  2 42 35 38  3 29 13
  9 14 40 23 37 38 18 15 20 12 36  8  1 22 28 24 27 42  4 32  6 11 41 19 26 10 13 21  7 25 30 29 34 39  2 16 33 31  5 17  3 35
 22 12 15  4 34  1 39 42 32 40  7 35 20 29 11 25  9  6 24 26 37 19 17 16  8 21 14 38 27 28  3 33 30 31 18  5 36 13 10 41 23  2
 40  1 38 20 29 12 28 18 26 21 23 16 24 37  6 41 15 19 27  8  3 39 22  9  7 17 10 33  4 35 31 25  2 30 36 34 14 11 13 42 32  5

Go

Parts 1, 2 and (a small part of) 3

The J & M implementation is based on the C code here. Although this produces satisfactory results for Parts 1 and 2, it is glacial for Part 3 and could only generate 5 order 42 Latin squares in around 22 seconds. Optimizing the code somewhat gets this down to about 14 seconds which suggests that the full 750 could be generated in about 35 minutes though Part 4 is still well out of reach.

All timings are for my Celeron @1.6 GHz and will therefore be much faster on a more modern machine though probably still far too slow for the later Parts. <lang go>package main

import (

   "fmt"
   "math/rand"
   "time"

)

type (

   vector []int
   matrix []vector
   cube   []matrix

)

func toReduced(m matrix) matrix {

   n := len(m)
   r := make(matrix, n)
   for i := 0; i < n; i++ {
       r[i] = make(vector, n)
       copy(r[i], m[i])
   }
   for j := 0; j < n-1; j++ {
       if r[0][j] != j {
           for k := j + 1; k < n; k++ {
               if r[0][k] == j {
                   for i := 0; i < n; i++ {
                       r[i][j], r[i][k] = r[i][k], r[i][j]
                   }
                   break
               }
           }
       }
   }
   for i := 1; i < n-1; i++ {
       if r[i][0] != i {
           for k := i + 1; k < n; k++ {
               if r[k][0] == i {
                   for j := 0; j < n; j++ {
                       r[i][j], r[k][j] = r[k][j], r[i][j]
                   }
                   break
               }
           }
       }
   }
   return r

}

// 'm' is assumed to be 0 based func printMatrix(m matrix) {

   n := len(m)
   for i := 0; i < n; i++ {
       for j := 0; j < n; j++ {
           fmt.Printf("%2d ", m[i][j]+1) // back to 1 based
       }
       fmt.Println()
   }
   fmt.Println()

}

// converts 4 x 4 matrix to 'flat' array func asArray16(m matrix) [16]int {

   var a [16]int
   k := 0
   for i := 0; i < 4; i++ {
       for j := 0; j < 4; j++ {
           a[k] = m[i][j]
           k++
       }
   }
   return a

}

// converts 5 x 5 matrix to 'flat' array func asArray25(m matrix) [25]int {

   var a [25]int
   k := 0
   for i := 0; i < 5; i++ {
       for j := 0; j < 5; j++ {
           a[k] = m[i][j]
           k++
       }
   }
   return a

}

// 'a' is assumed to be 0 based func printArray16(a [16]int) {

   for i := 0; i < 4; i++ {
       for j := 0; j < 4; j++ {
           k := i*4 + j
           fmt.Printf("%2d ", a[k]+1) // back to 1 based
       }
       fmt.Println()
   }
   fmt.Println()

}

func shuffleCube(c cube) {

   n := len(c[0])
   proper := true
   iters := n * n * n
   for i := 0; i < iters; i++ {
       var rx, ry, rz int
       for {
           rx = rand.Intn(n)
           ry = rand.Intn(n)
           rz = rand.Intn(n)
           if c[rx][ry][rz] == 0 {
               break
           }
       }
       for {
           var ox, oy, oz int
           for ; ox < n; ox++ {
               if c[ox][ry][rz] == 1 {
                   break
               }
           }
           if !proper && rand.Intn(2) == 0 {
               for ox++; ox < n; ox++ {
                   if c[ox][ry][rz] == 1 {
                       break
                   }
               }
           }

           for ; oy < n; oy++ {
               if c[rx][oy][rz] == 1 {
                   break
               }
           }
           if !proper && rand.Intn(2) == 0 {
               for oy++; oy < n; oy++ {
                   if c[rx][oy][rz] == 1 {
                       break
                   }
               }
           }

           for ; oz < n; oz++ {
               if c[rx][ry][oz] == 1 {
                   break
               }
           }
           if !proper && rand.Intn(2) == 0 {
               for oz++; oz < n; oz++ {
                   if c[rx][ry][oz] == 1 {
                       break
                   }
               }
           }

           c[rx][ry][rz]++
           c[rx][oy][oz]++
           c[ox][ry][oz]++
           c[ox][oy][rz]++

           c[rx][ry][oz]--
           c[rx][oy][rz]--
           c[ox][ry][rz]--
           c[ox][oy][oz]--

           if c[ox][oy][oz] < 0 {
               rx, ry, rz = ox, oy, oz
               proper = false
           } else {
               proper = true
               break
           }
       }
   }

}

func toMatrix(c cube) matrix {

   n := len(c[0])
   m := make(matrix, n)
   for i := 0; i < n; i++ {
       m[i] = make(vector, n)
   }
   for i := 0; i < n; i++ {
       for j := 0; j < n; j++ {
           for k := 0; k < n; k++ {
               if c[i][j][k] != 0 {
                   m[i][j] = k
                   break
               }
           }
       }
   }
   return m

}

// 'from' matrix is assumed to be 1 based func makeCube(from matrix, n int) cube {

   c := make(cube, n)
   for i := 0; i < n; i++ {
       c[i] = make(matrix, n)
       for j := 0; j < n; j++ {
           c[i][j] = make(vector, n)
           var k int
           if from == nil {
               k = (i + j) % n
           } else {
               k = from[i][j] - 1
           }
           c[i][j][k] = 1
       }
   }
   return c

}

func main() {

   rand.Seed(time.Now().UnixNano())

   // part 1
   fmt.Println("PART 1: 10,000 latin Squares of order 4 in reduced form:\n")
   from := matrix{{1, 2, 3, 4}, {2, 1, 4, 3}, {3, 4, 1, 2}, {4, 3, 2, 1}}
   freqs4 := make(map[[16]int]int, 10000)
   c := makeCube(from, 4)
   for i := 1; i <= 10000; i++ {
       shuffleCube(c)
       m := toMatrix(c)
       rm := toReduced(m)
       a16 := asArray16(rm)
       freqs4[a16]++
   }
   for a, freq := range freqs4 {
       printArray16(a)
       fmt.Printf("Occurs %d times\n\n", freq)
   }

   // part 2
   fmt.Println("\nPART 2: 10,000 latin squares of order 5 in reduced form:")
   from = matrix{{1, 2, 3, 4, 5}, {2, 3, 4, 5, 1}, {3, 4, 5, 1, 2},
       {4, 5, 1, 2, 3}, {5, 1, 2, 3, 4}}
   freqs5 := make(map[[25]int]int, 10000)
   c = makeCube(from, 5)
   for i := 1; i <= 10000; i++ {
       shuffleCube(c)
       m := toMatrix(c)
       rm := toReduced(m)
       a25 := asArray25(rm)
       freqs5[a25]++
   }
   count := 0
   for _, freq := range freqs5 {
       count++
       if count > 1 {
           fmt.Print(", ")
       }
       if (count-1)%8 == 0 {
           fmt.Println()
       }
       fmt.Printf("%2d(%3d)", count, freq)
   }
   fmt.Println("\n")

   // part 3
   fmt.Println("\nPART 3: 5 latin squares of order 42, showing the last one:\n")
   start := time.Now()
   var m42 matrix
   c = makeCube(nil, 42)
   for i := 1; i <= 5; i++ {
       shuffleCube(c)
       m42 = toMatrix(c)
   }
   elapsed := time.Since(start)
   printMatrix(m42)
   fmt.Printf("Took %s\n", elapsed)

}</lang>

Output:

Sample run:

PART 1: 10,000 latin Squares of order 4 in reduced form:

 1  2  3  4 
 2  1  4  3 
 3  4  1  2 
 4  3  2  1 

Occurs 2509 times

 1  2  3  4 
 2  4  1  3 
 3  1  4  2 
 4  3  2  1 

Occurs 2571 times

 1  2  3  4 
 2  3  4  1 
 3  4  1  2 
 4  1  2  3 

Occurs 2446 times

 1  2  3  4 
 2  1  4  3 
 3  4  2  1 
 4  3  1  2 

Occurs 2474 times


PART 2: 10,000 latin squares of order 5 in reduced form:

 1(183),  2(189),  3(162),  4(188),  5(191),  6(171),  7(154),  8(212), 
 9(169), 10(177), 11(198), 12(174), 13(181), 14(177), 15(189), 16(162), 
17(202), 18(188), 19(167), 20(194), 21(167), 22(158), 23(157), 24(154), 
25(183), 26(160), 27(192), 28(186), 29(187), 30(171), 31(159), 32(182), 
33(156), 34(198), 35(165), 36(170), 37(166), 38(163), 39(182), 40(161), 
41(198), 42(188), 43(176), 44(190), 45(217), 46(178), 47(153), 48(199), 
49(178), 50(158), 51(192), 52(205), 53(177), 54(184), 55(183), 56(179)


PART 3: 5 latin squares of order 42, showing the last one:

18 21 11 26  2  8 25 39 38 24  3 19 33 37  5 16 30  4  9 40 32 31 36 22  1 42  7 12 27 35 23 13 17 14 15 10 41 29 20 34  6 28 
41 30  9 40 37 11 16 14  2 32 42 33  7  5 12  1 18 34 23 19 26 22 35 25 36 24  4 21 28  6 39 15 20  8 27 38 17  3 13 10 31 29 
 8 29 34  2 19  3  6  4 23 30 36 38 11 39 26 28 10  7 22 24 42 25 16 32 17 14  5  9 33 41 31 40 18 27 13  1 37 21 35 12 20 15 
30 15  8 18 28  7 31  2 16 10 38  4 26 29 17 25  9 35 14 20 41 33 39 11 24  5  3 36 21 27  1 23 37 40 42 22 12 19 34 32 13  6 
39 41 20 17 27 19 24 38 34 16  6 32 29 13 28  3 25  8  1 11 31 12 10 33 23 21 37  2 40  5 18 22 14  7 26 35  9 42 15 36  4 30 
 2  1 23 15 26 35 36 29 13  6 27 31 12 30 40  7 39 19  3 34 21 17 42 20 14 38  9  8 41 11 22 33  4  5 24 28 18 37 25 16 32 10 
28 31  7 10 40 24 30 11 35 23 33 17 32 18 22 12 42 25 13 15  8 21  9 16 41  3 27  5 38 36  6 20 19  4  1 29 39 34 26  2 14 37 
 6 26  3 12 13 40 38 30 33 17 20 29 28  9 34 15 24 32 39 14 11  8 25 21 19  1 35 23  5 16  2 41 36 31  7 37 22  4 10 18 42 27 
19  5 26 31 36 12 33  6  4  1 21 27 38 17  7 20 34 14 32 22  3  2  8 10  9 35 16 18 39 15 37 42 41 29 28 24 30 13 11 40 23 25 
 5 22 36 11 29 42 41 17 39 40  4  9  8 25  1 21  3 24  7 23 35 13 27 26 38 12 33 31 14 28 15 18  2 34 32 20 10 30  6 19 37 16 
33 36 32 28 11 17 14  9 25 21 23  7 15  3 24  2  4 22 31 26 30 10 34 41 27 19 38 29  1 40 20 35 13 18  6 39  8 16 42 37 12  5 
16 25 10  3 23 26 20 32 17  5 31 40 36  1  4 27 14 39 11 28 12  9 24 19 33  8 42 22  2 30 38 21 34 15 29  7 35  6 37 13 41 18 
40 28 17 16 39 25 37 41 22 15 30  8 42 20 11 19 35 26 10 29  7  5 13 18 21  6 36 32 12 24 27  4 33 23  9  3 38  2 31 14  1 34 
25 37  1 29  7 28  9 19 26 22 13 41 21  2  6 39 12  3 16 27 17 42 14 36 18 15 30  4 11 20 35  8 24 32 10 34 40 31 33 38  5 23 
37 34 18 33 35 38 27 23 41  8 28 10 39 40 31  5 11  1 30  9 24 29  3  7 25 32  6 16 26 13 14 19 42 17  2 15 20 36 12  4 22 21 
15  3 37 35 38 21 32 42 36 34 16 18 30 33 19 41 20  5 27 25 13  7 28  1  2 11 24 14  6 17  8 10 40 22 39 12  4  9 23 29 26 31 
10 35 13  1 42  6 34 20  9  4  5 14 22 23 38 30  7 11 28 21 27 32  2 15  8 39 29 40 37 26 25 24 12 19 41 18  3 17 16 31 36 33 
23 33 39 20 25  9 40 34 30 35 15 42 37 14  3 18 21  2  8 12 36  4 17  5 26 31 10  6 13  1 24 16 22 41 38 11 27 28 19  7 29 32 
12 27 16 39 30  4 18 15 14 20 35  1 40  8  9 23 38 36 41  2 34 11 19  6 29 17 22 10 25 37 13 28 31 33  5 42 26  7 32 21 24  3 
24  9 38 42 41 34 21 36 18 25  8 16  1 12 10 17 27 37 19 32 20 26 33 13 30  4 28 15 29 39  7 31  5  3 35 23  6 22 14 11 40  2 
22 39 19 13  9 23 11  7 20 28 10  5 18 36 41 14 40 27 15 16 38  6 31 34  3  2 17 37 35 33 30 12 29 42 25  4 24 32 21  1  8 26 
 9 40 27 36 10 20  4  1 42 14  2 13  5 41 37  8 15 18 25  7 19 23  6 35 32 29 26  3 22 12 33 30 28 21 16 31 34 11 17 24 38 39 
 3 42 25 24  8  5 17 22  1 13 14 36 20 35  2 31 26 29 37 33 18 34 11 30 15 40 19 27  7 10 28 32  9 16  4  6 23 12 38 39 21 41 
20 16 29  9  1  2 15  5 31 18 19 37 35 26 32 24  6 30  4 42 22 28 23  3 12 13 25 39 36 34 41 14 10 38 40 21 11 27  7  8 33 17 
17 32 28 41  6 30  8 37 21 29 24 34 10 38 18 35 19 16 33 31 25 14 15 40  4  9 12 42 23  7  3  5 27 26 22  2 36  1 39 20 11 13 
11  4  5 22 16 15 12 25 40 33  1 39 31  7 23 42 36 10 29  6 14 27 30 38 28 37 13 26 34  9 32  3 35 20 21 41  2 24 18 17 19  8 
32  7 35  6 22 13 28 16 37 26 17  3 24 15 25 40 33  9 18  5 10 20 12  4 11 41 14 30  8 21 29 34 38  2 31 36  1 23 27 42 39 19 
34 18 22 21 32 14 39 26  7 38 12 24 27 10 36 13 29 15 17 30 33  1 41 37 42 25 20 11 19 23  4  2 16  6  8  5 31 40  3 28 35  9 
31 23 40 27  3 41 29 24 11 39 25 21 34 32 15 38 13  6 12 10  9 16 37  8 20 28  1 17  4 18  5 26  7 36 33 19 42 35  2 22 30 14 
38  8 33 19 15 10 23 12 32 42  7  2  6  4 14 36 17 31 35 18 37 39  1 29 16 22 21 13 24 25 34 27  3 11 20  9  5 41 30 26 28 40 
13 20 42  4 17 32  3 28 15  2 37 22 14 16 29 11  1 21 26 39  6 24  5 31 40 27 34 41  9 38 12  7 30 25 19  8 33 10 36 23 18 35 
27  2 30 37 31 22 35  8 19 36 41 12  4 34 39 29 16 23 38 13 28 40 21 24  6 26 15  7 20 42  9 17 25 10 18 14 32  5  1 33  3 11 
 1 17 24 32 20 36 10 31 29 37 22 28 23 11 27 34 41 33 42 38  4  3 40  2  5  7 39 35 15 19 26  9  6 13 14 30 21 18  8 25 16 12 
26 14 15 30 24 18 42 10  8  7 32 25  3 19 33  6 31 28 40 36  5 35  4 23 34 20  2 38 16 29 21  1 11 12 37 27 13 39 41  9 17 22 
35 38 41 23  4 39 26 13 28  3 18 20 19  6 16 32  2 12  5  8  1 37 22 27 10 34 40 33 17 31 42 29 21 30 11 25  7 14 24 15  9 36 
29 24  6  7 21 16 22 33 12 31 11 23 13 27  8 26 28 38 34 35 40 41 18 14 39 10 32  1  3  4 19 37 15  9 36 17 25 20  5 30  2 42 
36 12 31 14 18 29  5 40 10 27 39 30 17 24 21 22 37 13  6  3 15 38 32  9  7 23  8 28 42  2 16 11  1 35 34 33 19 26  4 41 25 20 
14 11  4 25 34  1  7 27  5 19  9 26 41 42 30 33 22 17 21 37  2 15 20 12 35 16 18 24 31  3 40 36 32 39 23 13 29  8 28  6 10 38 
 4 19 14  5 33 37  2 35 24 41 29 15  9 21 20 10 23 42 36 17 39 18 38 28 13 30 31 34 32  8 11  6 26  1 12 40 16 25 22  3 27  7 
 7  6 21 38 14 33 13 18  3 12 40 11  2 22 35 37  5 41 20  4 29 19 26 42 31 36 23 25 10 32 17 39  8 24 30 16 28 15  9 27 34  1 
21 13  2  8 12 27 19  3  6 11 34 35 25 31 42  9 32 40 24  1 16 36  7 39 37 18 41 20 30 22 10 38 23 28 17 26 14 33 29  5 15  4 
42 10 12 34  5 31  1 21 27  9 26  6 16 28 13  4  8 20  2 41 23 30 29 17 22 33 11 19 18 14 36 25 39 37  3 32 15 38 40 35  7 24 

Took 13.714977269s

Parts 1, 2, 3 and (a small part of) 4

The J & M implementation this time is based on the optimized Go code here which is more than 100 times quicker than before. The full 750 order 42 latin squares are now generated in around 17 seconds. Even Part 4 is now within reach with 10 order 256 latin squares being produced in 70 seconds suggesting the full 1,000 could be produced in under 2 hours.

However, this is at the expense of Part 1 now producing non-uniform results and Part 2 (though more uniform) being less than ideal. This doesn't matter so much for Parts 3 and 4 where the number of possibilities is astronomic in any case though it is still, of course, a concern. <lang go>package main

import (

   "fmt"
   "math/rand"
   "time"

)

type (

   vector []int
   matrix []vector

)

func rand2(a, b int) (int, int) {

   if rand.Intn(2) == 0 {
       return a, b
   }
   return b, a

}

func toReduced(m matrix) matrix {

   n := len(m)
   r := make(matrix, n)
   for i := 0; i < n; i++ {
       r[i] = make(vector, n)
       copy(r[i], m[i])
   }
   for j := 0; j < n-1; j++ {
       if r[0][j] != j {
           for k := j + 1; k < n; k++ {
               if r[0][k] == j {
                   for i := 0; i < n; i++ {
                       r[i][j], r[i][k] = r[i][k], r[i][j]
                   }
                   break
               }
           }
       }
   }
   for i := 1; i < n-1; i++ {
       if r[i][0] != i {
           for k := i + 1; k < n; k++ {
               if r[k][0] == i {
                   for j := 0; j < n; j++ {
                       r[i][j], r[k][j] = r[k][j], r[i][j]
                   }
                   break
               }
           }
       }
   }
   return r

}

// 'm' is assumed to be 0 based func printMatrix(m matrix) {

   n := len(m)
   for i := 0; i < n; i++ {
       for j := 0; j < n; j++ {
           fmt.Printf("%2d ", m[i][j]+1) // back to 1 based
       }
       fmt.Println()
   }
   fmt.Println()

}

// converts 4 x 4 matrix to 'flat' array func asArray16(m matrix) [16]int {

   var a [16]int
   k := 0
   for i := 0; i < 4; i++ {
       for j := 0; j < 4; j++ {
           a[k] = m[i][j]
           k++
       }
   }
   return a

}

// converts 5 x 5 matrix to 'flat' array func asArray25(m matrix) [25]int {

   var a [25]int
   k := 0
   for i := 0; i < 5; i++ {
       for j := 0; j < 5; j++ {
           a[k] = m[i][j]
           k++
       }
   }
   return a

}

// 'a' is assumed to be 0 based func printArray16(a [16]int) {

   for i := 0; i < 4; i++ {
       for j := 0; j < 4; j++ {
           k := i*4 + j
           fmt.Printf("%2d ", a[k]+1) // back to 1 based
       }
       fmt.Println()
   }
   fmt.Println()

}

func shuffleMatrix(xy matrix) {

   n := len(xy)
   xz := make(matrix, n)
   yz := make(matrix, n)
   for i := 0; i < n; i++ {
       yz[i] = make([]int, n)
       xz[i] = make([]int, n)
   }
   for i := 0; i < n; i++ {
       for j := 0; j < n; j++ {
           k := xy[i][j]            
           xz[i][k] = j
           yz[j][k] = i
       }
   }

   var mxy, mxz, myz int
   var m [3]int
   proper := true
   minIter := n * n * n
   for iter := 0; iter < minIter || !proper; iter++ {
       var i, j, k, i2, j2, k2 int
       var i2_, j2_, k2_ int

       if proper {
           // Pick a random 0 in the array
           i, j, k = rand.Intn(n), rand.Intn(n), rand.Intn(n)
           for xy[i][j] == k {
               i, j, k = rand.Intn(n), rand.Intn(n), rand.Intn(n)
           }
           // find i2 such that [i2, j, k] is 1. same for j2, k2
           i2 = yz[j][k]
           j2 = xz[i][k]
           k2 = xy[i][j]
           i2_, j2_, k2_ = i, j, k
       } else {
           i, j, k = m[0], m[1], m[2]
           // find one such that [i2, j, k] is 1, same for j2, k2.
           // each is either the value stored in the corresponding
           // slice, or one of our three temporary "extra" 1s.
           // That's because (i, j, k) is -1.
           i2, i2_ = rand2(yz[j][k], myz)
           j2, j2_ = rand2(xz[i][k], mxz)
           k2, k2_ = rand2(xy[i][j], mxy)
       }

       proper = xy[i2][j2] == k2
       if !proper {
           m = [3]int{i2, j2, k2}
           mxy = xy[i2][j2]
           myz = yz[j2][k2]
           mxz = xz[i2][k2]
       }

       xy[i][j] = k2_
       xy[i][j2] = k2
       xy[i2][j] = k2
       xy[i2][j2] = k

       yz[j][k] = i2_
       yz[j][k2] = i2
       yz[j2][k] = i2
       yz[j2][k2] = i

       xz[i][k] = j2_
       xz[i][k2] = j2
       xz[i2][k] = j2
       xz[i2][k2] = j
   }

}

// 'from' matrix is assumed to be 1 based func makeMatrix(from matrix, n int) matrix {

   m := make(matrix, n)
   for i := 0; i < n; i++ {
       m[i] = make(vector, n)
       for j := 0; j < n; j++ {
           var k int
           if from == nil {
               k = (i + j) % n
           } else {
               k = from[i][j] - 1
           }
           m[i][j] = k
       }
   }
   return m

}

func main() {

   rand.Seed(time.Now().UnixNano())

   // part 1
   fmt.Println("PART 1: 10,000 latin Squares of order 4 in reduced form:\n")
   from := matrix{{1, 2, 3, 4}, {2, 1, 4, 3}, {3, 4, 1, 2}, {4, 3, 2, 1}}
   freqs4 := make(map[[16]int]int, 10000)
   m := makeMatrix(from, 4)
   for i := 1; i <= 10000; i++ {
       shuffleMatrix(m)
       rm := toReduced(m)
       a16 := asArray16(rm)
       freqs4[a16]++
   }
   for a, freq := range freqs4 {
       printArray16(a)
       fmt.Printf("Occurs %d times\n\n", freq)
   }

   // part 2
   fmt.Println("\nPART 2: 10,000 latin squares of order 5 in reduced form:")
   from = matrix{{1, 2, 3, 4, 5}, {2, 3, 4, 5, 1}, {3, 4, 5, 1, 2},
       {4, 5, 1, 2, 3}, {5, 1, 2, 3, 4}}
   freqs5 := make(map[[25]int]int, 10000)
   m = makeMatrix(from, 5)
   for i := 1; i <= 10000; i++ {
       shuffleMatrix(m)
       rm := toReduced(m)
       a25 := asArray25(rm)
       freqs5[a25]++
   }
   count := 0
   for _, freq := range freqs5 {
       count++
       if count > 1 {
           fmt.Print(", ")
       }
       if (count-1)%8 == 0 {
           fmt.Println()
       }
       fmt.Printf("%2d(%3d)", count, freq)
   }
   fmt.Println("\n")

   // part 3
   fmt.Println("\nPART 3: 750 latin squares of order 42, showing the last one:\n")
   start := time.Now()
   m = makeMatrix(nil, 42)
   for i := 1; i <= 750; i++ {
       shuffleMatrix(m)
   }
   elapsed := time.Since(start)
   printMatrix(m)
   fmt.Printf("Took %s\n", elapsed)

   // part 4
   fmt.Println("\nPART 5: 10 latin squares of order 256:\n")
   start = time.Now()
   m = makeMatrix(nil, 256)
   for i := 1; i <= 10; i++ {
       shuffleMatrix(m)
   }
   elapsed = time.Since(start)
   fmt.Printf("Took %s\n", elapsed)

}</lang>

Output:

Sample run:

PART 1: 10,000 latin Squares of order 4 in reduced form:

 1  2  3  4 
 2  4  1  3 
 3  1  4  2 
 4  3  2  1 

Occurs 2976 times

 1  2  3  4 
 2  1  4  3 
 3  4  2  1 
 4  3  1  2 

Occurs 3090 times

 1  2  3  4 
 2  3  4  1 
 3  4  1  2 
 4  1  2  3 

Occurs 3053 times

 1  2  3  4 
 2  1  4  3 
 3  4  1  2 
 4  3  2  1 

Occurs 881 times


PART 2: 10,000 latin squares of order 5 in reduced form:

 1(237),  2(170),  3(160),  4(181),  5(174),  6(211),  7(191),  8(153), 
 9(162), 10(153), 11(175), 12(184), 13(169), 14(162), 15(174), 16(168), 
17(177), 18(178), 19(185), 20(169), 21(234), 22(186), 23(173), 24(180), 
25(184), 26(166), 27(176), 28(172), 29(154), 30(145), 31(148), 32(165), 
33(166), 34(175), 35(154), 36(176), 37(166), 38(162), 39(180), 40(206), 
41(191), 42(236), 43(179), 44(223), 45(165), 46(148), 47(181), 48(173), 
49(164), 50(226), 51(175), 52(177), 53(239), 54(169), 55(171), 56(182)


PART 3: 750 latin squares of order 42, showing the last one:

 8 23 13 39 42 41  3 15 26  9 18 11 30 19  7 10 22  5 29 34 21 12 17 20 36  2 28  4 40 33 31 35 37 14  1 27 38 25 24  6 32 16 
36 16 23 30 10 34 31  6  5 11 39 27 14 37 26 25 12 38 17  1  4 20 35  2  3 18 21 24 15  7 13 32 40  8 19 42  9 28 41 33 22 29 
23 10  1 37 24 18 34 35 16 21 11 33  5 12 40 17 36 27  6 42 25 39 20  9 29 15 14  7  8 26  3 41 22 32  2 19 31 13 30  4 28 38 
 4  9 35 20 25 10 13 32 27 39 14 15 12 42 34 19 29  6 23 30 18 36  1  3  7 38 24 28 21  8 16 40 33 41 31 26  5  2 22 11 37 17 
 1 13 40 14 26  5 11 21 28 29 27 36  4 25  6 22 15 18 30 35  9 10 39 33 19 16  3 20  7 34  2 12 23 31 37 17  8 41 32 24 38 42 
33 38 34 21 15 42 40 19 29  4  2 35 24 28 10 27 37 17 26  9  3 31 13 11 14 41 23 30 39 36  5  6 25  1 16 20  7  8 18 32 12 22 
13 14 29 16 37 30 25 41 39 31 38  5 40  2 22 34 23 32 28 27  7 24  9 35 18  1  8  3 33 12 10 26 19 17  4  6 21 15 42 20 36 11 
 5 41 17 24 28  7 14 36  1 13  8 16  9 18 42 26 20  3 37  2 32 29 11 34 38 19 22 40 31  6 25 27  4 30 12 15 10 23 39 35 33 21 
11 22 28 27 35 15 19  8 41 24 33 31 20 26 36 23  7 39 34 18 13  1 38 25  5  4 32 17  3 40 42 30  9 37 10 14 16 21 29  2  6 12 
38 20 24  2 23  3 27 10 18 41 32 17 22  7 31 30 28 36 35 19  6 42  4 13 40 34 39 25 12 21  9 14  1 15  5 16 37 26 33 29 11  8 
42 37 15 31  7 20 18  9  4 28 10  3 16  6 13  8  5 33 40 12 24 11 27 41  1 23  2 38 32 14 21 17 35 39 25 29 30 19 26 22 34 36 
41 18 22 17 38 40 29 30 10 33  7 25 21 34  9 12 11  4  3 24 14 27  2  1 35 42 26 16 19 23 39  8 31 13 28 32 36 20 37 15  5  6 
17 33 18 10 21 11  4 27  6 23 41 28 37 15 19 13 40  7 16 39 29 32 30 12  8 26  1 42 38  2 22 36 34  9 35 31  3  5 20 14 25 24 
28 17  2  8 33 27  5 34 22 15 23 13  1 35 41 29 42 19 12  6 16 38 10 39 20 14 40 11 36 31 26  4 21 18 32 25 24  9  3  7 30 37 
12 39 36 35  8 21 28 13  2  6 22 23 27  3  5 11 31 29 15 14 17 33 32 30 42 24 34  9 26 25 19 37 41  4 40 10  1 38  7 16 20 18 
16 25 39  3 40  6  8  2 20  1 12 10 35 30 17 41 13 37 32 26 19 15 34  7 31 22  4 33 29 18 24 23 42 27 11  5 28 14 38 36 21  9 
25 40 20 38 29 14 24 26 11 42 35 37 39 13  2  7  3 23 31 10  5 16 21 17  6  9 12 27 41 15 18 19 28 33 22  1  4 34 36 30  8 32 
24 15 25 33 11  1 35  3 37  8 20 34 26 14 28  2 30 22 42 29 31 19 41 32 23 40 38  6 16 10 17  9 39 21 18  4 12 36 13  5  7 27 
14 29  5 42 31 37 21 23  9 27 17 39  7 32  8 35 41  1 11 25 22 30 36 16  2 33  6 13 18 19 20 15 24 40 26 38 34 12  4 10  3 28 
40 26 31 32  1 19  2  7 35  3  9 18  6 23 15 28 38 16 21 37 30 14  8 29  4 36 42  5 27 22 11 20 13 12 33 24 41 10 34 17 39 25 
21  2  8 29 20  9 22 18 38 14 16  1 33 27 37  5 26 12 24  3 40 28 19 15 32 25 17 31  6 41  4 13 11 36 39 34 23 30 35 42 10  7 
10 21  6 36  2 39 37 42  8 20 15 24 38 41  1 32  4 25 27 40 33 23 16 31  9 11 19 18 34 13  7  5 17 22 30 12 14 35 28 26 29  3 
 7 11 38 28 19 32 36 14 31  5 34 26  3 22 33 40 17  2  8 16 12  4 24 10 21 13 18 29 23 30 27 25 20  6 41 37 15 42  9  1 35 39 
30 19  4 34 12 22 10 33  7  2  3  9 31  5 16 20  8 11  1 28 41 25  6 37 13 35 36 32 42 29 38 18 27 24 15 39 26 17 21 40 14 23 
 2 35 12  1 27 26 32 22 13  7 25  4 29 17 39  9 18 31 36 21 15  8 23 38 10  3 30 37  5 20 34 28  6 42 24 11 33 16 14 19 40 41 
19 31 16  7 41 28 38 11 24 40 42 12 36  8 27 37 39 35  4 13 26  9  5 23 33  6 20  1  2 32 30 21 29 34 14  3 17 22 15 25 18 10 
 9 12 11 18 13 25 30 28  3 32 40 20 23 33 24 36 19 26 38  5 39 41  7  8 22 37 15 14  1 42  6 29 16 10 34 21 35 31  2 27 17  4 
26 28 10  9  4 33  6 17 23 34  5 38 25 36 29 31 35 21 22 41 42  2 15 40 30 20 16 39 24  3 12 11 14 19 13  7 18 32  8 37 27  1 
31 32 37 11 30 29 16 20 21 25 24 40 17 38 35  4  9 15 33 36 10  6 12 28 26 27 13 19 22  1 14  7  8  5  3 41 39 18 23 34 42  2 
 3 36  9 15 17  4 39 31 40 22  1  7  2 21 38  6 16 13  5 33 20 34 28 14 41 32 35 23 10 24  8 42 12 29 27 30 25 37 11 18 19 26 
18  8 27 22 16 38  1 29 32 26 30 42 28 11 14 21  6 34 13 15 35  5 33 19 24 39 37 41 17  4 23 10  7 20  9 36 40  3 25 12  2 31 
34 24 30  4  5 31  7 12 36 38 19  6 42  1 32 33 14 41 10 17 11 26 37 22 16 29 25  8 20 39 35  2 18 23 21 28 13 40 27  3  9 15 
37  7 41  5 18 12 20 25 14 35 21 32 13 16  4 15 10 24 39 11 27 22  3 36 28 31 33 34  9 17 29 38 30 26 42 40  2  1  6  8 23 19 
27  4 26 41 14 24 17 37 34 30 36  8 32 40 12 42  2 10 18 38 28 13 31  6 15  7 29 21 25  9 33  1  3 11 20 22 19 39  5 23 16 35 
39 27 42 25 36  8  9  4 15 18 13 14 34 20 30 16 21 28  7 22  2 40 29 26 37 17 41 12 11  5 32 31 10  3 23 35  6 24 19 38  1 33 
29  5 33 12  3 35 23 40 42 19  6  2 15 39 25 18 32 30 41  4 37 21 14 24 27 28 11 10 13 16  1 22 36 38 17  8 20  7 31  9 26 34 
22 30 32 40  6 23 33 16 12 17 37 21 19 29 18  3 34  9 14  7 36 35 26 42 25 10  5 15  4 38 41 24  2 28  8 13 27 11  1 39 31 20 
20 42  3 19  9 17 12 38 30 37 28 29 41 24 11 39  1  8  2 32 23  7 40 21 34  5 27 26 14 35 36 16 15 25  6 18 22 33 10 31  4 13 
35  3  7  6 32 16 15  5 19 12 29 41  8 31 20 14 33 42 25 23  1 18 22 27 39 21 10 36 30 28 37 34 26  2 38  9 11  4 17 13 24 40 
15  1 19 23 34 36 42 24 33 10 26 22 11  9 21 38 25 40 20 31  8  3 18  4 17 30  7 35 37 27 28 39  5 16 29  2 32  6 12 41 13 14 
32  6 21 13 39  2 26  1 17 16 31 30 10  4  3 24 27 14 19 20 34 37 25 18 12  8  9 22 35 11 15 33 38  7 36 23 42 29 40 28 41  5 
 6 34 14 26 22 13 41 39 25 36  4 19 18 10 23  1 24 20  9  8 38 17 42  5 11 12 31  2 28 37 40  3 32 35  7 33 29 27 16 21 15 30 

Took 16.74757144s

PART 5: 10 latin squares of order 256:

Took 1m9.236940447s