The New Sudoku Players' Forum

[Mathimagics]

MOSS = Mutually Orthogonal Sudoku Squares.
Two Sudoku grids (GA, GB) are MOSS (orthogonal) if, for every cell position (r, c), the pairs (A, B) that are formed by A = GA(r, c), B = GB(r, c), are all distinct.

A couple of years back we had a lively discussion of transversals & orthogonality.

I have now tested every ED Sudoku grid and the estimate of 1 in ~20,000 grids having an orthogonal mate was pretty close. There are 287,109 such grids, or 1 in 19,061.51.

The MC grid has 279 transversals, and it turns out that really is the maximum across all grids.

The strong correlation between automorphisms and orthogonality is clear in this table of orthogonal grids by automorphism count:

Code: Select all

  NA        Grids       Orthog        P(O) 
----------------------------------------------
   1   5472170387       257683      0.000047
   2       548449        25347      0.046216
   3         7336         2228      0.303708
   4         2826          854      0.302194
   6         1257          763      0.607001
   8           29           13      0.448276
   9           42           36      0.857143
  12           92           74      0.804348
  18           85           77      0.905882
  27+          35           34      0.971428
----------------------------------------------
       5472730538       287109      0.00005246
----------------------------------------------


So, the automorphic grids are just ~0.01% of the total grids, but they represent over 10% of the orthogonal cases.

[Mathimagics]

Minimally Orthogonal Grids

Orthogonality requires a set of 9 mutually disjoint transversals. So, at least 9 transversals are needed, but are there any instances of orthogonal grids with only 9 transversals?

I believe that there are only 3 grids with this property:

Code: Select all

123456789456789123798213654285174396314695278967832541541967832679328415832541967
123456789456789123897231564214678395675394218938512647362845971541967832789123456
123456789456789231789312456245638917618927345937145628364871592591264873872593164

The transversals for the first grid are shown below:

Minimally Orthog Example: Show

