The New Sudoku Players' Forum

by **champagne** » Sun May 19, 2024 8:34 am

Another example with the gangster index 34, expected to fit with 30 of the 416 bands
here is my list of the results, sorted on the increasing index of the band corresponding to the fill

Code: Select all: 158239674247156389369478125;34;13,37 157239684248156379369478125;34;11,39 158239674249176385367458129;34;16,60 149276385258139674367458129;34;5,62 148256379257139684369478125;34;3,95 159276384248139675367458129;34;18,98 147256389258139674369478125;34;1,114 148239675259176384367458129;34;4,117 169258374257436189348179625;34;29,164 168259374257436189349178625;34;26,165 159238674247156389368479125;34;17,172 169478325257139684348256179;34;28,179 167458329248139675359276184;34;21,180 158476329247139685369258174;34;14,184 169258374247139685358476129;34;23,185 147256389259138674368479125;34;2,188 169478325258139674347256189;34;30,190 158476329249138675367259184;34;15,199 148256379267439185359178624;34;9,200 167259384249138675358476129;34;22,201 147256389268439175359178624;34;6,202 147239685269158374358476129;34;7,247 149238675267159384358476129;34;10,269 167458329258139674349276185;34;25,270 147256389269438175358179624;34;8,295 167259384258436179349178625;34;24,310 168479325259138674347256189;34;27,312 157438629249176385368259174;34;12,365 157438629268159374349276185;34;19,384 159276384268439175347158629;34;20,368

we have the 30 bands, with only one fill for each of them.
It seems the the code works well

by **champagne** » Sun May 19, 2024 1:40 pm

first gangsters index 0-5

Hidden Text: Show

by **champagne** » Sun May 19, 2024 1:44 pm

fills gangsters index 6-23

Hidden Text: Show

by **champagne** » Sun May 19, 2024 1:46 pm

fills gangsters index 24-43

Hidden Text: Show

by **champagne** » Tue May 28, 2024 6:48 am

slow progress here, but the quick identification of a gangster with the parameters to morph known solutions is in progress
I updated the repository of the catalog builder with the current status of the code.
I hope to have to draft for the 44 gangsters in the next 2 weeks.

repository for the minlex solution grids builder and services

by **champagne** » Sat Jun 08, 2024 2:29 pm

The target is to have a process replacing the loops testing all morphs of a given non minlex gangster to find the minlex morph and the mapping.
Next step will be to use the known valid fills of each gangster in minlex morph to speed up the last step of the catalog builder. This step is part of the direct link {solution grid rank => solution grid minlex morph} and reverse, so improving the last step will lower the average response.

The quick identification uses the known list of gangsters in minlex morph (see the first post.)

Here, to achieve a quick match of the “current status” to the “gangster index”, we use a “bit fields” view of the analyzed gangster.
Take as example this morph of the gangster 11 (index 10)

Code: Select all: 579 368 124 689 457 123 789 456 123

For each column, we have three bit-fields for the first one 579, it would be

Code: Select all: ....1.1.1 a digit bit field (digits 579) 1........ a column bit field, here first column 1.. a stack bit field here first stack.

The first task will be to merge columns having identical “digits bit-fields”. (always different stacks)
Here we would get this summary

Code: Select all: Digits columns stacks 111...... .....1..1 .11 ....1.1.1 1........ 1.. ..1..1.1. .1....... 1.. 11.1..... ..1...... 1.. .....1.11 ...1..... .1. ...11.1.. ....1.... .1. ......111 ......1.. ..1 ...111... .......1. ..1

As a result, we get 6 classes of gangsters having respectively 3,5,6,7,8 or 9 items.
Here, the first item is for the 2 occurrences of the “123”
The classes with 3 items and 5 items have only one gangster each, the 2 at the top in the list in minlex order.
The class with 9 items has gangsters 20 to 44 of the list starting with gangster 20 (index 19)

The class with 7 items has 2 sub classes,
One with a “3 occurrences” + 6 singles
One with a 2x “2 occurrences” plus 5 singles.

Except for the last class, the existence of items with several occurrences gives constraints limiting the morphing possibilities. For the last class, more can be done if we consider the known list.

In the minlex morph of the 2 first stacks, we have 3 possibilities

Code: Select all: a) 123 456 789 124 357 689 (gangsters 20 to 39) b) 123 456 789 124 378 569 (gangsters 40 to 43) c) 123 456 789 147 258 369 (gangster 40)

The last gangster is easily identified.
For the other ones, analyzing where the pattern can be found gives in the same time sub classes and a limited number of cases to consider, usually with auto morphism making any case valid as start.

Another easy simple way to create sub classes is to count the number of possible ways to find the searched pattern, and to see if the last stack can be 125,126 or 128

Subject to a check of the code,

In the sub-group 20 to 39:

six gangsters (22,23,26,27,35,39) have only one occurrence of the pattern fitting with a), 2 of them with 125 in stack 3. In this group the mapping is quite simple.

Seven gangsters (21,25,28,31,33,34,37) have 2 different ways to build the pattern a)
The rest (seven gangsters) have 3 possible ways to build the pattern.

