The New Sudoku Players' Forum

[JPF]

so here is the minimum min-lex 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 5 6
-------+-------+-------
 2 1 4 | 3 6 5 | 8 9 7
 3 6 5 | 8 9 7 | 2 1 4
 8 9 7 | 2 1 4 | 3 6 5
-------+-------+-------
 5 3 1 | 6 4 2 | 9 7 8
 6 4 2 | 9 7 8 | 5 3 1
 9 7 8 | 5 3 1 | 6 4 2

Thanks Red Ed.
This grid is automorphic without relabeling, again .

You were close, JPF!

Well...I wonder how many grids there are between these two grids.

JPF

[Red Ed]

The maximum min-lex grid is:

Code: Select all

123456789457893612986217354274538196531964827698721435342685971715349268869172543

This is the unique grid (up to isomorphism) in which all 6 chutes have the maximum band index, i.e. 416. The grid is 72-way automorphic. And you'll notice that its minimal form doesn't have r2c5,6 = 8,9 -- so that closes off the question about guaranteed digits in min-lex form, too.

I'm feeling better about this thread now!

[coloin]

Yes thats is the max
That has saved a lot of searching, any many of my assuptions were wrong !

All the bands are 416.......of course.......

These two grids have the same 6 bands........
They are either essentially the same grid or they are different.

Code: Select all

160 274 348  , 214 341 353   567812349892374156314965287136247598759638412248591673483756921625189734971423865
160 274 348  , 214 341 353   856197342214853769739264851625781493497532186381649275978326514162475938543918627


If its the latter then the coding isnt specific enough, I suspect this now.

However the first duplicate found [with the same index416] out of a million generated grids appeared at the 100,000 mark.
This gives an estimate of the number of essentially different grids as 5*10^9. Which is about right. So it might be OK ?

C

[JPF]

The maximum min-lex grid is:

Code: Select all

123456789457893612986217354274538196531964827698721435342685971715349268869172543

... And you'll notice that its minimal form doesn't have r2c5,6 = 8,9 -- so that closes off the question about guaranteed digits in min-lex form, too.

Impressive and quick work !
Well done.

JPF

[udosuk]

Right, so here is the minimum min-lex 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 5 6
-------+-------+-------
 2 1 4 | 3 6 5 | 8 9 7
 3 6 5 | 8 9 7 | 2 1 4
 8 9 7 | 2 1 4 | 3 6 5
-------+-------+-------
 5 3 1 | 6 4 2 | 9 7 8
 6 4 2 | 9 7 8 | 5 3 1
 9 7 8 | 5 3 1 | 6 4 2

Just a note that back in August 2005 this problem was already discussed in this thread...

But the max min-lex grid is surely a nice result!

[kjellfp]

I understand there is some interrest in the lexiographic order in my 416-grouping.

I'll see if I have time to give it this evening. At least, what I can say is that the order is not at all intuitive or canonical, it's merely a practical way of doing it for fast classifications.

IIRC, the first box is always

Code: Select all

123
456
789

[JPF]

You were close, JPF!

Well...I wonder how many grids there are between these two grids.

To answer to my own question the proposed grid was # 264 / 5472730538
but who cares

JPF

[coloin]

Welcome kjellfp

JPF - good calculation

before I get kjellfp to even think about his program and what it does and doesnt do ! I need to know if it can classify our min lex [all different] grids.....

There are 416 essentially different ways to portray a band

There are 6 bands therefore 416^6 = 5182746699759616

Dividing by 6^2 because of band swapping = 143965186104434

Still more than enough possibilities

But I dont think it is specific enough for our essentially different grids

take these two

Code: Select all

93 197 230  , 105 105 414   123456789457189263689237451298614375315798642746325198534861927872943516961572834
93 197 230  , 105 105 414   123456789457189263689237451298614375315798642746325198534872916861943527972561834


They have the same banding - there are no repeating minirows - but they have different unavoidables in the bottom horizintal band - therefore ? they are different.

So not looking good then
But it is a very fast program !

As it is it it works fine - "if the coding is different then the grids are definitely different"..... but the converse that "if the coding is the same the grids are possibly the same" only holds.



C

[JPF]

take these two

Code: Select all

93 197 230  , 105 105 414   123456789457189263689237451298614375315798642746325198534861927872943516961572834
93 197 230  , 105 105 414   123456789457189263689237451298614375315798642746325198534872916861943527972561834