Code: Select all

 +-------+-------+-------+
 | 1 2 3 | 4 5 6 | 7 8 9 |
 | 4 5 6 | 7 8 9 | 1 2 3 |
 | 7 9 8 | 2 1 3 | 6 5 4 |
 +-------+-------+-------+
 | 2 8 5 | 1 7 4 | 3 9 6 |
 | 3 1 4 | 6 9 5 | 2 7 8 |
 | 9 6 7 | 8 3 2 | 5 4 1 |
 +-------+-------+-------+
 | 5 4 1 | 9 6 7 | 8 3 2 |
 | 6 7 9 | 3 2 8 | 4 1 5 |
 | 8 3 2 | 5 4 1 | 9 6 7 |
 +-------+-------+-------+

 +-------+-------+-------+   +-------+-------+-------+   +-------+-------+-------+
 | 1 . . | . . . | . . . |   | . 2 . | . . . | . . . |   | . . 3 | . . . | . . . |
 | . . . | 7 . . | . . . |   | . . . | . 8 . | . . . |   | . . . | . . 9 | . . . |
 | . . . | . . . | 6 . . |   | . . . | . . . | . . 4 |   | . . . | . . . | . 5 . |
 +-------+-------+-------+   +-------+-------+-------+   +-------+-------+-------+
 | . . 5 | . . . | . . . |   | . . . | 1 . . | . . . |   | 2 . . | . . . | . . . |
 | . . . | . 9 . | . . . |   | 3 . . | . . . | . . . |   | . . . | 6 . . | . . . |
 | . . . | . . . | . 4 . |   | . . . | . . . | 5 . . |   | . . . | . . . | . . 1 |
 +-------+-------+-------+   +-------+-------+-------+   +-------+-------+-------+
 | . . . | . . . | . . 2 |   | . . . | . . 7 | . . . |   | . . . | . . . | 8 . . |
 | . . . | . . 8 | . . . |   | . . 9 | . . . | . . . |   | . 7 . | . . . | . . . |
 | . 3 . | . . . | . . . |   | . . . | . . . | . 6 . |   | . . . | . 4 . | . . . |
 +-------+-------+-------+   +-------+-------+-------+   +-------+-------+-------+

 +-------+-------+-------+   +-------+-------+-------+   +-------+-------+-------+
 | . . . | 4 . . | . . . |   | . . . | . 5 . | . . . |   | . . . | . . 6 | . . . |
 | . . . | . . . | 1 . . |   | . . . | . . . | . 2 . |   | . . . | . . . | . . 3 |
 | . 9 . | . . . | . . . |   | 7 . . | . . . | . . . |   | . . 8 | . . . | . . . |
 +-------+-------+-------+   +-------+-------+-------+   +-------+-------+-------+
 | . . . | . . . | . . 6 |   | . . . | . . 4 | . . . |   | . . . | . 7 . | . . . |
 | . . . | . . 5 | . . . |   | . . . | . . . | . . 8 |   | . . . | . . . | 2 . . |
 | . . 7 | . . . | . . . |   | . 6 . | . . . | . . . |   | 9 . . | . . . | . . . |
 +-------+-------+-------+   +-------+-------+-------+   +-------+-------+-------+
 | . . . | . . . | . 3 . |   | . . 1 | . . . | . . . |   | . 4 . | . . . | . . . |
 | . . . | . 2 . | . . . |   | . . . | 3 . . | . . . |   | . . . | . . . | . 1 . |
 | 8 . . | . . . | . . . |   | . . . | . . . | 9 . . |   | . . . | 5 . . | . . . |
 +-------+-------+-------+   +-------+-------+-------+   +-------+-------+-------+

 +-------+-------+-------+   +-------+-------+-------+   +-------+-------+-------+
 | . . . | . . . | 7 . . |   | . . . | . . . | . 8 . |   | . . . | . . . | . . 9 |
 | 4 . . | . . . | . . . |   | . 5 . | . . . | . . . |   | . . 6 | . . . | . . . |
 | . . . | . . 3 | . . . |   | . . . | . 1 . | . . . |   | . . . | 2 . . | . . . |
 +-------+-------+-------+   +-------+-------+-------+   +-------+-------+-------+
 | . . . | . . . | . 9 . |   | . . . | . . . | 3 . . |   | . 8 . | . . . | . . . |
 | . 1 . | . . . | . . . |   | . . 4 | . . . | . . . |   | . . . | . . . | . 7 . |
 | . . . | 8 . . | . . . |   | . . . | . . 2 | . . . |   | . . . | . 3 . | . . . |
 +-------+-------+-------+   +-------+-------+-------+   +-------+-------+-------+
 | . . . | . 6 . | . . . |   | . . . | 9 . . | . . . |   | 5 . . | . . . | . . . |
 | . . . | . . . | . . 5 |   | 6 . . | . . . | . . . |   | . . . | . . . | 4 . . |
 | . . 2 | . . . | . . . |   | . . . | . . . | . . 7 |   | . . . | . . 1 | . . . |
 +-------+-------+-------+   +-------+-------+-------+   +-------+-------+-------+


[Mathimagics]

Grids with No Transversals

These are pretty rare, also. There only seem to be 74, and 50 of those are in minlex band #1.

Grids with no transversals: Show

Code: Select all

