About Essentially Different Sudoku.

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

About Essentially Different Sudoku.

Postby alyssa21 » Wed Sep 10, 2008 12:03 am

I know there are 5472730538 essentially different sudoku grids.
But it was enumerated by using the group theory method, and it wasn't actually listed up all.
So, a question.

Have anyone ever listed up all essentially different sudoku grids actually?

thanks for reading.
my english is poor, sry;)
alyssa21
 
Posts: 4
Joined: 09 September 2008

Re: About Essentially Different Sudoku.

Postby gsf » Wed Sep 10, 2008 1:18 am

alyssa21 wrote:I know there are 5472730538 essentially different sudoku grids.
But it was enumerated by using the group theory method, and it wasn't actually listed up all.
So, a question.

Have anyone ever listed up all essentially different sudoku grids actually?

thanks for reading.
my english is poor, sry;)

yes, listed but not posted
see http://forum.enjoysudoku.com/viewtopic.php?p=41368#p41368
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Allan Barker » Wed Sep 10, 2008 9:17 pm

gsf,

I just read your referenced posts about the 5472730538 essentially different Sudoku grids database. I was wondering, have you thought about trying to find the most difficult puzzle in the lot, which would presumably be the most difficult puzzle (?). I'm aware of the time involved but thought that it might be interesting to start the task by first "draining the pond" of easy ones leaving behind a much smaller batch of more difficult puzzles above a given rating. This is initially faster becasue you can abort rating puzzles above a to be determined difficulty rating.

Once down to about a million, the task could be approached incrementally, and other folks could help out, too. This might even help stimulate the development of rating methodology and/or provide for interesting comparison, discussion, and competition.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby gsf » Wed Sep 10, 2008 10:08 pm

Allan Barker wrote:I just read your referenced posts about the 5472730538 essentially different Sudoku grids database. I was wondering, have you thought about trying to find the most difficult puzzle in the lot, which would presumably be the most difficult puzzle (?). I'm aware of the time involved but thought that it might be interesting to start the task by first "draining the pond" of easy ones leaving behind a much smaller batch of more difficult puzzles above a given rating. This is initially faster becasue you can abort rating puzzles above a to be determined difficulty rating.

my first response to your post is/was
I almost wrote:alas its a db of solution grids
from a thread on this forum there are an estimated 10^15 minimal puzzles per grid
analyzing at a rate of 10^6 minimal puzzles per second would require ~10^9 sec (~30 years) per grid

but on rereading your post I think puzzle/grid may have been used interchangeably when they shouldn't

what did you mean by find the most difficult puzzle in the lot?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: About Essentially Different Sudoku.

Postby alyssa21 » Thu Sep 11, 2008 2:20 am

thank you for replying.
I'm now writing a program for listing all essentially different sudoku grids, because I want to examine the characteristic of the whole sudoku grids.
But, in my mehotd, if using only one cpu, it seems to take about 7days to 10days.
Could you tell me how long your method took to list it all?

gsf wrote:yes, listed but not posted
see http://forum.enjoysudoku.com/viewtopic.php?p=41368#p41368
Last edited by alyssa21 on Wed Sep 10, 2008 10:27 pm, edited 1 time in total.
alyssa21
 
Posts: 4
Joined: 09 September 2008

Re: About Essentially Different Sudoku.

Postby gsf » Thu Sep 11, 2008 2:25 am

alyssa21 wrote:thank you for replying.
I'm now writing a program for listing all essentially different sudoku grids, because I want to examine the characteristic of the whole sudoku grids.
But, in my mehotd, if using only one cpu, it seems to take about 7days to 10days.
Could you tell me how long your method took to list all?

gsf wrote:yes, listed but not posted
see http://forum.enjoysudoku.com/viewtopic.php?p=41368#p41368

it took ~2weeks @ 3Ghz to generate and compress
it takes ~7hours to decompress and list
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: About Essentially Different Sudoku.

Postby alyssa21 » Thu Sep 11, 2008 2:41 am

I'm interested in your mehotd.
you don't write a paper or so about your method?

gsf wrote:it took ~2weeks @ 3Ghz to generate and compress
it takes ~7hours to decompress and list
alyssa21
 
