catalog of all essentially different grids

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

Re: catalog of all essentially different grids

Postby dukuso » Mon Jun 07, 2010 7:08 am

how fast ? I haven't yet implemented the quick 6* 416-number creation
also looking for quick canonical form
or quick automorphism group
so to filter the 5.5e9 from my 1.16e10
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: catalog of all essentially different grids

Postby gsf » Mon Jun 07, 2010 7:57 am

dukuso wrote:how fast ? I haven't yet implemented the quick 6* 416-number creation
also looking for quick canonical form
or quick automorphism group
so to filter the 5.5e9 from my 1.16e10

Code: Select all
6*416       ~40000 grid/sec/Ghz
canon+aut    ~9000 grid/sec/Ghz
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: catalog of all essentially different grids

Postby dukuso » Mon Jun 07, 2010 9:22 am

too slow to walk through all the 5e9 grids

OK, using Kjell's (where is he ?) program from 2005, I think I need ~10h with 2GHz to generate
the 1.1e10 416-sixtuples and the counts for the 44-threetuples 1.1e10 grids,
presumably all the T-classes are represented, but I'm not sure.

it's running now , please no bug ...
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: catalog of all essentially different grids

Postby gsf » Tue Jun 08, 2010 5:00 am

dukuso wrote:too slow to walk through all the 5e9 grids

OK, using Kjell's (where is he ?) program from 2005, I think I need ~10h with 2GHz to generate
the 1.1e10 416-sixtuples and the counts for the 44-threetuples 1.1e10 grids,
presumably all the T-classes are represented, but I'm not sure.

it's running now , please no bug ...

do you have a url for Kjell's program
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

kjellfp's software at dukuso's web-site

Postby Pat » Tue Jun 08, 2010 7:52 am

gsf wrote:do you have a url for Kjell's program
User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

Re: catalog of all essentially different grids

Postby dukuso » Tue Jun 08, 2010 7:53 am

integrated into my command-line shell for input and output :

http://magictour.free.fr/index416.exe


ha, simultaneous post with PAT (how likely was that ?)


allg416.exe sudogan.gri >ll

did the 7.5h run to count the 44-band-triples
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: catalog of all essentially different grids

Postby dukuso » Tue Jun 08, 2010 9:08 am

to summarize:
---------------------------------------
You generate 416 compressed files of total size 5.5GB
and each of these can be expanded to give sudokugrids,
one from each S-class in lexicographically minimal form.
The 416 files represent the S-classes with that 416-gangster
as first band and all other bands or towers have same or larger 416-index
The grids in that file are lexicographically minimal in their S-class
and are sorted lexicographically.
(right ?)
---------------------------------------

1.)
I'd like a list of all (-say- "X-classes"), minimized by size, # of members, such that
every T-class can be obtained from at least one member of the list by permuting
mini-colomns within the bands.
And a bitstream-file that indicates which of the thus (canonically) genearated
mini-column-permutations do create new T-classes.
An estimated ~400000 sudokugrids for the X-classes, and a bitstream
of ~1.5 e10 bits ~ 2e9 bytes = 2GB

This can then be used to generate exactly one sudoku from each T-class, residing
in memory for a moment, in less than an hour with 2GHz, 1e10 grids in total

--------------------------------------------------------------

2.) the same, but for S-classes, the same ~400000 sudokugrids, but another
bitstream, so that only one sudokugrid from each S-class is created

--------------------------------------------------

can this idea be applied to the rookery-based liting of -classes ?
can it be applied to latin squares isotopy classes ?
or n-queen-solutions or pandiagonal latin squares or
magic squares or cubes or Nasik-Cubes or magic knight's tours
or ...
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: catalog of all essentially different grids

Postby gsf » Tue Jun 08, 2010 2:13 pm

dukuso wrote:to summarize:
---------------------------------------
You generate 416 compressed files of total size 5.5GB
and each of these can be expanded to give sudokugrids,
one from each S-class in lexicographically minimal form.
The 416 files represent the S-classes with that 416-gangster
as first band and all other bands or towers have same or larger 416-index
The grids in that file are lexicographically minimal in their S-class
and are sorted lexicographically.
(right ?)
---------------------------------------

yes
the advantages of sorting are
  • during generation, each new candidate is compared only with itself:
    it is canonicalized and if the lexicographic order is less than itself
    then it has been seen already
  • the compression algorithm compresses only the difference between
    the current and next grid: the more similarity between successive grids
    means the better the compression ratio