123456789456789123789123456214367598367598214598214367632941875875632941941875632
123456789456789123789123456214397865397865214865214397572938641641572938938641572
123456789456789123789123456214537968537968214968214537341672895672895341895341672
123456789456789123789123456214537968537968214968214537341895672672341895895672341
123456789456789123789123456214537968537968214968214537345671892671892345892345671
123456789456789123789123456214537968537968214968214537345892671671345892892671345
123456789456789123789123456214538697538697214697214538345862971862971345971345862
123456789456789123789123456214538697538697214697214538345971862862345971971862345
123456789456789123789123456214567938567938214938214567341675892675892341892341675
123456789456789123789123456214567938567938214938214567341892675675341892892675341
123456789456789123789123456214567938567938214938214567342671895671895342895342671
123456789456789123789123456214567938567938214938214567342895671671342895895671342
123456789456789123789123456214567938567938214938214675341675892675892341892341567
123456789456789123789123456214567938675938214938214675341675892567892341892341567
123456789456789123789123456214568937568937214937214568392845671671392845845671392
123456789456789123789123456214597638597638214638214597345862971862971345971345862
123456789456789123789123456214635897635897214897214635341562978562978341978341562
123456789456789123789123456214635897635897214897214635341972568568341972972568341
123456789456789123789123456214635897635897214897214635341978562562341978978562341
123456789456789123789123456214635897635897214897214635348971562562348971971562348
123456789456789123789123456214635978635978214978214635341562897562897341897341562
123456789456789123789123456214635978635978214978214635341567892567892341892341567
123456789456789123789123456214635978635978214978214635341592867592867341867341592
123456789456789123789123456214635978635978214978214635341597862597862341862341597
123456789456789123789123456214635978635978214978214635341892567567341892892567341
123456789456789123789123456214635978635978214978214635341897562562341897897562341
123456789456789123789123456214638597597214638638597214345971862862345971971862345
123456789456789123789123456214638975638975214975214638341567892567892341892341567
123456789456789123789123456214638975638975214975214638341592867592867341867341592
123456789456789123789123456214638975638975214975214638341597862597862341862341597
123456789456789123789123456214638975638975214975214638341867592592341867867592341
123456789456789123789123456214638975638975214975214638341892567567341892892567341
123456789456789123789123456214638975638975214975214638341897562562341897897562341
123456789456789123789123456214675938675938214938214675341892567567341892892567341
123456789456789123789123456214675938675938214938214675347591862591862347862347591
123456789456789123789123456214678935678935214935214678341597862597862341862341597
123456789456789123789123456214678935678935214935214678341892567567341892892567341
123456789456789123789123456214837695695214837837695214342568971568971342971342568
123456789456789123789123456214837695695214837837695214342971568568342971971568342
123456789456789123789123456214937865865214937937865214348572691572691348691348572
123456789456789123789123456214937865865214937937865214348672591591348672672591348
123456789456789123789123456214938567567214938938675214341892675675341892892567341
123456789456789123789123456214938567675214938938675214341892675567341892892567341
123456789456789123789123456214938675675214938938675214347591862591862347862347591
123456789456789123789123456214938675675214938938675214347862591591347862862591347
123456789456789123789123456214968537537214968968537214345671892671892345892345671
123456789456789123789123456234567891567891234918342675342918567675234918891675342
123456789456789123789123456234567918675891234891342567342918675567234891918675342
123456789456789123789123456234597618567831942891264375345918267678342591912675834
123456789456789123789123456247538961538961247961274538374692815692815374815347692
123456789456789123789123456247538961538961274961274538374692815692815347815347692
123456789456789123789123456267591348591834672834267915375618294618942537942375861
123456789456789123789123465214635897635897214897214536341562978562978341978341652
123456789456789123789123465214635978635978214978214536341562897562897341897341652
123456789456789123789123465214937856865214937937865214372591648548672391691348572
123456789456789123789123465217645938645938217938217546371564892564892371892371654
123456789456789123789123465234597618567831942891264357345918276678342591912675834
123456789456789123789123465234867951567291348891534672345972816678315294912648537
123456789456789123789123465237594618561837942894261357378642591612975834945318276
123456789456789123789123465267591348591834672834267951375618294618942537942375816
123456789456789123789123465267915348591348672834672951375861294618294537942537816
123456789456789123789123465294375618537618942861942357348267591672591834915834276
123456789456789123789132564217564938645893217938271456371645892564928371892317645
123456789456789123897231564214895637738164295965372841372548916589613472641927358
123456789456789123897231564231564978564978231789312645312897456645123897978645312
123456789456789123897231564231564978564978231789312645312897456648125397975643812
123456789456789123897231564231564978569378241784912635312897456645123897978645312
123456789456789123897231564231645978649378251785912436312897645564123897978564312
123456789456789132789132546231574698574698321698321475312845967845967213967213854
123456789456789132789132546234891675671325894895674321312547968547968213968213457
123456789457189236689372541291563874378941652564728193715234968832697415946815327
123456789457189236698237145246915873379864512581372694714623958832591467965748321
123456789457189263869273451218564397745391628936728514381645972574912836692837145
123456789457189623689723451241568397396247518578391246735914862812635974964872135

