The New Sudoku Players' Forum

[eleven]

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]

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.

[Mathimagics]

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]

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.

[eleven]

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

[David P Bird]

Hi Serg,

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.

[Mathimagics]

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.

[David P Bird]

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

David

[Mathimagics]

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]

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]

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



[eleven]

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).

[David P Bird]

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).

[Serg]

Hi, David!

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

[Mathimagics]

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!