1.)
I'd like a list of all (-say- "X-classes"), minimized by size, # of members, such that
every T-class can be obtained from at least one member of the list by permuting
mini-colomns within the bands.
And a bitstream-file that indicates which of the thus (canonically) genearated
mini-column-permutations do create new T-classes.
An estimated ~400000 sudokugrids for the X-classes, and a bitstream
of ~1.5 e10 bits ~ 2e9 bytes = 2GB

This can then be used to generate exactly one sudoku from each T-class, residing
in memory for a moment, in less than an hour with 2GHz, 1e10 grids in total

--------------------------------------------------------------

2.) the same, but for S-classes, the same ~400000 sudokugrids, but another
bitstream, so that only one sudokugrid from each S-class is created

--------------------------------------------------

can this idea be applied to the rookery-based liting of -classes ?
can it be applied to latin squares isotopy classes ?
or n-queen-solutions or pandiagonal latin squares or
magic squares or cubes or Nasik-Cubes or magic knight's tours
or ...

given a canonicalization function for each type of grid it should be
possible to have a general algorithm parameterized on the canonicalization function
computing the list of seed grids would be the hard part
to know the list was complete you would need to know the size of the generated class up to isomorphism

Red Ed, assuming we had the list of seed grids for the S-classes, with the
number of grids (up to isomorphism or with dups counted) for each class, could that
be used in an unbiased random grid generator?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: catalog of all essentially different grids

Postby dukuso » Tue Jun 08, 2010 9:27 pm

fast creation of grids doen't seem to help much, since, whatever calculation you do
with the grids, it is hardly much faster than loading the grid from HD.
The total time is >5 hours anyway.
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: catalog of all essentially different grids

Postby dukuso » Wed Jun 09, 2010 6:37 am

> so I'm thinking of a pay it forward scheme where I mail an 8Gi
> usb stick containing the catalog to one recipient, and that recipient mails it to the next etc.
>
> I assume it will mostly be forum oldies who want the catalog
> we can exchange snail mail addrs via pm
>
> post here if you want on the list
> include your country so the mailing can be optimized for distance

yes, I want it. These small (~1cm*1cm) memory chips are easy to send in a letter or even card,
but usb-stick is also OK. I pay by paypal ? Address by PM
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: catalog of all essentially different grids

Postby Red Ed » Wed Jun 09, 2010 7:05 am

gsf wrote:Red Ed, assuming we had the list of seed grids for the S-classes, with the
number of grids (up to isomorphism or with dups counted) for each class, could that
be used in an unbiased random grid generator?
Sure. Each S-class should be picked with probability inversely proportional to the number of automorphisms it exhibits; then grab a representative of that S-class and 'scramble' it (relabel, swap bands etc.) randomly.

You can build fast unbiased random generators with much less lookup data than that, though, e.g. my method or (sadly lost in the crash) holdout's.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: catalog of all essentially different grids

Postby gsf » Wed Jun 09, 2010 1:44 pm

Red Ed wrote:
gsf wrote:Red Ed, assuming we had the list of seed grids for the S-classes, with the
number of grids (up to isomorphism or with dups counted) for each class, could that
be used in an unbiased random grid generator?
Sure. Each S-class should be picked with probability inversely proportional to the number of automorphisms it exhibits; then grab a representative of that S-class and 'scramble' it (relabel, swap bands etc.) randomly.

You can build fast unbiased random generators with much less lookup data than that, though, e.g. my method or (sadly lost in the crash) holdout's.

I was thinking about the ~400K S-class generators (we don't have them yet)
  • pick an S-class generator grid
  • generate one S-class grid from it using minirow permutations
  • scramble it using S-class permutations
each S-class generator would generate a known number of S-class members so they can be weighted
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: catalog of all essentially different grids

Postby dukuso » Wed Jun 09, 2010 2:36 pm

some would be generated twice, some not
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: catalog of all essentially different grids

Postby gsf » Wed Jun 09, 2010 4:12 pm

dukuso wrote:some would be generated twice, some not

not if we add in your idea of an S-class generator bitstream that identifies dups
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: catalog of all essentially different grids

Postby Red Ed » Wed Jun 09, 2010 4:52 pm

gsf wrote:I was thinking about the ~400K S-class generators (we don't have them yet)
Oh, that. Okay. If X-classes generate T-classes then maybe W-classes generate S-classes ... Whatever; it doesn't look like a win because of the overhead of keeping a cumulative version of the anti-dup bitstream that tells you how many new S-classes the given X- (or W- ... I can't keep up) class generates.

I'm not seeing any problem with my method or holdout's. What issue with those are you trying to solve?
Red Ed
 
Posts: 633
Joined: 06 June 2005

PreviousNext

Return to General