Transversals in Sudoku Squares

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

Re: Transversals in Sudoku Squares

Postby eleven » Sun Jan 07, 2018 4:20 pm

Code: Select all
136 452 978
452 897 136
897 361 452

245 789 361
613 245 897
978 136 245

524 978 613
789 613 524
361 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 987
425 879 163
879 316 425
          
631 254 879
254 798 316
987 163 254
          
316 542 798
542 987 631
798 631 542
eleven
 
Posts: 1816
Joined: 10 February 2008

Re: Transversals in Sudoku Squares

Postby eleven » Sun Jan 07, 2018 5:27 pm

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 123
231 486 957
579 123 648

486 957 312
123 648 795
957 312 864

648 795 231
312 864 579
795 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: 1816
Joined: 10 February 2008

Re: Transversals in Sudoku Squares

Postby Mathimagics » Sun Jan 07, 2018 5:35 pm

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! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 681
Joined: 27 May 2015

Re: Transversals in Sudoku Squares

Postby Mathimagics » Sun Jan 07, 2018 5:46 pm

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 = 243

Orthog  pairs  = 72024
SudokuP orthog = 46656

First 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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 681
Joined: 27 May 2015

Re: Transversals in Sudoku Squares

Postby eleven » Sun Jan 07, 2018 6:12 pm

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: 1816
Joined: 10 February 2008

Re: Transversals in Sudoku Squares

Postby David P Bird » Sun Jan 07, 2018 6:14 pm

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
.
[Edit] 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: 1026
Joined: 16 September 2008
Location: Middle England

Re: Transversals in Sudoku Squares

Postby Mathimagics » Sun Jan 07, 2018 7:30 pm

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 681
Joined: 27 May 2015

Re: Transversals in Sudoku Squares

Postby David P Bird » Sun Jan 07, 2018 8:43 pm

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

David
David P Bird
2010 Supporter
 
Posts: 1026
Joined: 16 September 2008
Location: Middle England

SudokuP - Frequency Anomaly

Postby Mathimagics » Sun Jan 07, 2018 9:07 pm

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! :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 681
Joined: 27 May 2015

Re: Transversals in Sudoku Squares

Postby Mathimagics » Sun Jan 07, 2018 9:14 pm

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 ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 681
Joined: 27 May 2015

Re: Transversals in Sudoku Squares

Postby Mathimagics » Sun Jan 07, 2018 9:21 pm

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 = 189

Orthog pairs = 67082
SudP   pairs = 53330

First 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

User avatar
Mathimagics
2017 Supporter
 
Posts: 681
Joined: 27 May 2015

Re: Transversals in Sudoku Squares

Postby eleven » Sun Jan 07, 2018 9:44 pm

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: 1816
Joined: 10 February 2008

Re: Transversals in Sudoku Squares

Postby David P Bird » Sun Jan 07, 2018 10:05 pm

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: 1026
Joined: 16 September 2008
Location: Middle England

Re: Transversals in Sudoku Squares

Postby Serg » Sun Jan 07, 2018 11:12 pm

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: 600
Joined: 01 June 2010
Location: Russia

Re: Transversals in Sudoku Squares

Postby Mathimagics » Sun Jan 07, 2018 11:23 pm

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!
User avatar
Mathimagics
2017 Supporter
 
Posts: 681
Joined: 27 May 2015

PreviousNext

Return to General