The New Sudoku Players' Forum

by **coloin** » Fri Apr 05, 2024 4:09 pm

t wasnt clear from Mladens link as to how the compression program would work ....
And a 50G look up table isnt ideal !!

I can see why you would wish to keep the bands in min lex order and using the row4 would be a step to make the files more manageable.

A post by holdout and blue 4-RowCover confirmed the number of 4-row partial grids as 4051084.

its not clear from the thread what the actual number of row 4 completions there are .. and r4c1 is resticted to a 2 ... [EDIT it might well be 7666]

of course the number of ways to have a row 4 with a specific band isnt 8! .. its more like eg 1x6x4x5x3x3x2x1x1 ~ 2000
in band 1 , with 1007170 grids there were only 126 different row4s,
In band 299 with 133302 grids there were 1994 different row4s

the first 27 row4s in my list are

Hidden Text: Show

the number of row4s [ in use in the min lex] that i have scourged approaches 4020 and is increasing....
I think gsfs generator would generate these in the order

Compressing the whole file strategically , and reducing the data to be compressed go together i suppose.

the 416 can be stored
the row4 for a specific band can be generated on the fly too - although there are isomporphic reductions [ as in band 1] - so probably could be stored as an actual.

As an idea we could have an example of a minlex solution grid

Code: Select all: 123456789457189623968327145214538976639271458785964312341892567572643891896715234 1st Band Row4 Rest of puzzle 123456789457189623968327145:214538976:639271458785964312341892567572643891896715234 Band:row4:row5-9 299:0027:639271458785964312341892567572643891896715234 123456789457189623968327145214538976..........85964312.41892567.72643891.9671.234 Band:row4:row6-9reduced 123456789457189623968327145214538976.............6..12.4.892.6..7..4............. 299:0027:...6..12.4.892.6..7..4.............

Possiby could be a reversable process

by **champagne** » Sat Apr 06, 2024 8:05 am

Hi coloin,

The idea is clearly to have a quick link from a given solution grid in min lexical form to it's number 1 - 5472730538 and reverse. This reduces the solution grid to 10 digits or 5 bytes in binary mode (33 bits).

The first constraint is to have common definition of the solution grids order and it will surely be the min lexical order of the ED solution grids.
This pushes to have either a copy of the catalog done with this constraint or a catalog builder giving it.

