## Transversals in Sudoku Squares

Everything about Sudoku that doesn't fit in one of the other sections

### Transversals in Sudoku Squares

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
2017 Supporter

Posts: 1480
Joined: 27 May 2015
Location: Canberra

### Transversals in Sudoku Squares - Extremes

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
2017 Supporter

Posts: 1480
Joined: 27 May 2015
Location: Canberra

### Orthogonality - Minimum Transversals

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`

Mathimagics
2017 Supporter

Posts: 1480
Joined: 27 May 2015
Location: Canberra

### Re: Transversals in Sudoku Squares

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.
Last edited by StrmCkr on Wed Jan 03, 2018 1:44 am, edited 2 times in total.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1085
Joined: 05 September 2006

### Re: Transversals in Sudoku Squares

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?

Mathimagics
2017 Supporter

Posts: 1480
Joined: 27 May 2015
Location: Canberra

### Re: Transversals in Sudoku Squares

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 964550123456789456789123789123456231564897564897231897231564312978645645312978978645312 # 108 001 964558123456789456789123789123456231564897564897231897231564348672915672915348915348672 # 54 001 964568123456789456789123789123456231564897564897231897231564348915672672348915915672348 # 54 001 964569123456789456789123789123456231564897564897231978312645312645978645978312897231564 # 36 001 964589123456789456789123789123456231564978564897312897231645312978564645312897978645231 # 72 001 965096123456789456789123789123456231564978564978231978231564312645897645897312897312645 # 108 001 965174123456789456789123789123456231564978564978231978231564312897645645312897897645312 # 36 001 965182123456789456789123789123456231564978645897231897312564312645897564978312978231645 # 36 001 966422123456789456789123789123456231597864597864231864231597312678945678945312945312678 # 36 001 985543123456789456789123789123456231597864597864231864231597312948675675312948948675312 # 36 001 985544123456789456789123789123456231678945678945231945231678312597864597864312864312597 # 36 001 989378123456789456789123789123456231678945678945231945231678312894567567312894894567312 # 36 001 989379123456789456789123789123456231897564564231897897564231348672915672915348915348672 # 27 001 989400123456789456789123789123456231897564564231897978645312312978645645312978897564231 # 36 001 989404123456789456789123789123456231897645564312897978564231312978564645231978897645312 # 36 001 989622123456789456789123789123456234567891567891234891234567318642975642975318975318642 # 54 001 992761123456789456789123789123456234567891567891234891234567345678912678912345912345678 # 54 001 992769123456789456789123789123456234567891567891234891234567372615948615948372948372615 # 54 001 992773123456789456789123789123456235964817817235964964817235392641578578392641641578392 # 54 001 1006748123456789456789123789123456267591348591834672834267915375618294618942537942375861 # 54 001 1007164123456789456789123789123456267591834591834267834267591375618942618942375942375618 # 162 001 1007168123456789456789123789123456267591834591834267834267591375942618618375942942618375 # 54 001 1007169123456789456789123789132465231564978564978231978213546312645897645897312897321654 # 36 004 50092115123456789456789123798132465231564897564897231879213546312645978645978312987321654 # 36 009 224283635123456789456789123897231564231564978564978231789312645312645897645897312978123456 # 54 016 473714886123456789456789231789123645231564897564897312897231456375618924618942573942375168 # 36 027 1012364857123456789456789231789123645231564978564897123897231564375942816618375492942618357 # 36 027 1012366524123456789456789231789312456231564978564978312978123564312645897645897123897231645 # 27 030 1061944621123456789456789231789312456231645978645978312978123645312564897564897123897231564 # 54 030 1062073983123456789457189236968372514291738465374265198685941327546813972732694851819527643 # 36 133 4869572229123456789457189326869372514214965873635847192978213465381624957546798231792531648 # 36 240 5449015463123456789457289163689173452235964817816735924974812635392641578568397241741528396 # 54 348 5472677656123456789457289163689173452245968317316745928978312645564897231731524896892631574 # 108 348 5472677695123456789457893612986217354274538196531964827698721435342685971715349268869172543 # 72 416 5472730538`
dobrichev
2016 Supporter

Posts: 1777
Joined: 24 May 2010

### Re: Transversals in Sudoku Squares

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

Proven to have been wrong
Last edited by eleven on Tue Jan 02, 2018 1:57 pm, edited 2 times in total.
eleven

Posts: 2241
Joined: 10 February 2008

### Re: Transversals in Sudoku Squares

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.

Mathimagics
2017 Supporter

Posts: 1480
Joined: 27 May 2015
Location: Canberra

### Re: Transversals in Sudoku Squares

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
.
David P Bird
2010 Supporter

Posts: 1042
Joined: 16 September 2008
Location: Middle England

### Re: Transversals in Sudoku Squares

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 789456 789 123789 123 456234 567 891567 891 234891 234 567345 678 912678 912 345912 345 678`

Hidden Text: Show
Code: Select all
`1*2°3- 4'5"6& 7#8!94&5'6" 7 8#9! 1-2*3°    123 456 7897!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 1268"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 3459'1"2& 3#4!5  6°7-8*`
eleven

Posts: 2241
Joined: 10 February 2008

### Re: Transversals in Sudoku Squares

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
2018 Supporter

Posts: 690
Joined: 01 June 2010
Location: Russia

### Re: Transversals in Sudoku Squares

Hi, StrmCkr!
StrmCkr wrote:
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.]
Last edited by Serg on Wed Jan 03, 2018 4:12 pm, edited 1 time in total.
Serg
2018 Supporter

Posts: 690
Joined: 01 June 2010
Location: Russia

### Re: Transversals in Sudoku Squares

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.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1085
Joined: 05 September 2006

### Re: Transversals in Sudoku Squares

David P Bird wrote:
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
2017 Supporter

Posts: 1480
Joined: 27 May 2015
Location: Canberra

### Re: Transversals in Sudoku Squares

Serg wrote: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?

Mathimagics
2017 Supporter

Posts: 1480
Joined: 27 May 2015
Location: Canberra

Next