[Mathimagics]

MOSS for Variants

I have tested all ED grids for the following Sudoku variants:

• SudokuX: diagonals

• SudokuW: aka Windoku

• SudokuP: aka Disjoint Groups, "Color Sudoku"

The results are:

Code: Select all

   ------------------------------------------------------
     9x9           ED Grids        Orthog     ED / Orthog
   ------------------------------------------------------

   Sudoku     5,472,730,538       287,109          19,061

   SudokuX    1,596,582,158        13,972         114,270

   SudokuW       68,239,994         1,432          47,654

   SudokuP       53,666,689       107,033             501



MOSS (orthogonal pairs) occur least with SudokuX (1 grid in 114,270). This can be attributed to the reduced number of transversals available. We need 9 disjoint transversals where each transversal not only hits every row/col/box, but must also contain exactly one cell from each of the two diagonals.

The real standout is SudokuP, where one in every 501 grids has at least one orthogonal SudokuP pairing.

Sample MOSS pairs for each variant are given below.

SudokuX: Show

Code: Select all

 +-------+-------+-------+    +-------+-------+-------+
 | 1 2 3 | 4 5 6 | 7 8 9 |    | 1 2 3 | 4 5 6 | 7 8 9 |
 | 4 5 8 | 3 7 9 | 6 2 1 |    | 9 8 6 | 7 1 2 | 5 4 3 |
 | 7 9 6 | 2 8 1 | 5 4 3 |    | 4 5 7 | 8 3 9 | 1 6 2 |
 +-------+-------+-------+    +-------+-------+-------+
 | 6 1 2 | 8 9 7 | 4 3 5 |    | 2 6 1 | 9 7 8 | 3 5 4 |
 | 9 8 7 | 5 3 4 | 1 6 2 |    | 3 4 5 | 2 6 1 | 8 9 7 |
 | 3 4 5 | 1 6 2 | 8 9 7 |    | 8 7 9 | 5 4 3 | 2 1 6 |
 +-------+-------+-------+    +-------+-------+-------+
 | 5 3 4 | 7 2 8 | 9 1 6 |    | 6 1 2 | 3 9 5 | 4 7 8 |
 | 2 6 1 | 9 4 5 | 3 7 8 |    | 5 3 4 | 6 8 7 | 9 2 1 |
 | 8 7 9 | 6 1 3 | 2 5 4 |    | 7 9 8 | 1 2 4 | 6 3 5 |
 +-------+-------+-------+    +-------+-------+-------+


SudokuW: Show

Code: Select all

+-------+-------+-------+  +-------+-------+-------+
| 1 2 3 | 4 5 6 | 7 8 9 |  | 1 2 3 | 4 5 6 | 7 8 9 |
| 4 6 7 | 3 9 8 | 5 1 2 |  | 8 9 5 | 2 1 7 | 3 4 6 |
| 8 9 5 | 1 7 2 | 3 4 6 |  | 4 6 7 | 8 3 9 | 5 1 2 |
+-------+-------+-------+  +-------+-------+-------+
| 5 4 2 | 8 3 9 | 6 7 1 |  | 9 3 4 | 1 7 2 | 8 6 5 |
| 7 8 9 | 5 6 1 | 2 3 4 |  | 2 5 8 | 6 4 3 | 1 9 7 |
| 6 3 1 | 2 4 7 | 8 9 5 |  | 7 1 6 | 5 9 8 | 2 3 4 |
+-------+-------+-------+  +-------+-------+-------+
| 3 7 4 | 9 2 5 | 1 6 8 |  | 6 4 2 | 7 8 1 | 9 5 3 |
| 9 5 8 | 6 1 3 | 4 2 7 |  | 5 8 9 | 3 2 4 | 6 7 1 |
| 2 1 6 | 7 8 4 | 9 5 3 |  | 3 7 1 | 9 6 5 | 4 2 8 |
+-------+-------+-------+  +-------+-------+-------+