In the sub-group 40 to 43, one gangster has only one possible pattern, one has 2 and 2 have the 3 possible ways to define it..

The draft of the mapping is done except for the last class with 9 items.

by **champagne** » Wed Jun 19, 2024 7:42 am

Slow progress, but good results.

The first draft for the gangster mapping is now ready.
To get an idea of the average run time for the mapping, I used a reverse morph of the gangster and made 10 000 calls to the mapping process.
The total run time on my old I7 is 74ms giving an expected average 7.2/44 microseconds per gangster

Next step is to apply this to all bands 1+2 coming in the min lexical catalog builder.

by **champagne** » Thu Jun 27, 2024 2:15 pm

The first test running in parallel the catalog builder and the version using the gangsters possible fills showed bugs in the gangster mapping.
I changed the code for part of the gangsters and fixed the bug.

The first test running the min lexical grids with the first band in the range 400-415 is now correct (28 valid fills).
Next step will be to run in parallel the full catalog to check if we get the same results everywhere.

by **champagne** » Sat Jun 29, 2024 7:45 pm

One more step covered (repository updated)
parallel process for the last 408 rows 4

Both process send the same 697 min lexical solution grids
3.8 seconds with the classical process
1.1 second for the process using the gangster valid fills

this is an area where a good improvement was expected, but the result is over expectations.

Several bugs have been fixed in the gangsters mapping process.
Next test will cover more solution grids at the end of the catalog.

Using the gangsters valid fills, a full catalog should be built far below one day core.

by **champagne** » Sat Jun 29, 2024 7:54 pm

I just run the last test for to-day

last 2408 rows 4 => 4460 solution grids
old process 32s8
new process 7s8
(with the print option)

one or 2 days more for a big test.

by **champagne** » Mon Jul 01, 2024 9:39 pm

good news with the last test producing the bottom 39390 min lexical solution grids of the catalog.
both process give identical results (having fixed 2 bugs in the gangster mapping)

249 seconds with the classical back tracking process,
47 seconds using the gangster valid fills.

We could still have residual bugs in the gangster mapping, but not many.
I'll start wider tests in the next days.
If the ratio old/new remains stable, a full catalog could be built in less than half a day/core.
Most important, this lowers the response to the match solution grids <=> rank

I still have in mind a remark of "coloin" to test after :
A small number of "one band" in min lexical morph have the start 123456789456.
This open the door for an early back track when the row 5 is filled.

by **champagne** » Wed Jul 03, 2024 9:41 am

This could be the last post for this thread.
The mapping of the 44 gangster worked without bug for the entire catalog, so the code can be seen as valid.

The test (100000 times for each of the 44 gangsters) was covered in 95 milliseconds using my desk old i7.
This gives an average mapping done in 9.5/44 micro seconds.
For a random entry of a valid gangster, the results should be in the same range.
Note: the entry must be a valid gangster

The mapping is done to morph the valid fills of a gangster to the entry.
To be used in the minlex catalog, the morphed fill must still be ordered on the fist column.

Next comments will come in the minlex catalog thread.

by **Sojourner9** » Tue Jul 16, 2024 9:14 pm

Hi champagne,
There is another way to do this that might be more efficient. Although it will require going out of your comfort zone a little, or not. But I can help.
Use an approach like kjellg used with his Cmatrix, see ed.c .

In his case he counted Nmax in 2 seconds, but the same approach can be used here.
He treated his stacks different than his bands, sort of a warp and weft analogy.
He has an three dimensional array, hiding as two dimensional 280x280 array representing three column boxes in your band 3.
The first box is fixed with anything you like, you can use 123, 456, 789 or 147, 258, 369, whatever you want for the column data, because it only exists in the mind.
The other two boxes are the are the indexes into the array.

There are 9 pick 3 = 84 ways to fill a boxLine, your mini-column.
There are 280 ways of combining the boxLines to make a box which represents only the column or row portion of a box.
There are 36 turns for each box, which are again the 280 boxes only for the other axis.
There are 280x56=15680 ways of filling threeBoxes which represents the row data you are asking about.
Now since you have colB7 fixed you only need 36x56 threeBoxes and each threeBox has 36x36 turns for colB8 and colB9, so 2,612,736, that sounds familiar.
What do we put in the array, what is the data? In kjellg case he put GangOf44 numbers in each, knowing that each would have a fixed count.
You can have the array contain counts or you can have each be another array, where the number of elements of the array is the same as the count you would have used.
If the goal is to create and use the content then use the array, if the goal is just to sum counts then use integers.
Variable size arrays are not easy in C.

The cool part was how he accesses this array. if he has a colB7 that is not the expected value then he just creates a relabel map that will change what was expected to what he needs.
Then he uses the relabel map to relabel the symbols in colB8 and colB9 which pre-adjusts the input to the array. Now he accesses the array as though it were the desired colB7.
If it were me, I would fill each element of the array with all the threeBoxes that satisfy column requirements.
This will likely require relabeling the resultant threeBoxes as well when I read them out.
You can put what you deem best in the arrays. This might take 10 seconds to preloading the table.
He went through some amount of work getting the gangOf44 into the array but for me it was easier.
knowing the 36 turns for colB7 I just went through the 36x56 threeBoxes and the turns for rowB8 and rowB9 and appended that threeBox to the array at the address described.
Note that there are 6x ways of reordering the band as the threeBox looses the 6x redundency of a fixed grid. Your columns are likely fixed but ideally there would not be.

