Canonical Form

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

Postby JPF » Sun Jan 28, 2007 5:38 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Red Ed » Sun Jan 28, 2007 6:27 pm

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!:D
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby coloin » Sun Jan 28, 2007 6:55 pm

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
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby JPF » Sun Jan 28, 2007 7:07 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby udosuk » Mon Jan 29, 2007 3:18 am

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

Postby kjellfp » Mon Jan 29, 2007 2:15 pm

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
kjellfp
 
Posts: 140
Joined: 04 October 2005

Postby JPF » Mon Jan 29, 2007 6:15 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Mon Jan 29, 2007 6:56 pm

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
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby JPF » Mon Jan 29, 2007 10:41 pm

coloin wrote: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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Mon Jan 29, 2007 11:05 pm

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: 1638
Joined: 05 May 2005

Postby JPF » Mon Jan 29, 2007 11:13 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Mon Jan 29, 2007 11:24 pm

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: 1638
Joined: 05 May 2005

Postby Red Ed » Tue Jan 30, 2007 7:56 am

How about these:
Code: Select all
123456789457189236968372514219634857586927143734815962372541698645798321891263475
123456789457189236968372514219547368586213497734698125372865941645921873891734652
123456789457189236968372514215694378386527491794813625572941863649738152831265947
123456789457189236968372514291738465374265198685941327546813972732694851819527643
123456789457189236968372514215734968386921457794865123572698341649213875831547692
:?:
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby kjellfp » Tue Jan 30, 2007 10:11 am

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

Postby coloin » Tue Jan 30, 2007 8:37 pm

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
coloin
 
Posts: 1638
Joined: 05 May 2005

PreviousNext

Return to General