## Canonical Form

Everything about Sudoku that doesn't fit in one of the other sections
gsf wrote:we're using different parts of the grid in the inner loop
you: b1b2b3b4b7, me: b1b2b3b4b5b6

It seems both have their advantages.

I think my algorithm is faster. I might have fewer loops, and use the benifit of having fast lookup listings to get all bands from a configuration (but then, you might also have some fast lookup tricks in your search that I don't know about).

On the other hand, your code gets the min-lex grid for each class, I don't.

Also, great to see how others attack this problem about visiting every class. And to see the number of classes with diferent automorphism class size confirmed.
kjellfp

Posts: 140
Joined: 04 October 2005

kjellfp wrote:
gsf wrote:we're using different parts of the grid in the inner loop
you: b1b2b3b4b7, me: b1b2b3b4b5b6

It seems both have their advantages.

my guess is the minlex method produces too many grids to be checked (for new class members)
having both is good for confirmation and also for weeding out what's really going on with all those sudoku bits
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

I just read through this thread again, and I can't say I got the conclusion of "how many digits can we fix that all solutiongrids can be derived from"

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

Does this mean that this is the right answer, or do the 2 in r4c1 have to go to?
Code: Select all
`123|456|789 45.|...|... ...|...|... ---+---+--- 2..|...|... ...|...|... ...|...|... ---+---+--- ...|...|... ...|...|... ...|...|...`

any proofs / disproofs on that little 2?

Havard
Havard

Posts: 377
Joined: 25 December 2005

The 2 gets to stay. See http://forum.enjoysudoku.com/viewtopic.php?p=40791#p40791 for a simple proof.
Mike Barker

Posts: 458
Joined: 22 January 2006

Mike Barker wrote:The 2 gets to stay. See http://forum.enjoysudoku.com/viewtopic.php?p=40791#p40791 for a simple proof.

But that proof also has 100% for r2c5=8 and r2c6=9. Is the proof wrong for those two digits?
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Mike Barker wrote:Coloin, nice observation about r4c1=2. It will always be that way because r1c2=2 therefore there must be a 2 in r4-9c1. The only constraints on the orders of these rows will be to maintain the smallest lexicographic value so the row containing the 2 in column 1 will become row 4.

I think this is the proof Mike was referring to. Makes sense to me!

Havard
Havard

Posts: 377
Joined: 25 December 2005

### Re:

gsf wrote:
gsf wrote:the number of automorphisms for any grid is in the range 1..648 inclusive
do we know the impossible ones (number of automorphisms) in that range?

here is a table of #autmorphisms and #essentially-different-grids with that number of automorphisms
Code: Select all
`   1 5472170387   2     548449   3       7336   4       2826   6       1257   8         29   9         42  12         92  18         85  27          2  36         15  54         11  72          2 108          3 162          1 648          1`

Hello gsf,

Do you know why the numbers 24, 81, 261 and 324 are out of the range in the list?
Maq777

Posts: 4
Joined: 30 April 2016

### Re:

gsf wrote:
RW wrote:
gsf wrote:here is a table of #autmorphisms and #essentially-different-grids with that number of automorphisms

Nice! That confirms the number 6670903752021072936960 once again. Could you possibly post the grids from 27 up? Actually, maybe there should be an own thread for "the catalogue". I suspect this is otherwise going to drift very much off topic.

here are the 27 and up grids with #automorphisms, band, and minlex index

123456789456789123789123456231564897564897231897231564312645978645978312978312645 # 648 001 964550
123456789456789123789123456231564897564897231897231564312978645645312978978645312 # 108 001 964558
123456789456789123789123456231564897564897231897231564348672915672915348915348672 # 54 001 964568
123456789456789123789123456231564897564897231897231564348915672672348915915672348 # 54 001 964569
123456789456789123789123456231564897564897231978312645312645978645978312897231564 # 36 001 964589
123456789456789123789123456231564978564897312897231645312978564645312897978645231 # 72 001 965096
123456789456789123789123456231564978564978231978231564312645897645897312897312645 # 108 001 965174
123456789456789123789123456231564978564978231978231564312897645645312897897645312 # 36 001 965182
123456789456789123789123456231564978645897231897312564312645897564978312978231645 # 36 001 966422
123456789456789123789123456231597864597864231864231597312678945678945312945312678 # 36 001 985543
123456789456789123789123456231597864597864231864231597312948675675312948948675312 # 36 001 985544
123456789456789123789123456231678945678945231945231678312597864597864312864312597 # 36 001 989378
123456789456789123789123456231678945678945231945231678312894567567312894894567312 # 36 001 989379
123456789456789123789123456231897564564231897897564231348672915672915348915348672 # 27 001 989400
123456789456789123789123456231897564564231897978645312312978645645312978897564231 # 36 001 989404
123456789456789123789123456231897645564312897978564231312978564645231978897645312 # 36 001 989622
123456789456789123789123456234567891567891234891234567318642975642975318975318642 # 54 001 992761
123456789456789123789123456234567891567891234891234567345678912678912345912345678 # 54 001 992769
123456789456789123789123456234567891567891234891234567372615948615948372948372615 # 54 001 992773
123456789456789123789123456235964817817235964964817235392641578578392641641578392 # 54 001 1006748
123456789456789123789123456267591348591834672834267915375618294618942537942375861 # 54 001 1007164
123456789456789123789123456267591834591834267834267591375618942618942375942375618 # 162 001 1007168

Hello GSF,

You have some examples like:
123456789456789123789123456231564897564897231897231564312645978645978312978312645 # 648 001 964550
123456789456789123789123456267591834591834267834267591375618942618942375942375618 # 162 001 1007168
123456789456789123789123456231564897564897231897231564312978645645312978978645312 # 108 001 964558
123456789456789123789123456231564978564897312897231645312978564645312897978645231 # 72 001 965096
123456789456789123789123456231564897564897231897231564348915672672348915915672348 # 54 001 964569
123456789456789123789123456231564897564897231978312645312645978645978312897231564 # 36 001 964589
123456789456789123789123456231897564564231897897564231348672915672915348915348672 # 27 001 989400

Do you have examples for all of this cases ?
#324, #216, #81, #24, #18, #12, #9, #8, #6, #4, #3, #2, #1,

Thank you
Maq777

Posts: 4
Joined: 30 April 2016

### Re: Re:

Hi, Maq777!
Maq777 wrote:Hello GSF,

You have some examples like:
123456789456789123789123456231564897564897231897231564312645978645978312978312645 # 648 001 964550
123456789456789123789123456267591834591834267834267591375618942618942375942375618 # 162 001 1007168
123456789456789123789123456231564897564897231897231564312978645645312978978645312 # 108 001 964558
123456789456789123789123456231564978564897312897231645312978564645312897978645231 # 72 001 965096
123456789456789123789123456231564897564897231897231564348915672672348915915672348 # 54 001 964569
123456789456789123789123456231564897564897231978312645312645978645978312897231564 # 36 001 964589
123456789456789123789123456231897564564231897897564231348672915672915348915348672 # 27 001 989400

Do you have examples for all of this cases ?
#324, #216, #81, #24, #18, #12, #9, #8, #6, #4, #3, #2, #1,

Thank you

gsf didn't visit this forum for several years.

Your former question "Do you know why the numbers 24, 81, 261 and 324 are out of the range in the list?" ("261" is a typo, must be "216") is very complicated. Maybe you should ask StackOverflow about it. But I doubt that anyone knows it.

About examples you need. You can see in gsf's list that sudoku grids having 324 or 216 or 81 or 24 automorphisms exactly are absent. So, what examples for cases #324, #216, #81, #24 do you want to see? That list shows that almost always sudoku grid has the only automorphism ("Do nothing"). So, one can easy find an example for "#1" - take solution grid of any sudoku. It will be an example for "#1" with 99.99% probability. It's not easy to find examples for other cases.

Serg
Serg
2018 Supporter

Posts: 662
Joined: 01 June 2010
Location: Russia

### Re: Canonical Form

You can find examples of grids with 2,3,4,6,8,9,12 and 18 (or more) automorphisms in this post (and others), under the topic: About Red Ed's Sudoku symmetry group. Group theory aficionados, might like this listing, on the next page.
blue

Posts: 894
Joined: 11 March 2013

### Re: Canonical Form

Serg, Blue.

Thanks for notifying me that gsf is no longer responding in the forum

#261 was my mistake, it must have been #216.

The thing is, I'm designing programs to check. Using these programs I'm sure the examples are correct.

I think we do not find cases #324, #216, #81, #24, because they do not exist. I can not find a logical explanation for this. I thought that in the forum someone had already solved this question, but as you say is complicated to explain.

Thanks for the links were very useful.