## Transversals in Sudoku Squares

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

### Re: Transversals in Sudoku Squares

Code: Select all
`136 452 978452 897 136897 361 452245 789 361613 245 897978 136 245524 978 613789 613 524361 524 789`

I am not sure, if it is always possible, but with a few column and row swaps the above puzzle can be made a sudokuP:
Code: Select all
`163 425 987425 879 163879 316 425           631 254 879254 798 316987 163 254           316 542 798542 987 631798 631 542`
eleven

Posts: 1907
Joined: 10 February 2008

### Re: Transversals in Sudoku Squares

This is a minirow puzzle with a 9-cycle in the columns too (825419637). Probably one in Mladens list (54 automorphisms).

Code: Select all
`864 579 123231 486 957579 123 648486 957 312123 648 795957 312 864648 795 231312 864 579795 231 486`

So you can also replace each digit by the next one in the sequence to get an orthogonal pair and another SudokuP.
eleven

Posts: 1907
Joined: 10 February 2008

### Re: Transversals in Sudoku Squares

eleven wrote:I am not sure, if it is always possible, but with a few column and row swaps the above puzzle can be made a sudokuP:

Interesting point!

Certainly permutations of whole bands preserve P property, whether T or F.

Permutations within a band will only preserve if same is applied to all 3 bands, I think.

That leaves permutations within a single band, these may or may not change P.

I suspect you are right, that any grid can be converted to SudokuP by combination of row/col permutations. Another question worthy of investigation!

Mathimagics
2017 Supporter

Posts: 761
Joined: 27 May 2015

### Re: Transversals in Sudoku Squares

Re: eleven's example above:

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

High automorphs => high NTV => high orthogonality, so it seems.

Mathimagics
2017 Supporter

Posts: 761
Joined: 27 May 2015

### Re: Transversals in Sudoku Squares

What about this one ? It has 36 automorphs, but i think, that the (2) sticks and diagonal symmetries do not help much for transversals (maybe the jumping rows and diagonal symmetries).
294371865361895274875264391752643918613958742948712653487126539136589427529437186
eleven

Posts: 1907
Joined: 10 February 2008

### Re: Transversals in Sudoku Squares

Hi Serg,
you wrote:Is "trellis set" a 9-cells subset of sudoku grid having each its cell located in the same position of corresponding box?

Not quite. The 9 member cells must be in different boxes, confined to 3 rows and 3 columns, and hold one of each digit.
This makes a trellis set a particular type of orthogonal transversal (oops) P-set if I have followed Mathimagics' posts correctly. Repeating his example grid, it contains the trellis sets shown.
Code: Select all
` *----------*----------*----------* | 1  2  3  | 4  5  6  | 7  8  9  |   Trellis sets | 6  4  8  | 9  7  3  | 1  2  5  |   r148c169,   r158c169,   r158c257,   r158c348,   r168c147,   r167c157, | 7  5  9  | 1  2  8  | 3  4  6  |   r248c248,   r247c357,   r259c249,   r269c169,    *----------*----------*----------*   r347c169,   r347c258,   r347c347,   r357c169,   r357c369,   r369c167,   r367c359 | 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  | *----------*----------*----------*`

[Added] Using by row and column swaps, a single trellis set can be transformed into a P-set, so that the member cells all occupy the same positions in each box.

Regarding names, this is such a niche area that whatever names are used, they are never likely to make it into a glossary of Sudoku terms outside this forum unless someone champions them by composing puzzle sets. If so, that champion needs to find a suitable name for marketing purposes and should be allowed to do so.

Personally, I would favour calling all grids with cells holding digit pairs where every pairing occurs once, an Afghan grid, as that was the brief I was trying to satisfy in 2007.
Where the grid is fully populated with trellis sets, it could then be qualified as being a Trellis Afghan grid.
I wouldn't want to use my name for anything I devise to stop Eleven from belittling it by calling it 'Bird-brained'

