The New Sudoku Players' Forum

[dukuso]

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

[gsf]

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

[dukuso]

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

[gsf]

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

[Pat]

do you have a url for Kjell's program

kjellfp's software at dukuso's web-site --
index416.exe

[dukuso]

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]

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

[gsf]

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?

[dukuso]

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]

> 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

[Red Ed]

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.

[gsf]

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

[dukuso]

some would be generated twice, some not

[gsf]

some would be generated twice, some not

not if we add in your idea of an S-class generator bitstream that identifies dups

[Red Ed]

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?