The New Sudoku Players' Forum

[champagne]

Thanks blue.

my priority was the 4_4_27 file that I am checking.
I have 7876 4_4_27, you have 7866

Likely a missing clearing for the magic40 on my side,

I'll compare the 2 files this day.

EDIT stupid typo error somewhere, I had 7866 as well

[JPF]

I have 7876 4_4_27, you have 7866

I'm ok with 7866

JPF

[champagne]

The 4_4_27 issue is not sleeping. (is there any new 17 with that pattern)

I have now a stable code based mainly on

_ some code delivered by blue through pm filtering all "isomorphs" (see earlier in that thread)
_ a brute force based on the code posted here
by user zhouyundong_2012.

both are merged in a single program processing one piece of the field.

The entry is the file containing the ED patterns to process
3 parameters define
the start pattern number and the last pattern to process
the gangster to apply
The program deliver "primary puzzles" that must still be expanded as explained earlier in that thread

To-day my estimate is that
more than 10% of the task has been covered
with my own resources, the task should be finished in January 2014.
(but my deadline is mid January 2015, then end of march 2015 at best)

Anybody having cycles to share the burden is welcome

Another issue is not yet fully covered.

Starting from the "primary puzzles" we have to
expand each primary to all puzzles equivalences for the gangster used
find if 17 puzzles exist for that 4_4_27 puzzle.

For the second issue, we recently used an option of gridchecker doing much more than required, but too slow.

I am investigating to get a better option with so far 2 possibilities:

a) another process in gridchecker that must be reshaped for a friendly use
the target would be about 100 puzzles processed by second
b) a program that blue can share processing several puzzles by second.


PS: I think blue already wrote that, but the process is very sensitive
1) first and mainly to the gangster applied
2) to the pair gangster/pattern
the run time can vary from 1 to 5000 and may be more between the best and the worst pair

PS2: The way the brute force is written, it has been very easy to create a reduced code processing only bands 2 and 3 after the initial settlement of the gangster, this gives on the paper a 20% (minimum) improvement

[champagne]

Fresh news on the 27 + X + Y valid puzzle search for a possible 17 clues.

Several options have been investigated.

blue proposed a very general code giving amazing good results.
Mladen dobrichev has also a very good solution.

Both can answer for several puzzles (tens of puzzles) per second.

But the mot promising road is to use that very common property.

Most of these puzzle (if not all) have

. in total more than 15 UAs of size 2
. among them 8 or 9 disjoint UA's

Finding all UA's of size 2 require (27*26/2 = 351 ) calls of the brute force with about 33 given, a very fast process
The number of combinations solving disjoint UA's is not that big 2^n with n= 9 in general in a 4+4+27 pattern

I tested a 8396 file of 4+4+27 valid puzzles

in 12 seconds (700 puzzles per second) on a very busy computer I could clear nearly all the file (already checked by others as having no 17) just on that criteria.

a little more than 300 additional calls to the brute force were done and 6 puzzles were not cleared with the limited code used.

Normally, that filter plus blue's code give the answer to that key issue.

[champagne]

Some months later ...

Scanning of the 4+4+27 and 3+5+27 is now fully covered.

4+4+27 raw results have been cross checked by blue and no new 17 appeared
3+5+27 raw generation is over, not yet cross checked by blue and no 17 came on my side.

So, out of known 4+4+27, the maximum number of clues in a band/stack to have a 17 clues puzzle is 8.
The next steps would likely require a significant improvement in the performance of the program producing the raw results (ED pattern against gangster).
Optimization of the brute force cut in the run time by 18% (rough estimate), much more should be done to start a 3+6+27 or a 4+5+27 search

BTW did anybody counted the number of ED patterns 3+6+27 and 4+5+27?

[Serg]

Hi, champagne!

BTW did anybody counted the number of ED patterns 3+6+27 and 4+5+27?

I calculated ED maps and ED patterns for 3+6+27 and 4+5+27 clues-by-band distributions.

Code: Select all

distrib. maps patterns

3+5+27   38   20734
4+4+27   26   12998
3+6+27   51   61079
4+5+27   57   90897

Serg

[champagne]

I calculated ED maps and ED patterns for 3+6+27 and 4+5+27 clues-by-band distributions.

Code: Select all

distrib. maps patterns

3+5+27   38   20734
4+4+27   26   12998
3+6+27   51   61079
4+5+27   57   90897

Serg

Hi Serg,

I did not work meantime on that topic, so it's good to have a first shot.
As you gave as reference the count for ED 3_5 and 4_4, we have an order of magnitude of the ratio 9clues/8clues.

The final count for 3_5 and 4_4 has been given by blue and jpf after the magic 50 filter has been applied. I worked on a file of 8209 ED pattern for 3_5_27 and 7866 ED pattern for 4_4_27.

The same filter should be applied on the 3_6_27 and 4_5_27.

If we keep the same global ratio, we can expect 5 times the count of ED patterns to expand. Starting that task requires a significant improvement in the run time. My 20% gain in the brute force would not be enough.

[blue]

Some months later ...

Scanning of the 4+4+27 and 3+5+27 is now fully covered.

