The New Sudoku Players' Forum

[dukuso]

yes, but 50MB uncompressed
my http://magictour.free.fr/G_CLASS.GZ
(6MB compressed) has members
not minimal in their S-class or in their G-class

G-classes are not invariant to transposition
You can permute symbols,rows within a band,bands,
columns within a stack,stacks ;
even permute the 9 minicolums independently within a band ;
without leaving the G-class
- but not transpose, transposing usually changes the G-class.


band=floor
stack=tower

[dukuso]

here is a fast program to permute minicolumns within a band
it generates grids usually from a different T-class

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

windows - executable, source code attached to the executable, as usual

I may replace it with new versions in the next hours

[dukuso]

44 lexicographically minimal gangsters with number in my previous enumeration
3 consecutive rows

123456789456789123789123456 01
123456789456789123789123465 02
123456789456789123789123564 04
123456789456789123789132465 07
123456789456789123789132546 08
123456789456789123789132564 11
123456789456789123789231564 41
123456789456789123789231645 42
123456789456789123798132546 15
123456789456789123798213564 32
123456789456789123798213654 38
123456789456789123798231564 34
123456789456789123798231645 33
123456789456789123897231564 44
123456789456789132789123546 03
123456789456789132789213456 13
123456789456789132789213645 18
123456789456789132789213654 17
123456789456789132789231546 28
123456789456789231789123645 05
123456789456789231789312456 40
123456789457189236689273145 35
123456789457189236689273154 23
123456789457189236689273514 31
123456789457189236689372145 37
123456789457189236689372154 22
123456789457189236698237514 25
123456789457189236698723145 36
123456789457189236698732145 27
123456789457189236869372145 30
123456789457189263689273154 26
123456789457189263689723154 14
123456789457189263689732154 24
123456789457189263968327145 39
123456789457189263968327514 20
123456789457189263968372145 43
123456789457189263986327145 19
123456789457189263986327154 09
123456789457189623689723145 12
123456789457189623689723154 06
123456789457189623689723514 10
123456789457189632698732514 21
123456789457189632896372154 29
123456789457289631896137254 16


google search for 123456789457289631896137254 gave one hit, but no longer
accessable, page not cached

(gsf-)sudoku -qFN -f "%#0c" file prints sudokugrids minimal in the same S-class
as the sudokugrids in file ? (~7000 sudokus per sec.)
do we have a program to print sudokugrids minimal in the same T-class ?

[gsf]

some of the band count data in a post on the previous page were wrong
corrections were edited in

[dukuso]

I also had some errors
i.e. the rookery-counts, standing here since 2005 uncorrected
and ATM. I'm not sure whether the G-classes generate each T-class at least once
(by permuting mini-columns in a band)
They should still create each S-class at least once

we always need an independent confirmation of the numbers
(but then both may have made the same mistake..., less likely, though)

[gsf]

We want a procedure to walk through 5.4e9 grids, one from each S-class,
and then maybe call a subroutine to check some property.
You can read the grid from HD , that needs about 3 hours and 450 GB
You can use compressed grids, but that needs ~1 extra day for decompresion.

are you thinking about random access or streaming access?
for sudz compression the streaming rate is ~100K grids/sec/Ghz
~5 hours minimum to stream through the entire catalog @ 2.8Ghz
so sudz roughly doubles the access time but decreases storage by a factor of ~76 (5.9Gib)

[dukuso]

streaming, I think.
1 hour to generate the ~1.1e10 grids with 1.4GHz (sorted for ~3e5 G-classes
=44-gangster-triples for the bands)
filtering for ~5.5 S-classes may take another estimated hour

[gsf]

streaming, I think.
1 hour to generate the ~1.1e10 grids with 1.4GHz (sorted for ~3e5 G-classes
=44-gangster-triples for the bands)
filtering for ~5.5 S-classes may take another estimated hour

did you post the program to generate the ~1.1e10 grids?

[dukuso]

http://magictour.free.fr/allg.exe (post200330.html)
C-source code attached to the executable, as usual

it reads the grids from sudogan.gri (one from each G-class, replaced with G_CLASS now)
and just permutes the 9 minicolumns
in each band and then combines the bands (typically ~30 bands) to create the grids

http://magictour.free.fr/G_CLASS.GZ