They have the same banding - there are no repeating minirows - but they have different unavoidables in the bottom horizintal band - therefore ? they are different.

They are equivalent ...
min-lex representation :

Code: Select all

123456789457189263689237451294315678318764925765928134541872396832691547976543812

JPF

[coloin]

Well that is encouraging !

Do you think you could analyse a set of [ all different] min-lex grids [with clue 7 @r2c3]

run them with c:\index416.exe "file" 4 p>"fileindex"

Are there any duplicate 416codes in there ?

I use "boxer text editor" for this

Thanks

C

PS Red Ed nearly got it wrong !

[JPF]

Do you think you could analyse a set of min-lex grids [with clue 7 @r2c3]

I did it for 300000 min-lex different grids [with clue 7 @r2c3].
No duplicate 416 codes.

JPF

[coloin]

Thank you JPF, although there is still a lot of time for a counter example !

You could do it on your 4M file - ignore any repeating codes which contain a 1-31 band in them.

The fact that when I looked at my 1 million random grids file and only started getting duplicate index416 repeats at the 100,000 level made me hopeful.

Well done to kjellfp

And here is a clearer link - index416.exe

C

[Red Ed]

How about these:

Code: Select all

123456789457189236968372514219634857586927143734815962372541698645798321891263475
123456789457189236968372514219547368586213497734698125372865941645921873891734652
123456789457189236968372514215694378386527491794813625572941863649738152831265947
123456789457189236968372514291738465374265198685941327546813972732694851819527643
123456789457189236968372514215734968386921457794865123572698341649213875831547692


[kjellfp]

This is how I did the 416-grouping in Guenters program sudoku416:

I run through a subset of bands from which I know there will always be a representative for each class. The classes are named in the order their first element is found.

I restrict down to the following set of bands:

Code: Select all

123 ... ...
456 12x ...
789 ... 12y

On top level, I run through the choices for (x,y). First x=y=3, then x runs from 7 to 9 and y runs from 4 to 6.

With x and y, the elements in every minirow are given. I then run through the 6^4 different ways to permute the elements in the ...-minirows above. The minirows are handled in the following order:

First row 3, box 2
Then row 2, box 3
Then row 1, box 2
Then row 1, box 3

Just to make the mess complete, the permutations are done in the following order for each case:

123, 321, 312, 213, 231, 132

This is because I can then use the following simple code to run through all permutations:

Code: Select all

int permSet[3];  // Set to be permuted
#define SWAP(A,B) { int t=A; A=B; B=t; }

static void runThroughPermutations() {
  for (int i=0; i<6; i++) {
    <insert code to use for each permutation>

    // Permute
    SWAP (permSet[i%2], permSet[2]);
  }
}

The algorithm was one of my first contributions here. It was not meant to give an intuitive lexiographical ordering of the bands or the 416 classes, just to give them a unique index inside a program.

I see today ways to get the 416-index much faster.

If this is of any interrest, I had a program November 2005 that ran through all equivalence classes of Sudoku grids, when I confirmed the number 5472730538. One of the tools I used, was to get the 416-index of bands and stacks, as Guenters sudoku416-program does for a given list. I did indeed find several cases where essentially different Sudoku grids had the same 416-index tripple for bands and stacks.

[coloin]

Well, Red Ed's Grids all have an index416 of

Code: Select all

70  70  70  ,  70  70  70
70  70  70  ,  70  70  70
70  70  70  ,  70  70  70
70  70  70  ,  70  70  70
70  70  70  ,  70  70  70

and they are different grids.

I suppose it was inevitable that it would be this way.

Did you find them randomly or did you look at the grid solutions from a B1B2B3B4B7 [70,70] ?

No !..... they are 5 of a series of 9 grids which have the maximum possible number of 36 size 4 unavoidables - rare grids indeed !

Is the property pertaining to the 70 or because of the "isohex" banding

Other notable "isohex" grids are

Code: Select all

MC          - 1 1 1, 1 1 1
Maxminlex   - 416 416 416 , 416 416 416

The properties and puzzles of these grids is of course another thread.

As to the index416 program - its speed is already very impressive and its inner workings very clever.

If we could find out why some grids are arent uniquely represented by the coding then perhaps kjellfp might want to investigate.

Im tempted to say it would be useful to have an easy way to find out which grid is which.......
- actually the program is easily good enough !
- especially as JPF didnt get a duplicate code in 300,000 different grids

C