The New Sudoku Players' Forum

[Serg]

Hi, Mathimagics!

Nice work, mate!

Thanks!

You might have missed the fact (noted in earlier posts in this thread) that we now know that min NTV = 0 (we found a grid with NO transversals), and max NTV = 279 (which occurs in the most canonical, aka {MC} grid).

I wrote about my limits for minimal and maximal number of transversals to show - how far my search results were from known limits (i.e. it's no reason for me to do new random search). NTV = 0 is true minimal number of transversals, but why are you sure that NTV = 279 is maximal number of transversals? Certainly, it can be true, but nobody proves this statement.

I can also report that my search now has identified the new record low NTV for orthogonal grids as 15. That search has been running for several days and tested 1.5 billion grids so far.

Congratulations! Your search is very fast.

Can you describe your method for "Bird's orthogonal grids" search? (aka "Orthog SudokuP", or just "OrthogP")
I presume your 1 in 1,000,000 figure means the chances of a grid being SudokuP and having an orthog pair which is also SudokuP ...

I am not sure my understanding is right...
For given (randomly generated) sudoku solution grid I am searching for "Bird's transversals", i.e. 9-cells sets, containing different digits (1-9) such, that each cell is located in separate row, in separate column, in separate box and in separate "P-set" (aka "Bird's transversal").
Then I check found "Bird's transversals" for compatibility and register each set, containing 9 pairwise compatible "Bird's transversals", as solution (i.e. "Bird's Design"). Sudoku solution grid producing at least one "Bird's Design" is counted as "Bird's Design base solution grid" or "Bird's orthogonal grid". So, I found 86 "Bird's Design base solution grids" after scanning 10^8 random grids.

Serg

[Edited. I deleted my wrong example of "Bird's Design" containing no repeating triples. Error was caused by a bug in my searching program. Thanks to Mathimagics, who found an error in my example.]

[Mathimagics]

Hi Serg,

Code: Select all

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


Your left side grid is not SudokuP. Same value in (1, 4) and (4,1).

David Bird's construction is a pair of orthogonal grids, both of which are SudokuP.

You need to start with a single SudokuP grid (A), then check it's traversals for orthog pairs B, then test each B to see if any are also SudokuP.

[Mathimagics]

NTV = 0 is true minimal number of transversals, but why are you sure that NTV = 279 is maximal number of transversals? Certainly, it can be true, but nobody proves this statement.

A very good point!

It is true that 279 is the maximal so far, and we think it might be a true maximum only because of our conjecture that more automorphs seems to give more NTV. Also I ran random search for many days and never got NT > 159, but tested some of the high automorph cases (posted above in this thread), and all the ones I tested had NTV > 200.

But it remains conjectural ... I've been working on the SudokuP enumeration problem so haven't done any transversal count testing recently

I can, however, tell you that David Bird's example is quite remarkable:

• the left side (GridA) has NTV = 243, from which we can derive 67,158 orthog GridB's

• 49,644 of those GridB's are SudokuP

• so, from that single GridA we have an extended family of 6,537,215,965,593,600 "Bird Designs" (Orthog SudokuP pairs), since relabelling possibilities are 49,644 x 362,880 x 362,880.

[David P Bird]

Serg, Mathimagics,
My memory is rather vague about the intricacies of my search method of 2007 but the basic method involved setting digits to repeat in mini-lines in different diagonal directions for each tier and stack in as orderly way as possible. I picked up the grid I posted earlier in this thread from some jottings I made at the time, but it is not the one I presented. Later I found that I had posted that one earlier in this forum <here>.

Here they are both again

Code: Select all

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

In the margins I have added the diagonal directions the digits follow in the band mini-lines
Set A (the left digits) are above and to the left and the B set is to the right and bottom.
This shows each digit travels as a singleton once and in a pair twice in each orthogonal direction .
As I mentioned earlier, this is what I was striving to find as it contains no repeating triplets.

Code: Select all

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

This earlier trial has the weakness of repeating triplets in the tiers.
Also, the central box cells contained all the instances where the two colours would be the same.

Setting the repeat directions for the digits by manual trial and error, I seem to remember it took me two or three days.
Perhaps this might give you ideas about alternative search techniques.

David
.

[Serg]

Hi, Mathemagics!

Hi Serg,

Code: Select all

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


Your left side grid is not SudokuP. Same value in (1, 4) and (4,1).

You are right. This example is not "Bird's Design". I've corrected my post, thank you for cross-checking my result.

David Bird's construction is a pair of orthogonal grids, both of which are SudokuP.
You need to start with a single SudokuP grid (A), then check it's traversals for orthog pairs B, then test each B to see if any are also SudokuP.

Yes, now my program runs as follows.

1. A sudoku solution grid is randomly generated.
2. Generated grid is checked - is it "Bird's sudoku solution grid" (all rows, columns, boxes and P-sets don't contain repeating digits).
3. If generated grid is "Bird's sudoku solution grid", all traversals (concerning rows, columns, boxes and P-sets) are found.
4. All possible combinations of found transversals are checked to get 9 pairwise compatible transversals. Each found combination of 9 transversal is counted as solution for given generated grid. A "Bird's Design" can be built for every solution.

Well, I fixed a bug caused wrong example you pointed at, and got following results.
3 sudoku grids only from 100000 generated random sudoku grids had correct all P-sets (without repeating digits), i.e. were "Bird's sudoku solution grids". Then I got 191 grids, forming "Bird's Design", from 100000 "Bird's sudoku solution grids". So, 3.3 x 10^9 random sudoku grids produced 191 "base" solution grids, forming "Bird's Designs". Ratio 1 : 1.5 x 10^7. Those 191 grids were generated during 29 minutes, 6.5 grids per minute. Here is an example.

Code: Select all

An example - base solution grid producing "Bird's Design"

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

The same solution grid in the line form: 371254698294678351865193274139742865427865139658319427983427516512986743746531982

One of 20 produced "Bird's Designs"

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

Unfortunately, I couldn't find yet solution grid, producing "Bird's Designs" without repeating triples (David gave an example of such grid).

Serg

[Serg]

Hi, Mathemagics!
Tarek was so kind that send me instruction - how to run gsf's sudoku tool for calculation of sudoku solution grid's automorphisms. You should execute "sudoku" utility from command line:

sudoku -f%#aC <input_file >output_file

utility calculates numbers of grids' automorphisms and writes those numbers to output file.
I checked this this feature for multiautomorphism grids posted by Mladen Dobrichev - results coinside for all grids.
(If you will use this command line in Windows command file, you should replace "%" by "%%".)

Serg

[Mathimagics]

This earlier trial has the weakness of repeating triplets in the tiers.
Also, the central box cells contained all the instances where the two colours would be the same.

You can relabel either Grid A (the left hand digits) or GridB (the right hand digits) and still preserve the essential properties of the design. Relabel means apply a permutation.

For example you don't like the center block in your example:

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


So we choose a random permutation, say 485769321, and apply to grid A (ie map 1 to 4, 2 to 8, etc) and that problem disappears:

Code: Select all

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


From a mathematical perspective, you can apply any of 362880 permutations to A and/or B and the grid will still have the same design properties (ie: A and B both SudokuP, A and B orthogonal, ie every pair AB is different). That's how I arrived at the huge "family size" number given above.

Setting the repeat directions for the digits by manual trial and error, I seem to remember it took me two or three days.
Perhaps this might give you ideas about alternative search techniques.

I don't really understand your construction method, I am not fluent in Sudoku solution terminology, (only the mathematical aspects of complete grids). We do have a strange property of individual SudokuP grids (see "SudokuP Frequency Anomaly" thread) where the counting the number of SudokuP grids (ie:individual Sudoku grids with property P = all corresponding Positions have different values) gives wildly different counts according to Band 1 settings.

Maybe your construction method will yield some clue to this.

Cheers

[Mathimagics]

Hi serg!

Can you point me to where gsf sudoku tool can be obtained? A search for "gsf" and "sudoku" show many thousands of posts ...

3 sudoku grids only from 100000 generated random sudoku grids had correct all P-sets (without repeating digits), i.e. were "Bird's sudoku solution grids". Then I got 191 grids, forming "Bird's Design", from 100000 "Bird's sudoku solution grids". So, 3.3 x 10^9 random sudoku grids produced 191 "base" solution grids, forming "Bird's Designs". Ratio 1 : 1.5 x 10^7. Those 191 grids were generated during 29 minutes, 6.5 grids per minute.

So roughly one in 30,000 Sudoku grids are SudokuP. This agrees with my random grid results (and confirms your conjecture that SudukoP are less likely than SudokuOrthog).

Note that I have discovered that fixing Band 1 (or say, Row 1 + Col 1) can give wildly different results (see my "SudokuP Frequency Anomaly" thread).

That's why I was getting rates of 1 in 15 for enumerated grids, a contradiction you correctly identified!

[Serg]

Hi, Mathimagics!

Can you point me to where gsf sudoku tool can be obtained? A search for "gsf" and "sudoku" show many thousands of posts ...

I used link https://sites.google.com/a/cococlyde.org/gsf/download/sudoku to download binary executable "sudoku.exe". (I think, this is 32-bit binary executable.) It works fine in my Windows XP environment. Antivirus permitted downloading and execution of this program.

Serg

[Mathimagics]

got it! Spasiba ....

[David P Bird]

Mathimagics,
To elaborate on the jargon I used in my description,

A Sudoku 'line' is a row or column, which is divided into three 'mini-lines' (either a mini-row or a mini-column) as it intersects the boxes it crosses.
The Sudoku grid consists of 3 'bands' of boxes in the vertical and horizontal directions.
I call the horizontal bands 'tiers' and the vertical ones 'stacks' but other writers have different terms.

The three instances of a digit in a band will be contained in a diagonal of three mini-lines (which may wrap round) either in the / or \ directions.
The diagonal directions followed by three digits occupying any mini-line in a band of boxes will be split in a constant way throughout the band and will either be triples all following the same diagonal (aka a 'rope' pattern) or pairs and singles following opposite diagonals (aka a 'braid' pattern).
The diagrams in my last post show the patterns followed in each band in the margins.

My approach permutated the diagonal directions followed by each digit in the tiers and stacks from which the grid can be derived.
There is a simple rule that if two digits share a mini-line diagonal in a tier, they cannot share one in the stacks, and vice versa.
To ensure this rule was never broken, I used digit sets (123) (456) (789) in one direction and (147) (258) (369) in the other and making pairs and singles from them in each band .
Once I had worked all this out, it considerably reduced the search space to explore.

David
.

[Mathimagics]

got it! Ta muchly ...

[Serg]

Hi, David!
Thank you for 2 examples of "Afghan design" and for description of your method.

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

It's necessary to call your design, containing pairs of digits. I see possible variants - "Bird's design" or "Afghan design". Do you mind calling it as "Bird's design"? In this case, at least, it will be clear - who is the author of this construction. Anyway you have priority for naming this construction.

It's necessary to call sudoku solution grid with all correct P-sets (or "trellis sets"). Mathemagics proposes name "SudokuP", but to me it isn't the best possible variant. (What can one say this term in plural?)

Serg

[eleven]

From the symmetries point of view David's example has a minirow symmetry, i.e. if you cycle the columns in the stacks (c1->c2->c3->c1, c4->c5->c6->c4, c7->c8->c9->c7 etc), the digits always change in the same way.
E.g. in this puzzle you get the number cycles 136, 245 and 789. Now you can replace the digits of one cycle by the next (136)-> (245) etc. and you will have a orthogonal pair. If the original puzzle has the PSudoku property, it will be preserved.
(Minirow puzzles can be easily generated. For each digit you try to add, enter 2 more from it's cycle).

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

[Mathimagics]

Serg,

You must have missed my post above where I explained why "Mathimagics" is spelled the way it is!

SudokuP seems ok to me, and I am sure David would agree. "Bird's Design" is novel, but it is still mathematically just a pair of orthogonal SudokuP's. Since "Orthogonal Sudoku" seems to be the prevailing term for standard Sudoku's, that would suggest "Orthogonal SudokuP" as a natural choice.

I would be first to agree and acknowledge David's undisputed right to be identified as the first person to think of this Sudoku variant (well played, David!).