The New Sudoku Players' Forum

[Mathimagics]

I have decided to revisit the mysteries of Orthogonal Sudoku. (For an example see here)

I've been looking at normal Sudoku Squares (SS) and how many are orthogonal (ie: allow creation of orthogonal pairs).

Based on large samplings of random SS it appears that only 1 in 20,000 (roughly) are orthogonal. Compare this with 9x9 Latin squares (LS) for which roughly 1 in 100 have orthogonal mates.

Orthogonality depends on the existence of transversals. A transversal in a 9x9 Latin Square is a set of 9 cells (R, C, N) that covers all 9 rows, columns, and number values. For standard Sudoku Squares a transversal is a set of 9 cells (R, C, B, N) that covers all 9 rows, columns, 3x3 blocks, and number values.

Here is an example of a Sudoku transversal (cells marked *):

Code: Select all


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



Fundamental Theorem of Orthogonality

• A Latin Square of order n has an orthogonal mate iff it has a set of n disjoint transversals, that is, a set of n transversals that covers all n^2.

• The same is true for Sudoku Squares.

Orthogonality testing thus requires a simple recursive function that enumerates all transversals, and another simple recursion to find subsets of 9 disjoint transversals.

9x9 Latin Squares have on average 214 transversals (minimum = 68, maximum = 2241). This is a known result.

9x9 Sudoku Squares have on average just 21 transversals (minimum = 1, maximum = 159). This is based on my samplings of 500 million SS's. (This largely explains the relative scarcity of orthogonal Sudokus).

I will provide examples of Sudoku Squares with minimal and maximal NTV (number of transversals) below.

[Edit: I have found a Sudoku with NO transversals, see below]

[Mathimagics]

This example has only one transversal (marked *). These are rare (sample returned 1 in 25 million):

Code: Select all


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



This one has 159 transversals (maximum known so far):

Code: Select all


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



This example has NO transversals at all (it turned up after 250 million samples):

Code: Select all


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


[Mathimagics]

A natural question arises, what is the least number of transversals needed for a Sudoku to be orthogonal. The theoretical minimum is of course 9, but does such a case exist?

Such a number does guarantee orthogonality. For example I have seen a case where NTV = 66 (3 times the average) but with no orthogonal pair.

So far (1 billion samples tested) the least number of transversals in an orthogonal Sudoku square that I have found is 17:

Code: Select all

 

  1  2  3  | 4  5  6  | 7  8  9
  4  8  7  | 9  2  1  | 5  6  3
  9  6  5  | 3  7  8  | 1  2  4
  ------------------------------
  5  3  8  | 2  4  9  | 6  1  7
  2  4  9  | 6  1  7  | 8  3  5
  7  1  6  | 8  3  5  | 9  4  2
  ------------------------------
  8  7  2  | 5  6  3  | 4  9  1
  3  9  1  | 7  8  4  | 2  5  6
  6  5  4  | 1  9  2  | 3  7  8
 
 NTV = 17


This yields 6 orthogonal pairs shown below:

Code: Select all

 
 Soln #1:
  11 22 33 | 44 55 66 | 77 88 99
  45 84 79 | 97 28 13 | 56 62 31
  96 68 57 | 32 71 89 | 15 24 43
  ------------------------------
  52 37 85 | 21 49 94 | 63 16 78
  23 46 98 | 65 17 72 | 81 39 54
  74 19 61 | 83 36 58 | 92 47 25
  ------------------------------
  87 73 26 | 59 64 35 | 48 91 12
  38 95 14 | 76 82 41 | 29 53 67
  69 51 42 | 18 93 27 | 34 75 86
 
 Soln #2:
  11 22 33 | 44 55 66 | 77 88 99
  45 84 79 | 97 28 13 | 56 62 31
  96 68 57 | 32 71 89 | 15 24 43
  ------------------------------
  52 37 85 | 21 46 94 | 63 19 78
  23 49 98 | 65 17 72 | 81 36 54
  74 16 61 | 83 39 58 | 92 47 25
  ------------------------------
  87 73 26 | 59 64 35 | 48 91 12
  38 95 14 | 76 82 41 | 29 53 67
  69 51 42 | 18 93 27 | 34 75 86
 
 Soln #3:
  11 22 33 | 44 55 66 | 77 88 99
  45 84 79 | 97 28 13 | 56 62 31
  96 68 57 | 32 71 89 | 15 24 43
  ------------------------------
  52 39 85 | 21 47 94 | 63 16 78
  23 46 98 | 65 19 72 | 81 37 54
  74 17 61 | 83 36 58 | 92 49 25
  ------------------------------
  87 73 26 | 59 64 35 | 48 91 12
  38 95 14 | 76 82 41 | 29 53 67
  69 51 42 | 18 93 27 | 34 75 86
 
 Soln #4:
  11 22 33 | 44 55 66 | 77 88 99
  45 84 79 | 97 28 13 | 56 62 31
  96 68 57 | 32 71 89 | 15 24 43
  ------------------------------
  52 36 85 | 21 47 94 | 63 19 78
  23 49 98 | 65 16 72 | 81 37 54
  74 17 61 | 83 39 58 | 92 46 25
  ------------------------------
  87 73 26 | 59 64 35 | 48 91 12
  38 95 14 | 76 82 41 | 29 53 67
  69 51 42 | 18 93 27 | 34 75 86
 
 Soln #5:
  11 22 33 | 44 55 66 | 77 88 99
  45 84 79 | 97 28 13 | 56 62 31
  96 68 57 | 32 71 89 | 15 24 43
  ------------------------------
  52 39 85 | 21 46 94 | 63 17 78
  23 47 98 | 65 19 72 | 81 36 54
  74 16 61 | 83 37 58 | 92 49 25
  ------------------------------
  87 73 26 | 59 64 35 | 48 91 12
  38 95 14 | 76 82 41 | 29 53 67
  69 51 42 | 18 93 27 | 34 75 86
 
 Soln #6:
  11 22 33 | 44 55 66 | 77 88 99
  45 84 79 | 97 28 13 | 56 62 31
  96 68 57 | 32 71 89 | 15 24 43
  ------------------------------
  52 36 85 | 21 49 94 | 63 17 78
  23 47 98 | 65 16 72 | 81 39 54
  74 19 61 | 83 37 58 | 92 46 25
  ------------------------------
  87 73 26 | 59 64 35 | 48 91 12
  38 95 14 | 76 82 41 | 29 53 67
  69 51 42 | 18 93 27 | 34 75 86



[StrmCkr]

Code: Select all

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

edited for clarity:

looks like the {MC} most canonical Grid, which has 648 auto-morphs.
it has 3 distinctive repeating Mini Row/Cols in each of the bands.
order changes but the digits do not.

the biggest part to note is same the 3 x 3 sets do not repeat completely
in all 9 boxes like the MC grid shown below.

Code: Select all

123897645456231978789564312645123897978456231312789564897645123231978456564312789

A version of the MC grid.

[Mathimagics]

Thanks for pointing that out!

I wonder how strong the correlation is between automorphic grids and orthogonality is.

How does one count the automorphisms of a given grid? Do we have to actually enumerate all the possible transformations and check each one, whether its canonicalisation is the original grid?

Better still, is there a file available anywhere with the 560,151 essentially different automorphic grids?

[dobrichev]

Hi,