Posts: 4
Joined: 09 September 2008

Re: About Essentially Different Sudoku.

Postby gsf » Thu Sep 11, 2008 9:12 am

alyssa21 wrote:I'm interested in your mehotd.
you don't write a paper or so about your method?

gsf wrote:it took ~2weeks @ 3Ghz to generate and compress
it takes ~7hours to decompress and list

the url above points to a thread that contains some details

basically it does the search in minlex puzzle order
and splits it by minlex bands
it fills in the current search puzzle top to bottom left to right
this allows it to prune by doing minlex checks of the partial puzzle
if it minlex's to a smaller puzzle it is discarded

this is the crux of the algorithm: it is able to check for duplicates via minlex only
and does not have to check all previously generated puzzles in the search

the bottleneck is the partial puzzle minlex algorithm
to save time it is not recomputed with every clue addition

the minlex canonical bands are labeled 001-416
you can use my solver to generate all of the essentially different puzzles in a minlex band NNN with the option
Code: Select all
-gbNNN

a puzzle is a member of a band class NNN iff it is not a member of a band class MMM, MMM < NNN
this means that some band classses may have 0 members
it also means that lower numbered band classes usually take longer to generate
but it also means that if you have 416 spare cpus you can partition the search by band
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Allan Barker » Thu Sep 11, 2008 9:42 am

gsf wrote:
...but on rereading your post I think puzzle/grid may have been used interchangeably when they shouldn't


Opps, that's exactly what I did and then got carried away with the idea before realizing the mistake. The scenario I envisioned was a large database of unrated puzzles containing one or more extreme puzzles, which was large enough that searching for the toughest puzzles would take time and effort. I thought this might make an interesting environment for comparing rating methods particularly if there was some competition involved.

I should have realized my mistake because 5472730538 is such a small number, where as I like to point out that the number 9^81 is roughly the number of atoms in the universe.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Re: About Essentially Different Sudoku.

Postby alyssa21 » Fri Sep 12, 2008 2:11 am

thank you for replying.
This is my fault, but my being poor at english, I cannot understand all of your english, it seems, however, my method is quite similar to yours.
I take the least grid, when looking a grid as an 81th figures, as a representative of essentially 'equal' grids.
And, I can classify the top band to 397 groups.
This is not 416, so my method may be somewhere different from yours.

Anyway, thank you.
I will have someone who is good at english translate well and I'll reread in detail.

gsf wrote:
alyssa21 wrote:I'm interested in your mehotd.
you don't write a paper or so about your method?

gsf wrote:it took ~2weeks @ 3Ghz to generate and compress
it takes ~7hours to decompress and list

the url above points to a thread that contains some details

basically it does the search in minlex puzzle order
and splits it by minlex bands
it fills in the current search puzzle top to bottom left to right
this allows it to prune by doing minlex checks of the partial puzzle
if it minlex's to a smaller puzzle it is discarded

this is the crux of the algorithm: it is able to check for duplicates via minlex only
and does not have to check all previously generated puzzles in the search

the bottleneck is the partial puzzle minlex algorithm
to save time it is not recomputed with every clue addition

the minlex canonical bands are labeled 001-416
you can use my solver to generate all of the essentially different puzzles in a minlex band NNN with the option
Code: Select all
-gbNNN

a puzzle is a member of a band class NNN iff it is not a member of a band class MMM, MMM < NNN
this means that some band classses may have 0 members
it also means that lower numbered band classes usually take longer to generate
but it also means that if you have 416 spare cpus you can partition the search by band
alyssa21
 
Posts: 4
Joined: 09 September 2008

Postby coloin » Fri Sep 12, 2008 5:53 pm

There are 416 bands, 6 of these per solution grid.

I wanted to believe that each essentially different solution grid had a unique identifying code.

Eg, 123,234,267 : 210,334,390.

[416 ^ 6 ] / [36] * [2] is way bigger than our total.

But that did not turn out to be the case.

Maybe your classification is different - in which case it might be true.

C
coloin
 
Posts: 1637
Joined: 05 May 2005


Return to General