Canonical Form

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

Postby kjellfp » Wed Feb 21, 2007 9:55 pm

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

Postby gsf » Thu Feb 22, 2007 12:24 am

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

Postby Havard » Fri May 04, 2007 11:42 pm

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.

I'm feeling better about this thread now!:D

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

Postby Mike Barker » Sat May 05, 2007 12:29 am

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

Postby ronk » Sat May 05, 2007 4:39 am

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

Postby Havard » Sat May 05, 2007 8:42 am

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:

Postby Maq777 » Sun May 01, 2016 6:34 pm

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?

having the catalog in hand is ... handy
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:

Postby Maq777 » Sun Nov 20, 2016 3:09 pm

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:

Postby Serg » Sun Nov 20, 2016 7:59 pm

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
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Canonical Form

Postby blue » Mon Nov 21, 2016 12:53 am

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: 573
Joined: 11 March 2013

Re: Canonical Form

Postby Maq777 » Wed Nov 23, 2016 1:57 am

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.

Sorry for my bad english.

Thanks to both.
Maq777
 
Posts: 4
Joined: 30 April 2016

Previous

Return to General