4+4+27 raw results have been cross checked by blue and no new 17 appeared
3+5+27 raw generation is over, not yet cross checked by blue and no 17 came on my side.

The "3+5+27" results have been cross checked now ... same result ... no new 17

BTW did anybody counted the number of ED patterns 3+6+27 and 4+5+27?

My results matched those of Serg.

The final count for 3_5 and 4_4 has been given by blue and jpf after the magic 50 filter has been applied. I worked on a file of 8209 ED pattern for 3_5_27 and 7866 ED pattern for 4_4_27.

The same filter should be applied on the 3_6_27 and 4_5_27.

Applying the "magic 40" filter, reduced the viable pattern counts to 27692 for 3+6+27, and 67659 for 4+5+27.
This is around 6x the count for the "8"+27 cases.
With the extra clue cell, the work required for an exhaustive search, would be up by what (?) ... a factor of 25-30 ??

[champagne]

With the extra clue cell, the work required for an exhaustive search, would be up by what (?) ... a factor of 25-30 ??

which is far of the area of realistic tasks with to-days tools.

Even if new 17 can appear, the price to pay here is to high.

[Serg]

Hi, people!
Just to show ultimate picture - how many patterns one needs to check to do exhaustive search for 17-clue puzzles. (No filtering was applied.)

Code: Select all

distrib. maps   patterns

3+5+27   38     20,734
4+4+27   26     12,998
3+6+27   51     61,079
4+5+27   57     90,897
3+7+27   64    155,054
4+6+27   76    277,435
5+5+27   46    169,258
5+6+27  104  1,056,939
----------------------
Total        1,844,394


champagne and blue checked approx. 2 % of all possible patterns. Not so bad numbers ...

Serg

[champagne]

Hi, people!
Just to show ultimate picture - how many patterns one needs to check to do exhaustive search for 17-clue puzzles. (No filtering was applied.)

Code: Select all

distrib. maps   patterns

3+5+27   38     20,734
4+4+27   26     12,998
3+6+27   51     61,079
4+5+27   57     90,897
3+7+27   64    155,054
4+6+27   76    277,435
5+5+27   46    169,258
5+6+27  104  1,056,939
----------------------
Total        1,844,394


champagne and blue checked approx. 2 % of all possible patterns. Not so bad numbers ...

Serg

Hi Serg,

Interesting table.

The last line is about 55% of the total.

Let us assume that we have covered (in any way) the other lines. Then, no new 17 can be found with a band or stack distribution other than 6 6 5.

Any pattern having more than 6 clues in the "stack x {bands 1;2}" can be discarded

For other patterns, we know with a possible +-1 count the residual count in the "27 clues band"

IMO in such a case, the right process would not be a 27+X+Y scan, but a scan of each ED pattern with the residual count.

Just an idea, I did not work so far in that direction, but this is not so far from the magic 50 filter concept.

[champagne]

Hi, people!
Just to show ultimate picture - how many patterns one needs to check to do exhaustive search for 17-clue puzzles. (No filtering was applied.)

Code: Select all

distrib. maps   patterns

3+5+27   38     20,734
4+4+27   26     12,998
3+6+27   51     61,079
4+5+27   57     90,897
3+7+27   64    155,054
4+6+27   76    277,435
5+5+27   46    169,258
5+6+27  104  1,056,939
----------------------
Total        1,844,394


champagne and blue checked approx. 2 % of all possible patterns. Not so bad numbers ...

Serg

As said in another thread, I am working on quite a new process to continue that task.

So far, the improvement ratio is attractive enough to have a chance to cover at minimum 3+6 and 3+7, but likely 4+X.
I need some more days to give some preliminary results, but I am interested in 2 question:

Have anybody (likely blue have them) the corresponding file after reduction using the magic crossings

Is it possible to have the 3+6 and 3+7 reduced file available for downloading. This would save time on my side, I have still some work on the new process.

[champagne]

I finished my first test with amazing results.

With the first draft of the new code, it took about 10 hours * 9 cores to find the "native solutions 27 + 5 + 3" against the gangster index 34, one of the worst cases.

With the original code, the same tack lasted months.

I have still to check that no solution is missing and to verify the code for gangsters having automorphisms creating redundancy in that phase, but I am now convinced that this is true breakthrough in the process.

I am preparing some comments on the process applied that I'll load on my website (easier for maintenance).

[champagne]

Having so far small interest shown to that topic, I delayed the uploading of the process description.

I am running the last test before the start of the 27+6+3 case

I have 27692 ED patterns after magic 40 against 61079 found by Serg with no filter

This can be compared to the 27 + 5 + 3 case cross-checked by other sources where we have 8209 ED patterns out of 20 734.

In one or 2 days, I'll have an better idea of the run time ratio 27+6+3 against 27+5+3 but the last tests let's expect something better that the 30:1 forecast.
I hope to have about 15:1 with identified sources of improvement to implement

[champagne]

One week later, I have nearly covered the generation of 27+3+6 for one of the 2 worst cases : the gangster index 34.

Extrapolation is always difficult with that problem, but I hope to cover the full 27+3+6 generation in 2 months with the power I can use for that task. (in one week, I should be in a position to work with 15 cores around 3.5 Mhz)

We'll then know whether new 17 clues appear in that lot.