Also gsf software for enumerating Nmin is just a solver that starts with the first band filled with a a 416 member and then solves left to right, top to bottom on the remaining 54 cells.
He does some checks at cell 54 and 81. You might be able to find ideas there. He enumerates Nmin much faster than I can using my methods.

My methodology says that any sudoku grid can be described by six threeBox number, 0 thru 15679, three for bands and three for stacks, it is just that not all combinations are valid sudoku grids.

Since each of the 280 boxes has 36 turn there are 10080 unique values that can occupy each box, B1 thru B9.
I haven't done this, but any sudoku grid can be described by 9 numbers, 0 thru 10079, but all combinations are not valid sudoku grids.
This last one is the weakest, mine is stronger but minLex is the best, I think.
I suppose you could describe any sudoku with 9 template numbers, as well.

by **coloin** » Tue Jul 16, 2024 10:56 pm

kjellfp wrote:Timing on a 1.4GHz Athlon: 0.046 + 0.124 = 0.170 seconds

This is for the 6e21 number .. and I wonder what timing it could be now with a faster processor !!

However I think the reason champagne is using the gangster method is to optimize the generation of all the ED grids 5e9 [not just the number]

In the thread we were investigating the task of ascertaining if we could go from
a puzzle -> a solution grid -> minlex solution grid -> minlex solution grid number e.g number 3,458,394,379 [in the minlex catalog]

If we fix clues so that Box 1 and the 1 template is fixed .... maybe the array method can be quickly used to calculate / enumerate the 5e9 grids [ plus ~100,000 isomorphs]
- but the isomorph problem would need to be addressed somehow.... as well as the isomorphs from the 9 boxes and 9 templates.

I think champagne is close to achieving the task

by **champagne** » Wed Jul 17, 2024 5:28 am

coloin wrote:
kjellfp wrote:Timing on a 1.4GHz Athlon: 0.046 + 0.124 = 0.170 seconds

This is for the 6e21 number .. and I wonder what timing it could be now with a faster processor !!

However I think the reason champagne is using the gangster method is to optimize the generation of all the ED grids 5e9 [not just the number]

In the thread we were investigating the task of ascertaining if we could go from
a puzzle -> a solution grid -> minlex solution grid -> minlex solution grid number e.g number 3,458,394,379 [in the minlex catalog]

If we fix clues so that Box 1 and the 1 template is fixed .... maybe the array method can be quickly used to calculate / enumerate the 5e9 grids [ plus ~100,000 isomorphs]
- but the isomorph problem would need to be addressed somehow.... as well as the isomorphs from the 9 boxes and 9 templates.

I think champagne is close to achieving the task

Hi coloin and Sojourner9,

I restart from coloin answer where the main comments are.
As coloin wrote, this thread is a tiny part of the big issue discussed here
http://forum.enjoysudoku.com/high-density-files-for-solution-grids-and-18-clues-puzzles-t42669-45.html

Producing the minlex catalog is not an issue, "gsf" did the first shoot long ago and several of us have the results in a disk file.

Generally speaking, Sojourner9 is on a "first shoot" or in enumeration mode.
I am more in "what to do of the results" or "how to use in the best way the results".

As wrote coloin, the first target was to see how to use the min lexical catalog of solution grids in a kind of "direct access".

This requires the quick link{ minlex solution grid <-> minlex solution grid number}
The process proposed is a kind of "virtual catalog". It uses the known catalog through indexes.

Here we have an alternative piece of code using the gangster in the last part of the process.
This require a quick mapping of a given gangster to the canonical form, Again something done using the known list of gangsters, and the valid fills for a gangster.
This is a general problem and this was the reason to open this thread.

coloin wrote:I think champagne is close to achieving the task

Basically, the draft is closed. is missing the cleaning and the switch to a DLL.
In fact coloin is somehow responsible of the current delay.
In the process, the check of the min lexical status requires in several places the mapping of a band to the min lexical canonical morph.
The current code has something not bad, relying again on the list of the known 416 minimal bands,
I think that a better code can be written in this critical area, with an open door to an early negative response if the band start is 123456789456. I am working on it.

I have other comments, but I'll do them in the main thread

The New Sudoku Players' Forum

solution grids per gangster

Re: solution grids per gangster

Re: solution grids per gangster

Re: solution grids per gangster

Re: solution grids per gangster

Re: solution grids per gangster

Gangster quick identification and mapping

Re: solution grids per gangster

Re: solution grids per gangster

Re: solution grids per gangster

Re: solution grids per gangster

Re: solution grids per gangster

Re: solution grids per gangster

Re: solution grids per gangster

Re: solution grids per gangster

Re: solution grids per gangster