The New Sudoku Players' Forum

[gsf]

OK, thanks, I have it now. renamed to gsf4.exe 467968 bytes Windows executable.

-gB gives the 416 gangsters
the text could be extracted from the executable

gsf4 -gb299 -f '%#ec' -o 299.sudz

gives an error after ~1min , program must be terminated, report to Microsoft ?


gsf4 -gb299 > k5
is running ...

gives 133302 sudokus in file k5

with first band being 416-gangster #204

118 416-gangsters occur in total 299+118-1=416

looks like the windows version has trouble compressing
it uses the bzip2 library
if you want to test compression I can post the latest unix binary in whatever flavor you need

[dukuso]

do you have the sizes of the 416 files ?

[gsf]

do you have the sizes of the 416 files ?

300-416 contains all the bands between 300 and 416 inclusive
[ edit : this was not what dukuso was asking for -- its the number of bytes per band file -- the number of grids per band appears a few posts down ]

Code: Select all

  1035280 001  67389518 039  47756282 077  28893306 115  16099111 153   7236948 191   2929121 229    990464 267
 23688654 002  66527605 040  47016409 078  28454963 116  15893819 154   7133043 192   2838653 230    948257 268
 15615273 003  36183041 041  46810247 079  28007898 117  15503652 155   6992685 193   2599282 231    951905 269
  8366028 004  66004198 042  45634870 080  27402504 118  15331331 156   6695614 194   2526378 232    871045 270
 42206824 005  65546132 043  45137500 081  27119563 119  14975704 157   6550640 195   2492726 233    828316 271
 79749100 006  64345760 044  44563063 082  14043964 120  14807661 158   6405949 196   2410217 234    828605 272
 14933553 007  34643417 045  44301486 083  26223351 121  14583977 159   6248008 197    829658 235    425736 273
  5372458 008  63792574 046  23258848 084  13046916 122  14322015 160   6062326 198   2333430 236    417177 274
  8195149 009  63736485 047  43302848 085  25656277 123  13773218 161   5918225 199   1213855 237    409575 275
 43242379 010  63380450 048  42842780 086  13317406 124  13477630 162   5784716 200   2199244 238    383404 276
 42945926 011  62707591 049  42068301 087  24999670 125  13249178 163   5644370 201   2129792 239    374077 277
 43565208 012  61370676 050  41688079 088  24561398 126  12964705 164   5490374 202    378299 240    713196 278
 15214293 013  61350857 051  41077241 089  24506276 127  12648861 165   5351009 203   1105053 241    356478 279
 41218762 014  60459469 052  40410573 090  23894481 128  12399272 166   5289945 204   2057654 242    351583 280
 42513283 015  32399963 053  39868152 091  12409712 129   6462427 167   5162891 205   1934609 243    346581 281
  1741252 016  32697505 054  39344161 092  23167294 130  12080998 168   4938073 206   1924889 244    670630 282
 14568790 017  59491259 055  38697846 093  22890171 131  11808131 169   4790146 207    980961 245    584549 283
 42525196 018  58935177 056  38143413 094  22366510 132  11536065 170   4645865 208   1833420 246    313398 284
 41907385 019  58947636 057  37564201 095   4089664 133  11346448 171   4498267 209   1046097 247    308020 285
 75509109 020  57743873 058  37038197 096  21903908 134  11117336 172   2399806 210   1603270 248    295095 286
 41658668 021  57696702 059  19310558 097  21705990 135  10897679 173   4283342 211   1674547 249    298600 287
 73876227 022  56870620 060  18697297 098  21439214 136  10614115 174   4337288 212    829599 250    284176 288
 39747071 023  56015079 061  35753862 099  11041302 137   5566331 175   2230291 213    875238 251    101443 289
 72289380 024  55332841 062  35314124 100  20780588 138  10210055 176   2125685 214    929001 252    279746 290
 38986984 025  54787527 063  18557162 101  10704291 139  10004545 177   4060341 215    848141 253    514140 291
 36015703 026  54292596 064  34366929 102  20065870 140   9777043 178   4147769 216    332013 254    514207 292
  4668386 027  53650237 065  33869431 103  19678791 141   9664409 179   3996476 217    796893 255    474766 293
 37951985 028  53878794 066   6277648 104  10210611 142   9358929 180   3960581 218    785964 256    474771 294
  4772559 029  28521184 067  33489510 105  19020365 143   9150981 181   2010872 219   1418338 257    434836 295
  4699321 030  52924985 068  32970045 106   9942071 144   9006420 182   3744218 220   1396210 258    390577 296
 13393781 031  52361441 069  32440440 107  18583609 145   8806259 183   3512523 221    712108 259    381393 297
 37941690 032  51688534 070  31914526 108  18300312 146   8579319 184   3572803 222   1339983 260    196931 298
 68828763 033  27048791 071  31397149 109  17884599 147   8335283 185   3403058 223   1192488 261    346952 299
 68678759 034  50563199 072  30912299 110   9450833 148   8149319 186    725012 224   1151961 262   5911613 300-416
 68318302 035  49893634 073  30669330 111   9266424 149   7897342 187   3686424 225   1163757 263
 37383189 036  49473214 074  30164602 112  17259605 150   7738690 188   3236311 226   1111127 264
 68131523 037  26022722 075  29615887 113  17075143 151   7540391 189   2968264 227   1039467 265
 67159653 038  48292993 076  15434315 114  16724952 152   3919953 190   2923739 228   1028127 266


