## Canonical Form

Everything about Sudoku that doesn't fit in one of the other sections
Red Ed wrote: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 .

Red Ed wrote:You were close, JPF!

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

JPF
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

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.

Red Ed

Posts: 633
Joined: 06 June 2005

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   567812349892374156314965287136247598759638412248591673483756921625189734971423865160 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
coloin

Posts: 1790
Joined: 05 May 2005

Red Ed wrote: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
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

Red Ed wrote: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!
udosuk

Posts: 2698
Joined: 17 July 2005

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
`123456789`
kjellfp

Posts: 140
Joined: 04 October 2005

JPF wrote:
Red Ed wrote: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
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

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   12345678945718926368923745129861437531579864274632519853486192787294351696157283493 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
coloin

Posts: 1790
Joined: 05 May 2005

coloin wrote:take these two
Code: Select all
`93 197 230  , 105 105 414   12345678945718926368923745129861437531579864274632519853486192787294351696157283493 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
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

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 !
Last edited by coloin on Mon Jan 29, 2007 7:16 pm, edited 1 time in total.
coloin

Posts: 1790
Joined: 05 May 2005

coloin wrote: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
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

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
coloin

Posts: 1790
Joined: 05 May 2005

Code: Select all
`123456789457189236968372514219634857586927143734815962372541698645798321891263475123456789457189236968372514219547368586213497734698125372865941645921873891734652123456789457189236968372514215694378386527491794813625572941863649738152831265947123456789457189236968372514291738465374265198685941327546813972732694851819527643123456789457189236968372514215734968386921457794865123572698341649213875831547692`
Red Ed

Posts: 633
Joined: 06 June 2005

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

Posts: 140
Joined: 04 October 2005

Well, Red Ed's Grids all have an index416 of
Code: Select all
`70  70  70  ,  70  70  7070  70  70  ,  70  70  7070  70  70  ,  70  70  7070  70  70  ,  70  70  7070  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 1Maxminlex   - 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
coloin

Posts: 1790
Joined: 05 May 2005

PreviousNext