Here are some of the automorphic grids. The columns look like
-number of automorphisms
-lexicographical index of the top band (of 416)
-lexicographical index of the grid (possibly zero based, I can't remember)

Code: Select all

123456789456789123789123456231564897564897231897231564312645978645978312978312645 # 648 001 964550
123456789456789123789123456231564897564897231897231564312978645645312978978645312 # 108 001 964558
123456789456789123789123456231564897564897231897231564348672915672915348915348672 # 54 001 964568
123456789456789123789123456231564897564897231897231564348915672672348915915672348 # 54 001 964569
123456789456789123789123456231564897564897231978312645312645978645978312897231564 # 36 001 964589
123456789456789123789123456231564978564897312897231645312978564645312897978645231 # 72 001 965096
123456789456789123789123456231564978564978231978231564312645897645897312897312645 # 108 001 965174
123456789456789123789123456231564978564978231978231564312897645645312897897645312 # 36 001 965182
123456789456789123789123456231564978645897231897312564312645897564978312978231645 # 36 001 966422
123456789456789123789123456231597864597864231864231597312678945678945312945312678 # 36 001 985543
123456789456789123789123456231597864597864231864231597312948675675312948948675312 # 36 001 985544
123456789456789123789123456231678945678945231945231678312597864597864312864312597 # 36 001 989378
123456789456789123789123456231678945678945231945231678312894567567312894894567312 # 36 001 989379
123456789456789123789123456231897564564231897897564231348672915672915348915348672 # 27 001 989400
123456789456789123789123456231897564564231897978645312312978645645312978897564231 # 36 001 989404
123456789456789123789123456231897645564312897978564231312978564645231978897645312 # 36 001 989622
123456789456789123789123456234567891567891234891234567318642975642975318975318642 # 54 001 992761
123456789456789123789123456234567891567891234891234567345678912678912345912345678 # 54 001 992769
123456789456789123789123456234567891567891234891234567372615948615948372948372615 # 54 001 992773
123456789456789123789123456235964817817235964964817235392641578578392641641578392 # 54 001 1006748
123456789456789123789123456267591348591834672834267915375618294618942537942375861 # 54 001 1007164
123456789456789123789123456267591834591834267834267591375618942618942375942375618 # 162 001 1007168
123456789456789123789123456267591834591834267834267591375942618618375942942618375 # 54 001 1007169
123456789456789123789132465231564978564978231978213546312645897645897312897321654 # 36 004 50092115
123456789456789123798132465231564897564897231879213546312645978645978312987321654 # 36 009 224283635
123456789456789123897231564231564978564978231789312645312645897645897312978123456 # 54 016 473714886
123456789456789231789123645231564897564897312897231456375618924618942573942375168 # 36 027 1012364857
123456789456789231789123645231564978564897123897231564375942816618375492942618357 # 36 027 1012366524
123456789456789231789312456231564978564978312978123564312645897645897123897231645 # 27 030 1061944621
123456789456789231789312456231645978645978312978123645312564897564897123897231564 # 54 030 1062073983
123456789457189236968372514291738465374265198685941327546813972732694851819527643 # 36 133 4869572229
123456789457189326869372514214965873635847192978213465381624957546798231792531648 # 36 240 5449015463
123456789457289163689173452235964817816735924974812635392641578568397241741528396 # 54 348 5472677656
123456789457289163689173452245968317316745928978312645564897231731524896892631574 # 108 348 5472677695
123456789457893612986217354274538196531964827698721435342685971715349268869172543 # 72 416 5472730538


[eleven]

I wonder how strong the correlation is between automorphic grids and orthogonality is.

Proven to have been wrong

[Mathimagics]

Thanks to dobrichev for that list of automorphic grids.

As expected, these guys have unusually high NTV, and consequently high numbers of orthog mates.

The {MC} case (648 automorphs) has NTV = 279, and these form 139,990 disjoint subsets = orthogonal pairs. Both are record highs.

[David P Bird]

Perhaps this grid will be of interest:

Code: Select all

 *----------*----------*----------*
 | 23 89 56 | 41 17 74 | 95 38 62 |
 | 91 67 34 | 25 82 58 | 43 76 19 |
 | 45 12 78 | 93 69 36 | 21 54 87 |
 *----------*----------*----------*
 | 59 26 83 | 77 44 11 | 32 65 98 |
 | 64 31 97 | 88 55 22 | 16 49 73 |
 | 18 75 42 | 66 33 99 | 84 27 51 |
 *----------*----------*----------*
 | 86 53 29 | 14 71 47 | 68 92 35 |
 | 37 94 61 | 52 28 85 | 79 13 46 |
 | 72 48 15 | 39 96 63 | 57 81 24 |
 *----------*----------*----------*

I devised it in 2007 in response to a knitting group who wanted a design for an Afghan pattern. It has the properties:
a) that the 9 cells in the same position in each box hold complete 1-9 digit sets for the left and right digits.
b) that every left hand digit is paired once with every right hand digit
.