[dukuso]

sums to 6129079849.
Shouldn't it sum to 5472730538 ?

I had created the file for 299, it had 133302 sudokugrids.
But your list above gives 346952

[gsf]

sums to 6129079849.
Shouldn't it sum to 5472730538 ?

I had created the file for 299, it had 133302 sudokugrids.
But your list above gives 346952

sorry, I posted the file size in bytes
will post the number of grids per band shortly

[gsf]

here is a table with the number of grids per band
due to the canonical ordering, some later bands have no representative grids because they are isomorphic to a grids from lower bands
[ edit : I've been away from this for too long -- the band counts from 300 on were incorrect -- fixed with this edit ]
the bands with 0 elements are { 395 397 398 400 402 403 404 406 408 409 410 412 413 414 415 }

Code: Select all

  1007170 001  29966384 053  25997296 105   9805813 157   2443960 209    546083 261     80765 313      1368 365
 25502082 002  29734495 054  25467197 106   9629320 158   1243959 210    524804 262     43270 314      1232 366
 16538087 003  58731513 055  24888528 107   9490222 159   2317171 211    534167 263     74594 315      1667 367
  8417906 004  57263818 056  24423300 108   9280124 160   2357854 212    503384 264     69012 316       925 368
 48737791 005  57033275 057  23988326 109   8844112 161   1137589 213    464985 265     73627 317       872 369
 96229042 006  55394556 058  23541927 110   8628099 162   1083228 214    461786 266     62449 318       928 370
 15765443 007  55022930 059  23070530 111   8429593 163   2183311 215    441645 267     59123 319       808 371
  5306280 008  54018514 060  22609142 112   8227144 164   2244753 216    418773 268     57580 320       560 372
  8136013 009  52964870 061  22100458 113   7998287 165   2143677 217    424148 269     47910 321       757 373
 47174193 010  52242492 062  10879514 114   7813413 166   2100798 218    378441 270     44876 322       451 374
 46788396 011  51245000 063  21378062 115   3839149 167   1007465 219    361885 271     46852 323       245 375
 46177270 012  50540742 064  20985174 116   7548052 168   1970315 220    360821 272     46002 324       333 376
 15340394 013  49644127 065  20674972 117   7349287 169   1841722 221    176161 273     40108 325       156 377
 45397270 014  49190978 066  20107116 118   7146807 170   1873099 222    172023 274     37300 326       193 378
 45600758 015  24077300 067  19854606 119   6993422 171   1772301 223    165927 275     36969 327       161 379
  1631576 016  47978806 068   9732970 120   6828801 172    347777 224    154694 276     31504 328        23 380
 15093541 017  47059527 069  19084488 121   6674911 173   1968442 225    150664 277     28919 329       163 381
 45101600 018  46231581 070   9491325 122   6476248 174   1677704 226    309399 278     27982 330       154 382
 44832423 019  22715795 071  18532281 123   3166465 175   1521001 227    144927 279     29202 331       111 383
 88782526 020  44778204 072   9142485 124   6205963 176   1498734 228    141820 280     25098 332       124 384
 44036568 021  44053469 073  18075269 125   6040631 177   1515366 229    137601 281     20652 333        87 385
 85627559 022  43401907 074  17675306 126   5882934 178   1457098 230    287667 282     10105 334        49 386
 42711122 023  21398806 075  17545752 127   5812748 179   1331185 231    246093 283     19471 335        66 387
 85102373 024  42061440 076  16990098 128   5615082 180   1279569 232    123480 284     18996 336       125 388
 41847039 025  41316125 077   8369473 129   5461387 181   1262013 233    124070 285     17212 337        27 389
 41335391 026  40571245 078  16406705 130   5367414 182   1218744 234    116970 286     14780 338        59 390
  4455504 027  40282447 079  16189996 131   5222068 183    386642 235    117351 287     13660 339        19 391
 41102914 028  39233218 080  15791769 132   5072949 184   1182963 236    110418 288     12324 340        41 392
  4591391 029  38522319 081   2613345 133   4918277 185    570172 237     37988 289     10597 341         2 393
  4664261 030  37881913 082  15362664 134   4778878 186   1111083 238    109351 290      9562 342        16 394
 13606209 031  37460193 083  15272476 135   4641003 187   1076551 239    211267 291      9012 343         X 395
 40697707 032  18460204 084  14918036 136   4539624 188    167032 240    209636 292      8215 344        11 396
 80468663 033  36127803 085   7254450 137   4407284 189    533940 241    189161 293      7261 345         X 397
 79175610 034  35584769 086  14383075 138   2186822 190   1048083 242    188766 294      3569 346         X 398
 77979783 035  34821531 087   7011714 139   4220821 191    974591 243    171584 295      7136 347        10 399
 38536298 036  34334716 088  13738161 140   4158097 192    967788 244    152633 296       455 348         X 400
 76146967 037  33769162 089  13445152 141   4070158 193    455310 245    147806 297      2935 349         1 401
 74505665 038  33174401 090   6593805 142   3857103 194    915249 246     70955 298      2990 350         X 402
 74154564 039  32520037 091  12918117 143   3785628 195    500537 247    133302 299      4836 351         X 403
 72171447 040  31945541 092   6403269 144   3693474 196    783336 248    139754 300      2156 352         X 404
 36053455 041  31221072 093  12568136 145   3555681 197    822496 249    119226 301      2141 353         4 405
 70552290 042  30579410 094  12354720 146   3453089 198    377256 250     20203 302      1959 354         X 406
 69437575 043  29977732 095  12036469 147   3345667 199    408556 251     62246 303      4171 355        19 407
 67978951 044  29390061 096   5931073 148   3252227 200    437792 252     63613 304      3376 356         X 408
 33904021 045  14518368 097   5949060 149   3165254 201    387029 253     69669 305      3171 357         X 409
 66337407 046  14372444 098  11577852 150   3064062 202    140436 254     58811 306      3150 358         X 410
 65880161 047  28268021 099  11435633 151   2966309 203    361962 255     21225 307       647 359         3 411
 64996381 048  27849953 100  11155974 152   2932890 204    354702 256     56942 308      1528 360         X 412
 63898062 049  13768854 101  10671486 153   2841380 205    675674 257     55120 309      2484 361         X 413
 62192220 050  26929453 102  10525735 154   2701985 206    661737 258     49427 310      2233 362         X 414
 61691475 051  26382806 103  10188634 155   2628788 207    313209 259     91869 311      1930 363         X 415
 60192385 052   4359314 104  10059617 156   2532198 208    623191 260     89983 312      1353 364         1 416


[dukuso]

sums to 5472730538 now.

> some later bands have no representative grids because they are isomorphic to a grids from lower bands

but this was supposed to be considered by sudoku -bg ?
So to create the catalog of all essentially different grids I run

sudoku -gbxxx >> grids

for xxx running from 001 - 300
and then for 303,309,313,318,323,332

but ignoring the other xxx


is there a good,fast program to generate the canonical form ?
to generate the automorphisms ?
I remember, I converted the sudokus to graphs and then using Nauty

[dukuso]

> list some hundred of grid-transformations=operations , maps to manipulate a valid grid
> so to obtain another usually non-equivalent grid.

that's not so easy, not so fast. The easy transformations would generate
isomorphic sudokugrids.
You can generate sudokugrids by solving sudokus with multiple solutions.
But again, I assume that's too slow.

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.

You can use sudokus with the last band missing and then just lookup all
the solutions in a table. Then examine which of these are in a new
S-class, lookup some checksum

[gsf]

sums to 5472730538 now.

> some later bands have no representative grids because they are isomorphic to a grids from lower bands

but this was supposed to be considered by sudoku -bg ?
So to create the catalog of all essentially different grids I run

sudoku -gbxxx >> grids

for xxx running from 001 - 300
and then for 303,309,313,318,323,332

but ignoring the other xxx

good point that the solver should know the empty bands
the very first run of the algorithm had to compute them
once the output was verified its fine for them to be skipped
will fix that

is there a good,fast program to generate the canonical form ?
to generate the automorphisms ?
I remember, I converted the sudokus to graphs and then using Nauty

I hope my solver would be close to the fastest
a byproduct of the canonicalization of one grid is the number of automorphisms
btw, #automorphisms for each grid is also encoded in the sudz data

[gsf]

> list some hundred of grid-transformations=operations , maps to manipulate a valid grid
> so to obtain another usually non-equivalent grid.

that's not so easy, not so fast. The easy transformations would generate
isomorphic sudokugrids.
You can generate sudokugrids by solving sudokus with multiple solutions.
But again, I assume that's too slow.

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.

You can use sudokus with the last band missing and then just lookup all
the solutions in a table. Then examine which of these are in a new
S-class, lookup some checksum

~5e9 lookups is a challenging problem
some generation loops could generate another order of magnitude or more grids to be checked

the beauty of what I did (aha moment many moons ago) was to optimize comparison lookups to one comparison per grid

the inner generation loop generates grids in canonical order (so its a canonicalizer)
it keeps track of the previous canonicalized grid entered
if the current canonicalized grid is lexicographically <= the previous one then it is a dup and not entered
otherwise its a new grid and it is entered
"entered" here means: copy to output and replace the previous grid with the current grid

so the working data for the inner loop is 2 grids, previous and current
all of the other data is simply output and not referenced again by the inner loop

some places to speed up the inner loop

• quicker grid validity check
• quicker grid canonicalization

[dukuso]

what would be the command to get the number of automorphisms of an input file ?

this is worth its own thread here with all the options and switches
if not I might start one

[dukuso]

thinking again about my G-classes - it should be very fast to generate
~11B grids from it, at least one in each S-class (=isomorphism class, there are ~5.5e9)
My current program needs days, but I asume it can be improved: you just create
the possible bands for the top,midle,bottom band and then use all combinations.
Hard to imagine how to create grids faster !

Maybe that was even the motivation why I generated the G-classes, I don't remember now.

Now we must just check each of these ~11B grids, whether they are minimal in their isomorphism
class and reject those that aren't
You have a good routine for that already ?

[dukuso]

but then, why to create all the S-classes anyway ?

when you want to check all the S-classes for some property P, then you can just
quickly generate them on the fly :

for each of the ~300000 G-classes from the table
generate the possible sets of upper,middle and lower bands,
typically ~3*33 bands (between 16 and 288,average 33),
then combine them all to get typically ~36000
sudokugrids from that G-class.
About half of these will be "larger" in T-properties than their transpose,
which can be quickly checked, these needn't be tested for the property P.

When you have walked through all the ~300000 G-classes this way,
you will have tested a tiny fraction of isomorphic sudokus twice - who cares.

Well, you could check for automorphisms so to avoid this and speed
it up by ~1% ... at the cost of automorphism-testing.

[dukuso]

I implemented it now.
it generates ~3M sudokus per second, residing in Memory for a moment,
~1hour in total to generate all the ~11e9, at least one from each T-class.
Writing them to HD takes longer, ~40000 per second, 3 days in total for
all 11e9 sudokugrids, uncompresed, ~900 GB.

Now, I could check the 416-gangster 6-tuples or the signatures or the
number of bicolor-rectangle-corners of each of them ...
each test would take some few estimated hours

[gsf]

I implemented it now.
it generates ~3M sudokus per second, residing in Memory for a moment,
~1hour in total to generate all the ~11e9, at least one from each T-class.
Writing them to HD takes longer, ~40000 per second, 3 days in total for
all 11e9 sudokugrids, uncompresed, ~900 GB.

Now, I could check the 416-gangster 6-tuples or the signatures or the
number of bicolor-rectangle-corners of each of them ...
each test would take some few estimated hours

can you modify your program to list the first and last member found for each G-class
and then send it to me