However, I don't want to 'ruffle any feathers' so I don't want to claim priority. My effort only lasted 2 or 3 days after all (but it's nice to get some appreciation for it after all this time). In fact, following this thread has been a mixture of Groundhog Day recalling what I did before, and backward engineering to fill in my memory gaps.

David
.
 Terminology brain warp corrected, with a further clarification added, following Mathimagics' correction in the next post.
Last edited by David P Bird on Sun Jan 07, 2018 8:38 pm, edited 1 time in total.
David P Bird
2010 Supporter

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

### Re: Transversals in Sudoku Squares

serg wrote:Is "trellis set" a 9-cells subset of sudoku grid having each its cell located in the same position of corresponding box?

That's the definition of P-set, A SudokuP has different values in every row, col, block, and P-set.

A trellis-set appears to be a more generalised form of P-set, with explicit requirement for different values in them.

Mathimagics
2017 Supporter

Posts: 761
Joined: 27 May 2015

### Re: Transversals in Sudoku Squares

Mathimagics,
Thanks for correcting my goof in my previous post which I have now corrected.

David
David P Bird
2010 Supporter

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

### SudokuP - Frequency Anomaly

Define p(P) as the probability of a random Sudoku grid having property P, ie SudokuP.

Define p(O) as the probability of a random Sudoku grid having property "Orthogonal pair" exists.

Define p(P=>O) as the probability of a random SudokuP grid having property "Orthogonal pair" exists (not necessarily an "Afghan" pair).

I think we can agree on the following, based on extensive random grid testing:

• p(P) is approx 1/33,000
• p(O) is approx 1/20,000

If these were independent properties, we would expect p(P=>O) to be roughly 1/20,000 also, but my random grid tester shows a definite trend towards p(P=>O) of 1/400, suggesting that SudokuP's are 50 times more likely to be orthogonal than Sudoku's.

It gets better! I happen to have a complete set of SudokuP's with the first horizontal band fixed at:
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`
.

Now this particular band is unusual in that it happens to produce a particularly large number of SudokuP solutions: 631,369,728. That's one in every 13 Sudoku grids for this band.

(Most band settings produce less, as little as 2,000 SudokuP solutions.)

Random sampling of these 631 million SudokoP's indicates that 1 in 36 are orthogonal. That's around 500 times more likely to be orthogonal than random standard Sudoku's!

Mathimagics
2017 Supporter

Posts: 761
Joined: 27 May 2015

### Re: Transversals in Sudoku Squares

David P Bird wrote:Mathimagics,
Thanks for correcting my goof in my previous post which I have now corrected.

David

You're very welcome!

How did you get that neat little edit marker to display? "†" does not display in my text editor when I paste it ...

Mathimagics
2017 Supporter

Posts: 761
Joined: 27 May 2015

### Re: Transversals in Sudoku Squares

eleven wrote:What about this one ? It has 36 automorphs, but i think, that the (2) sticks and diagonal symmetries do not help much for transversals (maybe the jumping rows and diagonal symmetries).
294371865361895274875264391752643918613958742948712653487126539136589427529437186

Sorry, mate, I overlooked your post.

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

Mathimagics
2017 Supporter

Posts: 761
Joined: 27 May 2015

### Re: Transversals in Sudoku Squares

Ah thanks, much more than i had expected.

For comparison: There are 557205 grids with automorphism, which gives a rate of about 1:9821.
I saw that orthogonal grids don't need to be automorphs of the original grids. So the correlation is just, that the probability to have orthogonals is much higher for automorph grids (and those with minirow and full row symmetry definitely have an orthogonal pair [Added:] there are 8727 grids with 3 or 9-cycles).
Last edited by eleven on Sun Jan 07, 2018 10:20 pm, edited 1 time in total.
eleven

Posts: 1907
Joined: 10 February 2008

### Re: Transversals in Sudoku Squares

Matimagics wrote:How did you get that neat little edit marker to display? "†" does not display in my text editor when I paste it ...

That's strange! I use either notepad or MS Word 2010 and the dagger mark † pastes correctly into the forum's reply window.

However I used strikethrough on my blunder and was annoyed when that didn't paste. Then in composing this response, I forgot remembered, that to get strikethrough we must use an obscure bbcode {s} & {/s} (using square brackets of course).
David P Bird
2010 Supporter

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

### Re: Transversals in Sudoku Squares

Hi, David!
David P Bird wrote:
you wrote:Is "trellis set" a 9-cells subset of sudoku grid having each its cell located in the same position of corresponding box?

Not quite. The 9 member cells must be in different boxes, confined to 3 rows and 3 columns, and hold one of each digit.

Thanks for clarification! I see that "trellis set" and "P-set" is not the same. Moreover, neither of these objects is particular case of another.

Definition 1
Trellis set is 9-cells subset of sudoku grid, located at possible crossings of 3 reference rows and 3 reference columns, chosen in such way that each band contains 1 reference row exactly and each stack contains 1 reference column exactly. Trellis set's cells contain all different digits 1-9.

Definition 2
P-set is 9-cells subset of sudoku grid, each cell of which is located in the same position in the separate box.

So, you can see, that trellis set must contain all different digits 1-9, but P-set may contain repeating digits. P-set's cell positions in corresponding boxes must be the same, but trellis set's cell position in corresponding boxes may differ.
"SudokuP" contains either 9 P-sets containing different digits (particular case of P-sets) or 9 trellis sets which cells are located in the same positions of its boxes (particular case of trellis sets).

Mathemagics, is it possible to rename "SudokuP" to "P-Sudoku"? I think, it is more convenient - it would be possible to write this term in plural form and relation between "P-set" and "P-Sudoku" will be more evident.

Serg
Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: Transversals in Sudoku Squares

In response to eleven's question about whether a non-P grid can be made into a SudokuP grid by row/col permutations, I think this one shows this is not always the case:

Code: Select all
` 2 1 4 | 9 5 8 | 6 7 3 3 7 9 | 4 6 1 | 2 8 5 6 5 8 | 7 3 2 | 4 9 1 --------------------- 9 3 2 | 1 4 7 | 5 6 8 5 4 6 | 8 9 3 | 1 2 7 1 8 7 | 6 2 5 | 9 3 4 --------------------- 4 6 3 | 5 8 9 | 7 1 2 8 9 1 | 2 7 4 | 3 5 6 7 2 5 | 3 1 6 | 8 4 9`

This needs some independent verification, if possible. I believe the number of relevant transformations is 6^6 (46656), based on the following reasoning:

• all rotations, transpositions, reflections, etc preserve Pset composition
• same for all permutations of bands, horizontal or vertical
• that just leaves row/col permutations within a band

I'm pretty sure I tested all combinations, and I hope I'm wrong, it would be nice if it were always possible!

Mathimagics
2017 Supporter

Posts: 761
Joined: 27 May 2015

PreviousNext