[eleven]

This puzzle looks symmetric (automorph) too ... (would be with rows 4 and 7 swapped)

So i was wrong, there is a correlation.

E.g. for this grid with Gliding-Rows symmetry (move the stacks right and inside the bands the rows cyclically up to get the same grid) it was not hard to find 9 transversals manually.

Code: Select all

123 456 789
456 789 123
789 123 456

234 567 891
567 891 234
891 234 567

345 678 912
678 912 345
912 345 678

Hidden Text: Show

Code: Select all

1*2°3- 4'5"6& 7#8!9
4&5'6" 7 8#9! 1-2*3°    123 456 789
7!8 9# 1°2-3* 4"5&6'

2#3&4* 5-6 7" 8'9°1!
5°6!7' 8&9*1# 2 3"4-    459 378 126
8"9-1  2!3'4° 5*6#7&
 
3 4#5! 6*7°8- 9&1'2"
6-7*8  9"1&2' 3!4 5#    678 912 345
9'1"2& 3#4!5  6°7-8*

[Serg]

Hi, Mathimagics!
You found new interesting property of sudoku solution grids. Congratulations!
I confirm that MC grid has 279 transversals and that the grid

Code: Select all

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

has no transversals.

Wide field for investigations is opening ...

Serg

[Serg]

Hi, StrmCkr!

Code: Select all

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

the {MC} most canonical Grid, it has 648 auto-morphs.
it has 3 repeating Mini Row/Cols in each of the bands.

This is not Most Canonical grid exactly. It contains repeating minirows in each of the bands and repeating minicolumns in 2 stacks (B147 and B369) only. Here is minlex form of this grid:

Code: Select all

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

This is MC grid (minlex form):

Code: Select all

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

Serg

[Edited. I didn't recognized at the moment of posting that grid "having no transversals" doesn't contain repeating minicolumns in B258 stack. So it was wrong to say that this grid and MC grid belong to the same family of grids containing repeating minirows/minicolumns in all bands/stacks. Moreover, I misunderstood StrmCkr - he didn't state that published grid is MC grid exactly, but stated that published grid is similar to MC grid.]

[StrmCkr]

sorry guys for lack of clarity on which of the two grids I had in my post was the "MC" grid .

serg, immediately pointed it out and I updated my post to reflect the lack of continuity in my post.

[Mathimagics]

Code: Select all

 *----------*----------*----------*
 | 23 89 56 | 41 17 74 | 95 38 62 |
 | 91 67 34 | 25 82 58 | 43 76 19 |
 | 45 12 78 | 93 69 36 | 21 54 87 |
 *----------*----------*----------*
 | 59 26 83 | 77 44 11 | 32 65 98 |
 | 64 31 97 | 88 55 22 | 16 49 73 |
 | 18 75 42 | 66 33 99 | 84 27 51 |
 *----------*----------*----------*
 | 86 53 29 | 14 71 47 | 68 92 35 |
 | 37 94 61 | 52 28 85 | 79 13 46 |
 | 72 48 15 | 39 96 63 | 57 81 24 |
 *----------*----------*----------*

I devised it in 2007 in response to a knitting group who wanted a design for an Afghan pattern. It has the properties:
a) that the 9 cells in the same position in each box hold complete 1-9 digit sets for the left and right digits.
b) that every left hand digit is paired once with every right hand digit .
.

Thanks David.

Your properties are essentially the definition of "Orthogonal Sudoku".

If we label the two Sudoku grids A and B (ie grid A = left digits, grid B = right digits), then we find that grid A has NTV = 243 , from which we can obtain 67,158 different orthogonal pairs (Grid B) one of which will (with suitable labelling) will match your example.

Given the high NTV count, I assume that grid A has automorphs. Can anyone confirm?

[Mathimagics]

You can see both grids belong to the same family of grids containing repeating minirows/minicolumns in each of the bands/stacks, but they are not equivalent to each other.

It is very surprising that the grid with maximum transversals and the grid with minimum transversals belongs to the same family of grids containing repeating minirows/minicolumns.

Interesting and surprising indeed!!

PS: I still don't have an automorph count/enum function. Can anyone help?