The next step is a way to compress using files as small as possible. The 50G file proposed by mladen is a start (I did not check if it fits with the sort constraint.

Where we are, we are considering an option using

an index made of the first four rows
the rest to define, still open

Some comments on the "row4" index and the next one.
We could think of a second index having the valid rows 1-4 as number f entries.

coloin wrote:A post by holdout and blue 4-RowCover confirmed the number of 4-row partial grids as 4051084.

if my understanding is correct, this is similar to the number of 416 for the ED bands 1, but as several bands 1 have no ED solution grid in min lexical form (and some of them less tan 10), many of these 4 051 084 will have no solution grid attached. The final count could be around 1 million or less,
Then we cam think of a second index with the same number of entries.

coloin wrote:its not clear from the thread what the actual number of row 4 completions there are .. and r4c1 is resticted to a 2 ... [EDIT it might well be 7666]

of course the number of ways to have a row 4 with a specific band isnt 8! .. its more like eg 1x6x4x5x3x3x2x1x1 ~ 2000
in band 1 , with 1007170 grids there were only 126 different row4s,
In band 299 with 133302 grids there were 1994 different row4s

The number of theoretical ways to have the row 4 is not so important, it is a short to describe the first 4 rows in the index table, 8!=40320 seems reasonable for a quick decompression of the row4.
And your examples go in the direction of my previous statement
band1 has 108 isomorphism,
band 299 is already far in the sorting sequence (no isomorphism)

coloin wrote:
Compressing the whole file strategically , and reducing the data to be compressed go together i suppose.
.......
the 416 can be stored
the row4 for a specific band can be generated on the fly too - although there are isomporphic reductions [ as in band 1] - so probably could be stored as an actual.

As an idea we could have an example of a minlex solution grid
Code: Select all
123456789457189623968327145214538976639271458785964312341892567572643891896715234 Rest of puzzle rows 5-9 123456789457189623968327145:214538976: 639271458785964312341892567572643891896715234 Band:row4:row5-9 299:0027:639271458785964312341892567572643891896715234 123456789457189623968327145214538976..........85964312.41892567.72643891.9671.234 Band:row4:row6-9reduced 123456789457189623968327145214538976.............6..12.4.892.6..7..4............. 299:0027:...6..12.4.892.6..7..4.............

Possiby could be a reversable process

using index an only actual ED solution grids, the rest after row 4 is completely defined with rows 5-8 excluding box9. This is 32 digits to optimize (eg r789c1 are known when band 2 is defined).

by **champagne** » Mon Apr 08, 2024 8:12 am

coloin wrote:in band 1 , with 1007170 grids there were only 126 different row4s,
In band 299 with 133302 grids there were 1994 different row4s

Hi coloin,

more on this.

I made a test using my code for the 17 clues scan. The sequence is not the same, but the results have a similar logic.

I run
the band 1 (third, index 2 on my side)
the band index 6 on my side, the first band with no automorphism,
the band index 300 (no automorphism) close to your second example.

The run ties are respectively 22;1288and 162 seconds with my old computer.
The number of "rows 4" are expected to be close to yours in the first and last case and close to all patterns for the band index 6.

This means that one possible solution with a response below 0.1 second per solution grid could be to have no file per solution grid, but to start from the index per row4 and to use the builder to find the rank of the given solution grid.

I hope to have he time this week to finish and test the code.
Note: in such a case, the index would likely be an internal table of the code.

by **coloin** » Mon Apr 08, 2024 10:01 am

The 9! [362880] is reduced by a factor of ~ 1/9 x 9 because row1 is always 123456789, and by ~ 1/8 x 2 as the 4 and 5 are always starting row2.
This reduces the possibilities to exactly 102550.

Of these 14568 were of the form 2xxxxxxxx

I looked at several milllion minlexgrids and noted the individual row4s. FWIW I found 10163, but there may be a few more...

Indeed the number of valid row4s is specific for each of the 416 bands [actually specific for each of the 44 gangsters].... but it probably is < 2000 for each gangster
I dont think gsf employed this reduction as he generated from the 416, but maybe he did......

But I think compressing the solution grids of Min lex Band1/Row4 combinations is a way forward.

Of course the pruning still needs to be done....

by **coloin** » Tue Apr 09, 2024 2:49 pm

champagne wrote: The idea is clearly to have a quick link from a given solution grid in min lexical form to it's number 1 - 5472730538 and reverse.

maybe a solution to the mapping of grids to the #5e9
maybe the solution is to process like gsf has done, but not actually generate all the grids....
only the final part of the grids are pruned and can be identified as a minlex grid.

Classification of the look up tables which I can link to

Code: Select all: #1# 416 Band1 [ though only 401 are used] [the vast majority of minlex solution grids use initially bands 001-299] #2# 14568 Row4 [ though only 10163 + are known to be used ] [120-2000 for each band/gangster] #3# 720 c1r56789 [ though only 124 are extrapolated to be used] [each of the 4 options - 6,7,8 or 9 @r3c1 uses 100 or so]

take a relatively high up in the order min lex grid

Code: Select all: <-----Band1---------------><--Row4->x........x........x........x........x........ ....................................300000000500000000700000000800000000900000000##Col1 123456789457189236689327514278964351396215478514738962765842193832591647941673825##Chosen Minlexgrid This grid can be partially identified : as band-048 Row4-9960 and Col1-010. [ from the look up tables] #1# #2# #3# Band1 #Row4 #c1r56789# ---------------------------- #048# #278964351# #35789# 15266 sols [not all minlexgridsols] ------------------------- #048# # 09960# # 010# #416# # 14568# # 720#

Essentially we have a "Flag" pattern which is ordered minlexographically...

Code: Select all: +---+---+---+ |123|456|789| |457|189|236| - Band1 |689|327|514| +---+---+---+ |278|964|351| - Row4 |3..|...|...| - |5..|...|...| - +---+---+---+ - Col1 |7..|...|...| - |8..|...|...| - |9..|...|...| - +---+---+---+ 15266 sols which were all ED [ all the transformations apart from reflection are defined]

Pruning ..... by minlexing the 15266 6to minlex grids and then comparing with the original solutions, 11987 of the 15266 were minlex solution grids. This all took a few seconds or less processing time.

The solution grid can therefore be mapped to an extent.....

Code: Select all: 123456789457189236689327514278964351396215478514738962765842193832591647941673825 was # 9450 out of 11987

This solution grid can be identified as 048/09960/010/09450

Conversely, generating all of band 048 which took over an hour, splitting it into over 16 manageable files of 4M each, with a bit of effort I found the same grid at band 048/560890393 ! :geek:

Perhaps if this has no flaws the #2 and #3 look up combinations could be confirmed ... but defining all the gaps to elucidate the grid number maybe isnt actually required and would be quite a task :roll:

by **champagne** » Tue Apr 09, 2024 9:26 pm

Hi coloin,

I have surely a proposal in my head, but I was short in time to finish and test my draft. I should have more time in the next days to work on it.

coloin wrote:
champagne wrote: The idea is clearly to have a quick link from a given solution grid in min lexical form to it's number 1 - 5472730538 and reverse.

maybe a solution to the mapping of grids to the #5e9
maybe the solution is to process like gsf has done, but not actually generate all the grids....
only the final part of the grids are pruned and can be identified as a minlex grid.

Surely, the pruning comes mainly after the rows 4 " accepting the idea that the start is one of the 416 min lexical patterns".
This is not 100% true. You can apply the auto morphs filter to the band 4. This is enough to get only the 126 rows 4 that you found for the band 1

And if the index on "band1 plus row4" valid gives you all valid minlex solution grids attached, you have the start for the pruning of any given branch. So for me, this index can only be done out of the catalog builder.

coloin wrote:Classification of the look up tables which I can link to
Code: Select all
#1# 416 Band1 [ though only 401 are used] [the vast majority of minlex solution grids use initially bands 001-299] #2# 14568 Row4 [ though only 10163 + are known to be used ] [120-2000 for each band/gangster] #3# 720 c1r56789 [ though only 124 are extrapolated to be used] [each of the 4 options - 6,7,8 or 9 @r3c1 uses 100 or so]

No basic problem for the 2 first "lookup" tables, the third one is not in the minlex sequence. I discarded my stack option, we have the same problem here.

In fact, in what I have in mind,

The third part will be the code of the catalog builder giving on the spot the lilst of attached solution grids
The second lookup table contains only used rows 4 for each band1. the theoretical possible patterns will be used to describe the rows 4 in a compressed form and by the solution grid compressor to give the short to use in the lookup.
The first is just a table giving for each of the 416 band1 the number of rows 4 stored in the second table.

A key point is the number of "band1;row 4" existing in the catalog. I am sure that it is far below the 4 051 084 number of classes given by blue, but I need some more days to have a first estimate of it
And for sure, I have to verify that the pruning of the rest (after row4) can be done in less than 0.1 second.

by **coloin** » Tue Apr 09, 2024 11:55 pm

champagne wrote:No basic problem for the 2 first "lookup" tables, the third one is not in the minlex sequence. I discarded my stack option, we have the same problem here.

im pretty sure im just repeating what gsf did except he stopped at the end of band1 and i am generating and pruning furthur down the text sting with another row and another column.

I think you were right with the stack / column option ... i only tested for one of the 720 ways to fill in col1 after the 2 at r4c1, and it is in min lex order, [1462]35789, not [1462]35879 for example.

However ive overlooked furthur constraints and there are only 40 ways [ not 720, not 120] to fill in column 1 in minlex grids ! :oops:

Hidden Text: Show

Even more, with Row4 having starting 278xxxxxx as here.... this means there are only 3 ways to fill in col1 min lex

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

checking this, sol count for this band1plusrow4 is 530,000 sols , 3 x 15000 x 12 = 540000

champagne wrote:A key point is the number of "band1;row 4" existing in the catalog. I am sure that it is far below the 4 051 084 number of classes given by blue, but I need some more days to have a first estimate of it

I think you will find my numbers are aproaching the true figures, but as you say the absolute number is maybe less relevant as a zero solution / conflict costs very little in time !

champagne wrote:And for sure, I have to verify that the pruning of the rest (after row4) can be done in less than 0.1 second.

there are quite a lot of solutions to a band1 plus a row4, [~500,000] but this is inflated by x11 isomorphs which cant be minlex [2x6] !!! But if there are only 3 ED col1 I'm sure that the process is fast !!

All the minlex grids for that specific band1+row4+col1 i think are found - of course its easy to make an error and overlook major flaws... !!
I should go back and check the grids that I generated in the file containing 048/560890393....

by **dobrichev** » Wed Apr 10, 2024 10:40 am

Scanning the minlex grids catalogue for row4, regardles of the leading band, gives 10375 distinct values.
The result row4, number of occurences looks like

Code: Select all: 214365897 2603739 214365978 2455784 214367598 1157115 214367895 1567913 214367958 1904249 214368597 1540637 214368957 2042471 214368975 1814422 214375698 1853584 214375896 1032378 ... 298764315 401114 298764351 452061 298764513 380847 298764531 51201 298765134 28658 298765143 310825 298765314 369433 298765341 444253 298765413 421793 298765431 32568

The most frequent values are

Code: Select all: 231564978 3845370 231564897 3810781 231645897 3792232 231645978 3714482 214568397 3683145 214695378 3616850 215648397 3573586 234615897 3567672 215864397 3534200 234615978 3495857

and some of the less frequent are

Code: Select all: 246175893 1 276135894 1 276135948 1 278135946 1 279143865 1 279148365 1 279164853 1 286173945 1 286174395 1 286174593 1

by **champagne** » Wed Apr 10, 2024 11:55 am

Hi mladen,

I don't know if you have in hands the catalog sorted in the minlex sequence. The count that I expect to give in the next days in the number of occurrences (band1,row4) in such a sequence.
If you have such a file, it could be a way to cross check the count.

In fact, a catalog having the row 4 in the right sequence is likely enough to produce the right count.

by **dobrichev** » Wed Apr 10, 2024 12:58 pm

Hi Champagne,

Yes, I have the catalogue in hands and can confirm your results. Do you expect table in form <band number>, <row4 values>, <number of grids>?

It isn't clear to me what will be the next step after you get these lookups.

Clearly large sets of records, each consisting of previously binary compressed information, couldn't be effectively compressed later. For practical purposes, as JPF already mentioned, keeping puzzle lists as text in minlex in sorted files gives very good compression using standard zip.

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.

by **champagne** » Wed Apr 10, 2024 1:24 pm

dobrichev wrote:Hi Champagne,

Yes, I have the catalogue in hands and can confirm your results. Do you expect table in form <band number>, <row4 values>, <number of grids>?

this is exactly what I want to get as first output of my code. The idea is then to put it as internal table with a double index

count of row 4 per band 416 as first index
list of row4s with the count of solution grids as second index.
my bet is that the second index will contain around 1 million items, but more could still be acceptable for an internal big table.

dobrichev wrote:Hi Champagne,
It isn't clear to me what will be the next step after you get these lookups.

At this point, again something to verify, the catalog builder will take some milliseconds to produce the list of attached solution grids.

If the target is just to get the catalog entry number, we have one solution grid in minlex morph to transform in the solution grid ID. Having the start point from the lookup file, we run the builder with the first 4 rows till the expected solution grid and we get:
Either a pointer for an internal treatment on the catalog (likely what used "Mathimagics") or a reduction of the solution grid to a 10 digits/ 33 bits value.

But this can also be a way to deliver pieces of the catalog with different ways to show the last 5 rows.

by **coloin** » Wed Apr 10, 2024 1:52 pm

Glad to have that analysis done. Very good to get 10375 row4s !
looking at my results it appears the row5 adds more minlex grids
so, removing a tier and grinding out the possible col1s [ 3 in this case]

Code: Select all: +---+---+---+ |123|456|789| |457|189|236| |689|327|514| +---+---+---+ |278|964|351| |3..|...|...| |5..|...|...| +---+---+---+ |7..|...|...| |8..|...|...| |9..|...|...| +---+---+---+ 15266 sols +---+---+---+ |123|456|789| |457|189|236| |689|327|514| +---+---+---+ |278|964|351| |3..|...|...| |9..|...|...| +---+---+---+ |5..|...|...| |7..|...|...| |8..|...|...| +---+---+---+ 13284 sols +---+---+---+ |123|456|789| |457|189|236| |689|327|514| +---+---+---+ |278|964|351| |5..|...|...| |9..|...|...| +---+---+---+ |3..|...|...| |7..|...|...| |8..|...|...| +---+---+---+ 15852 sols 44402 sols from 44400 different grids [ 2 duplicate minlex solution grids. ]

of these solution grids there were 35042 minlex solution grids. [the others were larger] [so called pruning]

my chosen bandplusrow4 / grid

Code: Select all: 123456789457189236689327514278964351............................................................. 123456789457189236689327514278964351396215478514738962765842193832591647941673825 was 19934/35042

therefore the correct classification would be [ losing a tier] :!:

048/09960/019934

the #row4 number wuld be updateable as its 09960/14568, somewhere near 6700 / in list of 10375

by **coloin** » Wed Apr 10, 2024 2:51 pm

dobrichev wrote:It isn't clear to me what will be the next step after you get these lookups.

well a stepwise progression of

puzzle -> solution grid -> minlexsolutiongrid -> band/row4/number -> 5e9 number

This might give clarity in many applications... no ?

maybe the last step isnt necessary though

by **dobrichev** » Wed Apr 10, 2024 3:48 pm

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 0 214367598 49776 44554 0 214367895 94330 40523 0 214368597 134853 45278 0 214368975 180131 41310 ... 0 247691835 1007060 27 0 247835691 1007087 7 0 247935618 1007094 1 0 267348591 1007095 49 0 267591348 1007144 22 0 267591834 1007166 3 0 267834591 1007169 1 1 214365897 1007170 49461 1 214365978 1056631 48547 1 214367598 1105178 46139 ... 391 285317964 5472730470 1 392 245918376 5472730471 1 392 295713468 5472730472 1 393 231564897 5472730473 2 393 231645897 5472730475 3 393 231648597 5472730478 2 393 234615897 5472730480 2 393 234695817 5472730482 1 393 239645817 5472730483 2 393 239648517 5472730485 1 393 241573896 5472730486 1 393 281643597 5472730487 1 393 284615397 5472730488 1 394 231645897 5472730489 2 394 231864597 5472730491 4 394 231874596 5472730495 4 394 248615973 5472730499 1 395 231564978 5472730500 4 395 231645978 5472730504 6 396 285793146 5472730510 1 397 281537946 5472730511 1 397 285137946 5472730512 1 397 285713946 5472730513 1 397 289564173 5472730514 1 398 231564978 5472730515 4 398 231578946 5472730519 1 398 231645978 5472730520 7 398 231978546 5472730527 1 398 234178965 5472730528 1 398 234817965 5472730529 1 398 235178946 5472730530 1 398 235817946 5472730531 1 398 235964178 5472730532 1 398 239564178 5472730533 1 399 268174593 5472730534 2 399 268741593 5472730536 1 400 274538196 5472730537 1

Generation took 25 minutes.

If you have ordered list of millions of minlexed grids the mapping time will be in the same order (full catalog scan). For shorter lists binary search could skip some regions and reduce the time.
Mapping unordered lists (binary search for each grid) is of academic interest but I will stop here.

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.

by **champagne** » Wed Apr 10, 2024 3:52 pm

coloin wrote:
dobrichev wrote:It isn't clear to me what will be the next step after you get these lookups.

well a stepwise progression of

puzzle -> solution grid -> minlexsolutiongrid -> band/row4/number -> 5e9 number

This might give clarity in many applications... no ?

maybe the last step isnt necessary though

in your puzzle -> solution grid -> minlexsolutiongrid -> band/row4/number
"number" is the count of solution grids attached.
I don't see a way to skip the -> 5e9 number.
If the user is waiting for the list of solution grids attached, the problem is very similar but the constraint of the order of the sub list does not exist.

The New Sudoku Players' Forum

High density files for solution grids and 18 clues puzzles

Re: High density files for solution grids and 18 clues puzzl

Re: High density files for solution grids and 18 clues puzzl

Re: High density files for solution grids and 18 clues puzzl

Re: High density files for solution grids and 18 clues puzzl

Identifying Minlex solution grids

Re: Identifying Minlex solution grids

Re: Identifying Minlex solution grids

Re: High density files for solution grids and 18 clues puzzl

Re: High density files for solution grids and 18 clues puzzl

Re: High density files for solution grids and 18 clues puzzl

Re: High density files for solution grids and 18 clues puzzl

Re: High density files for solution grids and 18 clues puzzl

Re: High density files for solution grids and 18 clues puzzl

Re: High density files for solution grids and 18 clues puzzl

Re: High density files for solution grids and 18 clues puzzl