The New Sudoku Players' Forum

[champagne]

Here is part of the results.
The columns are
Band401 - a zero-based band index. The catalogue doesn't know that 416 bands exists, it knows only those capable to be top band. Could be remapped to Band416 after some manual work and searching in archives which bands are never at the top.
Row4 - the values of the cells in row 4.
FirstGridIndex - a zero-based index of the minlex grid.
NumGrids - number of grids sharing with this (top band + row 4). This isn't the number of solutions but the number of catalog items.

Code: Select all

0   214365897   0          49776
......
400   274538196   5472730537   1


Generation took 25 minutes.

From disk space perspective mapping resolves the grid (assuming catalogue existence) but leaves the pattern of the givens open. I still doubt this approach is practical.

Hi Mladen,

good job.

Is missing the number of pairs band1,row4, at this point an important number for me.
The empty bands 1 have an index over 390, so this is not at all a problem
I would be happy to get the entire file to crosscheck my results in due time.

And I agree that this is not a clear answer to a high density storage of the data base of ED 18 clues puzzles.

[dobrichev]

I would be happy to get the entire file to crosscheck my results in due time.

I sent you a mail to orange.fr with 6 MB attachment. If you can't receive it for some reason, please let me know and we will discuss other options.

[coloin]

Code: Select all

001  001
002  002
...  ...
...  ...
...  ...
390  390
391  391
392  392
393  393
394  394
395  396
396  399
397  401
398  405
399  407
400  411
401  416


from this
Band 395,397,398,400,402,403,404,406,408,409,410,412,413,414,415 arnt in the list of the 401 bands

[coloin]

I don't see a way to skip the -> 5e9 number.

there is a way but it would be cumulative addition of the preceeding solution grids .... which i think might be forthcoming .... in a few hours or days

Edit - its already done !!!!!!

NumGrids - number of grids sharing with this (top band + row 4). This isn't the number of solutions but the number of catalog items.]

[coloin]

puzzle -> solution grid -> minlexsolutiongrid -> band/row4/number -> 5e9 number
This might give clarity in many applications... no ?
maybe the last step isnt necessary though

Mladen ... there might be a comercial application here for many sudoku apps ... just saying

[coloin]

From disk space perspective mapping resolves the grid (assuming catalogue existence) but leaves the pattern of the givens open. I still doubt this approach is practical.]

Well i did it for one instance of band/row4 and the results were the same as in gsf's catalogue

Code: Select all

band/row4
123456789457189236689327514278964351.............................................................
number of solutions  44402   x 12  =  532824
number of minlex catalogue items   =   35042                                                           


For the huge files in high-clue search I used a dozen of minlexed sorted zip files, and applied filtering/merging using standard utilities like comm, sort -m, sort -u, split. Operations were done in pipeline, decompressing archives on the fly, which utilizes multiple CPU in a simple and self-balanced way.

Amazing !!
Im sure you can incorporate the last step !!

[champagne]

I would be happy to get the entire file to crosscheck my results in due time.

I sent you a mail to orange.fr with 6 MB attachment. If you can't receive it for some reason, please let me know and we will discuss other options.

great, the file has 652408 items, something I hoped to see, below the million
thanks a lot mladen

[champagne]

in band 1 , with 1007170 grids there were only 126 different row4s,

I got the same 126 just with the automorphism filter, but only 124 of them have minlex solution grids attached.
these 2

Code: Select all

235697841
235814697


are empty. Some others have less than 10 solution grids attached

and here is the highest number of solution grids attached in mladen's 'list
band1 index 0-415/row4/number of solution grids

Code: Select all

9   237861495   62887

[dobrichev]

Code: Select all

390  390
391  391
392  392
393  393
394  394
395  396
396  399
397  401
398  405
399  407
400  411
401  416


Thank you!

[coloin]

....... but only 124 of them have minlex solution grids attached.

Yes I made an error looking at the line number there are only 124 row4s associated with band 1

Of course all the solution grids of band 1 [ with the various minlex col1s ] are min lex as there are no grids to be "pruned"

With only a relatively small number of catalogue items / solution grids per band+row4 this makes this calculatable and the order known on demand.

The pruning process with a specific band 1 is simple as the catalogue grids are the ones at the bottom of the minlex order of the solution grids.

[champagne]

Hi coloin,

And here I am fighting against this one (among others) having the band 1 as first band

123456789456789123789123456247538961861942537935671248394815672518267394672394815

Seen from my logic, this is a minlex morph, but it is not in the 1007170 .
I have to find what is the missing morphing in my code.

[coloin]

Your code is good, It is in band 1 at no 1007028

[champagne]

Your code is good, It is in band 1 at no 1007028

Not exactly "your code is good", but you are right, the 2 solution grids wrong here are

123456789456789123789123456247538961638941275591267348375692814814375692962814537
123456789456789123789123456247538961935671248861942537394815672518267394672394815

The second is close to the previous one

EDIT oups seen the bug

[champagne]

Thanks to mladen and coloin who sent me pieces of the catalog to speed up the debugging, I think that the first phase is over with a code building the catalog in the minlex order.

I have to run the test till the end, but for the first 6 bands, I got the same index row4 as in mladen's file.

The run took 30 mn (1800 seconds) on my desk computer (6 years old i7) to produce the 7200 rows 4.
Here the ratio of empty rows 4 is relatively low (620/7820) so the ratio 1800/7200 = 0.25 seconds for a direct link { solution grid => 5e9 id } seems the target on this computer.

Next step will be to build the front indexes. Likely

A 417 item index pointing on the next one and giving the start of the catalog for each band 1
The row 4 index.

As noticed mladen, only 10375 patterns of the row 4 are in use. It's likely of interest to have a lookup table to reduce the row 4 to a number 0-10374.

PS I have to do a first cleaning in the code, I'll open a repository in the next days

[coloin]

Pretty good work 1

On the generating side [ before the pruning] Its only necessary to use 44 gangster bands { rather than 416]
This of course doesnt reduce the grids to be pruned by minlexgriding.

On the min lexing side each band1/row 4 has specific options to complete an ascending column 1 [depending on x,y and z ]
There are twelve isomorphic ways to insert abcde and one which is minlex.

Code: Select all

+---+---+---+
|123|...|...|
|4..|...|...|
|x..|...|...|
+---+---+---+
|2yz|...|...|
|a..|...|...|
|b..|...|...|
+---+---+---+
|c..|...|...|
|d..|...|...|
|e..|...|...|
+---+---+---+


But may not be necessary I guess.

x can be 6,7,8,9
and looking at all the valid row4s , depending on x, the y,z can be any one of 25 out of 43 options..

Hidden Text: Show

Code: Select all

214
215
216
217
218
219
231
234
235
236
237
238
239
241
245
246
247
248
249
261
264
265
267
268
269
271
274
275
276
278
279
281
284
285
286
287
289
291
294
295
296
297
298


So as mentioned before, with x,y,z. = 6,7,8 there are only 3 minlex ways to have a,b,c,d,e.

Code: Select all

+---+---+---+
|123|456|789|
|457|189|236|
|689|327|514|
+---+---+---+
|278|964|351|
|3..|...|...|         3  3  5
|5..|...|...|         5  9  9
+---+---+---+
|7..|...|...|         7  5  3
|8..|...|...|         8  7  7
|9..|...|...|         9  8  8
+---+---+---+