SudokuP: Show

Code: Select all

+-------+-------+-------+  +-------+-------+-------+
| 1 2 3 | 4 5 6 | 7 8 9 |  | 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 7 | 2 9 8 | 3 1 6 |  | 9 8 6 | 1 7 3 | 2 4 5 |
| 8 9 6 | 1 3 7 | 4 2 5 |  | 7 5 4 | 2 8 9 | 1 3 6 |
+-------+-------+-------+  +-------+-------+-------+
| 2 1 8 | 3 4 5 | 6 9 7 |  | 5 7 2 | 9 3 1 | 8 6 4 |
| 9 7 5 | 6 2 1 | 8 3 4 |  | 4 3 9 | 7 6 8 | 5 1 2 |
| 3 6 4 | 7 8 9 | 2 5 1 |  | 6 1 8 | 5 4 2 | 9 7 3 |
+-------+-------+-------+  +-------+-------+-------+
| 5 3 1 | 8 7 4 | 9 6 2 |  | 2 4 5 | 6 1 7 | 3 9 8 |
| 7 8 9 | 5 6 2 | 1 4 3 |  | 8 9 1 | 3 2 4 | 6 5 7 |
| 6 4 2 | 9 1 3 | 5 7 8 |  | 3 6 7 | 8 9 5 | 4 2 1 |
+-------+-------+-------+  +-------+-------+-------+


[Serg]

Hi, Mathimagics!

The results are:

Code: Select all

   ------------------------------------------------------
     9x9           ED Grids        Orthog     ED / Orthog
   ------------------------------------------------------

   Sudoku     5,472,730,538       287,109          19,061

   SudokuX    1,596,582,158        13,972         114,270

   SudokuW       68,239,994         1,432          47,654

   SudokuP       53,666,689       107,033             501



Interesting results, congratulations! It's interesting - what is the cause of the oddity of ordinary Sudoku orthogonal grids number? Trios or quintets of mutually orthogonal grids?

Red Ed years ago said:

I only said that it was impossible to get more than six mutually orthogonal sudoku grids.

(See the thread "Graeco-Latin Soduku" challenge.) And he posted an example of such "sextet". I think a limitation of 6 mutually orthogonal Sudoku grids came from Latin Squares area. But what is exact numbers of trios, quartets, quintets and sextets for Sudoku solution grids?

Serg

[Mathimagics]

Hi Serg,

So far I have only tested individual grids for existence of 2-MOSS (pairs of MOSS). Yes, it would be interesting to know about the existence of n-MOSS (sets of n mutually orthogonal Suduku grids) for n = 2, 3 ... and to know whether 6 really is the limit here (although I assume Red Ed has solid basis for this).

I will try and investigate further, when I have some free cores !!

Regarding the number of grids, I don't attach any particular significance to the oddness of the ED grid count.

By the way, the MC grid has 139,990 distinct orthogonal pairings, but these (after canonicalisation) reduce to 217 ED grids. (I did these computations only for the automorphic grids).

Cheers
MM

PS: I see in that thread you mentioned, that johnw seems to have noticed the link between orthogonality and SudokuP ...

[Serg]

Hi, Mathimagics!
Limitation of not more than 6 mutually orthogonal Sudoku solution grids came not from Latin Square world. Sequence https://oeis.org/A001438 says that not more than 8 mutually orthogonal 9x9 Latin Squares can exist. So, Red Ed found his 6-grid limit in another way.

Did you find any autoorthogonal Sudoku grids? (I mean grids being orthogonal to some own isomorphs.) Such autoorthogonal grids can also contribute to odd numbers of orthogonal grids.

Serg

[Mathimagics]

Did you find any autoorthogonal Sudoku grids? (I mean grids being orthogonal to some own isomorphs.)

