The New Sudoku Players' Forum

[alyssa21]

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;)

[gsf]

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

[Allan Barker]

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.

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

my first response to your post is/was

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?

[alyssa21]

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?

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

[gsf]

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?

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

[alyssa21]

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

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

[gsf]

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

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

[Allan Barker]

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.

[alyssa21]

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.

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

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

[coloin]

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