[gsf]

http://magictour.free.fr/allg.exe (post200330.html)
C-source code attached to the executable, as usual

it reads the grids from sudogan.gri (one from each G-class, replaced with G_CLASS now)
and just permutes the 9 minicolumns
in each band and then combines the bands (typically ~30 bands) to create the grids

http://magictour.free.fr/G_CLASS.GZ

aha
I had already grabbed that but missed the connection between sudogan.gri and G_CLASS.GZ and the input to allg.exe
I assume the .GZ is the compressed .gri

[gsf]

http://magictour.free.fr/allg.exe (post200330.html)
C-source code attached to the executable, as usual

it reads the grids from sudogan.gri (one from each G-class, replaced with G_CLASS now)
and just permutes the 9 minicolumns
in each band and then combines the bands (typically ~30 bands) to create the grids

http://magictour.free.fr/G_CLASS.GZ

when downloaded and uncompressed G_CLASS has 306693 grids
a quick canonicalization check shows two pairs of dups
so up to isomorphism there are only 306691 grids
the two pairs are

Code: Select all

124538697835796421976241583512463978643879215789125364251684739368957142497312856 # 42912
152698374863742591974351268295164783316875429487239615521486937639517842748923156 # 43366

124693578836751492975248361312564789589172634647389215251836947468927153793415826 # 153401
132765498876249351945381276521876934683594712794123685217438569359612847468957123 # 254040


did these grids slip through a signature?

[dukuso]

what isomorphism ?
S-class-isomorphism ? Then I'm surprised there are only two doubles.

They should be in different T-classes, though.

Permuting minicolumns does (usually) change the S-class



http://magictour.free.fr/index416.exe
determines the 416-gangster-indices for the 6 chutes


42912:23,21,342, 385,311,378
43366:338,244,284, 97,80,256
153401:80,256,97, 338,244,284
254040:311,378,385, 21,23,342

transposed, different T-class

[coloin]

More obviously......

Code: Select all

c:\Suxx>index416 test.txt 4
 # 42912   # 21  23 342  , 311 378 385
 # 43366   # 21  23 342  , 311 378 385
 # 153401  # 80  97 256  , 244 284 338
 # 254040  # 80  97 256  , 244 284 338

the two grids do have the same bands.......

so.....dukuso - are you saying you can generate the grids quicker - except a few isomorphs get generated ?

C

[dobrichev]

We want a procedure to walk through 5.4e9 grids, one from each S-class,
and then maybe call a subroutine to check some property.
You can read the grid from HD , that needs about 3 hours and 450 GB
You can use compressed grids, but that needs ~1 extra day for decompresion.

are you thinking about random access or streaming access?
for sudz compression the streaming rate is ~100K grids/sec/Ghz
~5 hours minimum to stream through the entire catalog @ 2.8Ghz
so sudz roughly doubles the access time but decreases storage by a factor of ~76 (5.9Gib)

I am using a flat file catalog of size 54 727 305 380 bytes (80 bits per grid).
The codec source is at http://sites.google.com/site/dobrichev/sudokugrids/sudoku_statistics_1.1.zip, file grid.cpp.
A full scan (including counting the unavoidable sets of size 4 to be sure optimizer didn't eliminate parts of the code) takes about 70K grids/GHz (~4 hours on 2x2.8 GHz).
This approach allows storing any collections of Row Minlex normalized grid sets.
Working with unique and ordered grids allows access in both directions (GetGridByIndex(index) = read from file position + decompress, or GetGridIndex(grid) = compress + binary search the file + return the index).

AFAIK Ano1 has an alternative codec which uses ~60MB lookup file. Not sure whether it has grid limitations at all (Box Minlex?).

[gsf]

what isomorphism ?
S-class-isomorphism ? Then I'm surprised there are only two doubles.

yes, I was surprised too that only 2/~300000 required the grid and its transpose

Permuting minicolumns does (usually) change the S-class

http://magictour.free.fr/index416.exe
determines the 416-gangster-indices for the 6 chutes

42912:23,21,342, 385,311,378
43366:338,244,284, 97,80,256
153401:80,256,97, 338,244,284
254040:311,378,385, 21,23,342

transposed, different T-class

-f%#bc in my solver prints the sorted band indexes
-f%#Bc unsorted