Indeed we did!

Of the 287,109 ED grids with orthogonal pair(s), over 1/6 have auto-orthogonal forms (46,059 grids).

It gets much more interesting if we consider the cases of "self-orthogonal" grids, ie grids A, for which every orthogonal grid B is an isomorph of A.

There are just 736 of these. In 730 cases there is just the one orthog grid B. For 6 grids there are multiple orthog pairs B, each an isomorph of A. These 6 cases are worth reporting, and are listed below.

a) Self-orthogonal, 2 orthog/isomorphic pairs (3 instances):

Code: Select all

A: 123456789456789123789123456267348591591672348834915267348267915672591834915834672
B: 356782914827149563491635278132896457689457132745321896968213745574968321213574689
B: 345267819726981534198453672614832957832579146579614283283146795957328461461795328

A: 123456789456789123789123564231897456564231978897645312375962841618374295942518637
B: 532476189189532764476189325918647253647253891253891647824715936795368412361924578
B: 435678192192354786867921435543192867219786354786435921371569248958247613624813579

A: 123456789457189236689237154295648317316725948748391625571862493832974561964513872
B: 617832459925146837438597216246378591871965342359214678783659124164723985592481763
B: 615342789984176235723985416476823951231659874859417362392568147167234598548791623

b) Self-orthogonal, 4 orthog/isomorphic pairs (1 instance):

Code: Select all

A: 123456789456789231789123645231978456564312897897645312375294168618537924942861573
B: 132456789897213564564789321789564132456132978213897456348925617925671843671348295
B: 134256789978341562625789134413897625897562341562413897281935476359674218746128953
B: 134562789789341562256897413625413897413978625978625134367284951842159376591736248
B: 123456789564897312978312564789645231231789456645231978417528693852963147396174825

c) Self-orthogonal, 12 (!!) orthog/isomorphic pairs (2 instances):

12 pairs, case 1: Show

Code: Select all

A: 123456789456789123798132465219648537345297816867513942534921678681375294972864351
B: 735821964946753812812946753427318695658294137391567248183675429274139586569482371
B: 735821964946753812812946753427319685659284137381567249193675428274138596568492371
B: 735821964946753812812946753428317695657294138391568247173685429284139576569472381
B: 735821964946753812812946753429317685657284139381569247173695428294138576568472391
B: 735821964946753812812946753428319675659274138371568249193685427284137596567492381
B: 735821964946753812812946753429318675658274139371569248183695427294137586567482391
B: 742831956965724813831956742327648195158293467694517238486175329273469581519382674
B: 742831956965724813831956742327649185159283467684517239496175328273468591518392674
B: 742831956965724813831956742328647195157293468694518237476185329283469571519372684
B: 742831956965724813831956742329647185157283469684519237476195328293468571518372694
B: 742831956965724813831956742328649175159273468674518239496185327283467591517392684
B: 742831956965724813831956742329648175158273469674519238486195327293467581517382694

12 pairs, case 2: Show

Code: Select all

A: 123456789457189236689327514235968471716243958948715362392671845564832197871594623
B: 735894126246513789198627534627958341983471265514362978471289653869735412352146897
B: 735894126246513798198627534627958341983471265514362879471289653869735412352146987
B: 735894126246513879198627534627958341983471265514362987471289653869735412352146798
B: 735894126246513978198627534627958341983471265514362897471289653869735412352146789
B: 735894126246513897198627534627958341983471265514362789471289653869735412352146978
B: 735894126246513987198627534627958341983471265514362798471289653869735412352146879
B: 734892561526413789198657324657948213983271645412365978271589436869734152345126897
B: 734892561526413798198657324657948213983271645412365879271589436869734152345126987
B: 734892561526413879198657324657948213983271645412365987271589436869734152345126798
B: 734892561526413978198657324657948213983271645412365897271589436869734152345126789
B: 734892561526413897198657324657948213983271645412365789271589436869734152345126978
B: 734892561526413987198657324657948213983271645412365798271589436869734152345126879