The New Sudoku Players' Forum

[champagne]

Hi coloin,
I run the scan for the 478 pairs index 0+0 listed above.
all of them have valid 12. The smallest number of valid 12 is 57 in the following pair

123456789457189326689327154214598673398674512576213498731942865842765931965831247

This gives nearly no chance to do better with pairs having a bigger number of {valid band 1 * valid band 2}

EDIT : bad error on my side mixing run time in milliseconds and number of valid 12 clues
for the given band, the right count is 113
and the lowest count is 90 for the band

123456789457189326689327154214965873375814962968273415531648297742591638896732541

at the end, the chances to find a minimum 13 clues are still lower

[champagne]

I checked the 11811 pairs file with bands requiring 6 clues.
I put a filter to 300 valid 2 bands.
out of bands with twice the band index 0, I only have this one

123456789457189326698273514231798465574362198986541237349615872762834951815927643 1 1 102 valid bands 12

So, really, i can't see any chance to have a pair requiring 13 clues

[champagne]

Hi debblez,

A little more after Mathimagics last post.

In the LCT project, Mathimagics did a significant step using the vicinity search to detect solution grids having one or more 18's.
He had to stop when the yield was too bad.

If we know that we have only 49158 ED 17s, the number of ED 18 is huge. I don't have an estimate of this number, but Blue and Mathimagics made an estimate that about 20% of the solution grids have at least one 18. As an average 5 18s per active solution grid is a reasonable bet, We should at the end have more then 5 billions ED 18s.

Blue delivered (not public) a DLL performing well for the 18 search in a unique solution grid. Unhappily, we don't have the sources and Blue withdrew from the project for personal reasons.
I suggested to Mathimagics to apply an improved process derived from the 17 scan to restart the project. Blue's DLL performance showed that we had room for that.

The first challenge was to guess how blue improved his process and to try to reach a similar or better run time. This is a hard job. There is no true economical challenge in the results, so it remains a kind of hobby research on my side and nobody was prepared to work with me on this code.

2 month ago, we were very close to have a beta test with a code approaching the DLL performance (but working in the frame used to scan the 17 field).

Thinking with Mathimagics of the best process to apply in his project, we came to the conclusion that we should change one of the main constraints of blue's design.
This leaded to another change in the last part of the process and pushed to another strategy to implement it.

This is of small (if any) interest for the users, but any change in this process requires many many tests not easy to design.

As wrote Mathimagics, we have now in hands a sound basis, with a code that seems faster than Blue's DLL, I agree that in March, we should have solved several minor performance issues and be in a position to start a beta test version for Mathimagics's project.

I chose to make public the draft of the code. This is consistent with my age and the risks attached the way this is implemented.

I open months ago a separate thread
http://forum.enjoysudoku.com/17clues-v7-scan-18-clues-scan-t40329.html
to give more details on this package. After a long silence, I intended to come back in the next weeks with a summary of the changes in progress.

Out of Mathimagics's project, the source could be modified easily to produce some 18s having specific properties, as for example a distribution in box 222222222, something on which works our friend coloin.

[champagne]

.


Finally, I should note (again), blue's DLL remains the only method to test a grid explicitly for having an 18C. Without it, we would be totally in the dark - we would have no way to verify that champagne's code is correct. This project would probably be dead in the water without blue's contribution.

Cheers
MM

Gridchecker can do this, but is much too slow to make it feasible, so yes, at the end you can write that Blue's DLL is to-day the only working process.

[champagne]

just some remarks linked to hard discussions here and there in other threads.

The code written here uses many "native instructions" of the families of processors having the same set of instructions than Intel processors.

The code is implemented using visual C++, but verified wit g++ to have the compatibility with LINUX.

Although we have no GUI here, we faced several portability problems that our expert mladen solved in due time. Thanks again to him.
Use of "native" instructions (as popcout, bitscan, use of 128 bits registers..) has been done to meet the performance requirements.

Here, discussion of the compatibility with a processor having another set of instructions has no interest.

[coloin]

Indeed well done - grids with automorphism tend to have less ED puzzles - of course !

so the LCT situation could be approx -

17 clues - 46300 ED grid solutions
18 clues - 1e9 grids
19 clues - 4e9 grids
20 clues - 100000 grids ? [including MC and PT grids - only 1 ED 20-puzzle in each]
21 clues - [only ?] 4 grids

the HCT is just a little bit more problematic to confirm

35 clues ? any
36 clues - the MC grid [ it did not have a 37 found in dobrichev 's files]
37 clues
38 clues
39 clues
40 clues - 2 puzzles 1 grid solution

[coloin]

Well .... I knew this exercise might be coming ....
However .... I think most of the Ed grids will have a 19 ( or an 18 )
It might be more worthwhile to generate and register the 19 grids first
And then individually check the missing ? 50k solution grids

And of course in a true morphing process.... if the pattern is kept the same ..... all puzzles generated will be from different solution grids ( excluding 8/9 clue swops ) ( excluding automorphic )

[coloin]

Yes ... will send you some ? Plenty of 18C and 19C collections in the next few days. C

[coloin]

Well .... I think its worthwhile for now for Mathemagics project to try to find any more grids without a 20 ... [if any]
The generation process is certainly fast for 20s and probably will get almost all the grids.
Im thinking that not many grids will only have a solitary 20 .... most grids will have plenty of 20s ? - aside from those automorphic grids which ave reduced numbers of puzzles but we will see.

If we get a batch of grids say 10000 grids [without a 20] left to process.... the ones with a high MCN will be doable with a "checker" process. There are other methods which might churn out a puzzle pseudo randomly in a short time [job done]

Also saving a puzzle exemplar is worthwhile for the 20 and no 19 grids, not so much for the 19C puzzles, And certainly worthwhile for the 18C puzzles.

Looking ahead ... if we get the logistics of the documentation sorted ....

Puzzle generation ....doing a {-1+1} on an internal 18C puzzle will generate the closed group of 1e9 puzzles at around 3000 per minute, probably faster with faster solvers.....

Generating the 19 C puzzles similarly [ and probably much faster - 6000 puzzles per minute] might give us one puzzle per the majority of the grids in reasonable time too.

[coloin]

I did some testing with random grids.
10,000,000 samples produced 461 grids with a 20 and no 19.....

....
Is this an upper bound ? - or have you actually checked [with a "checking program"] that those 461 grids didnt have a 19 ? [i get the feeling you have]
with checker - a low MCN and a high number of clues has in the past made this process last an unfeasibly long time .... but you have obviously made advances ..... ?
hence the 230 k is 461 * 5e9/1e7

100,000,000 samples, and every one had a 20, putting the "21, but no 20" count at "no more than 164" (with 95% confidence, I think).

i'm thinking probability-wise that the number of grids without a 20 is a lot less than 164 ... maybe only 4 ?

anyhow ive done a bit of research whilst mathemagic's program is ongoing ......

taking 8 random 18s - i generated similar pattern template 18s ... there appears to be a lower bound of an average of 26 puzzles per pattern
taking 8 random 19s - i generated similar pattern template 19s ... there appears to be a lower bound of an average of 10000 puzzles per pattern ... new ones still appearing though at the {+5} level

This makes the ratio between patterns with valid 18C puzzles / possible ED 18C patterns at smaller than 1/1000 which is difficult to understand if its correct !

ive been looking at a grid "which has an 18" but i've been struggling to find the 18 puzzle from scratch ....
this grid

Code: Select all

347981256582476193169523874896245317754318962213769485925137648478692531631854729

how long does your program take to confirm one 18-puzzle ? [ and how many 19s ? !]

C

[coloin]

ive copied them here Afmob's exhaustive brilliant searchs !

dd-sym18.txt.zip

(11.05 KiB) Downloaded 253 times

vertsymm18s.zip

(4.28 KiB) Downloaded 281 times

[coloin]

incredible..... am afraid my rough technique of sampling is many leagues behind !
I got around 600 19 puxzzles in the grid before i stumbled on the 18 .... and then stopped....so there was no easy way to see the 18 amid the white noise of the 19s...
well done indeed ......
given there are so many 20-puzzles in an average grid ... its going to be a rare grid which doesnt have one ..... so we will see !
given that there are 25-50 18 puzzles per pattern on average ... might be less than the 1/95 ... i think
it is what it is i suppose ..... and it is all preordained in the scrolls ....

[coloin]

As a little thought .... about those grids with few or only one 20 ......those puzzes may be difficult to find by pseudo-chance ......
blue has a pretty good program for finding / not finding a 20 in these grids ..... what about looking first in all those non-automorphic grids which have 416 band completions requiring 666,665,664, 655 or 555 clues in one or other of their triplebands ?

[coloin]

Gentlemen !
To Mathimagics .... if it finds the 20 ... job is done...whats the problem !
may be rotating the puzzle and scanning the other bands would be a sort of double check ....? ah EDIT i see blue has done that

To blue yeah it seemed a good one ! well maybe just do the grids with 665 ? how many are there of those ?
Anyway work in progress !

[coloin]

yes - a 665 would mean that the clues in band count are at least 665 . or more than 554 in each repective band.
as ony a few of the 416 bands need 6 clues maybe there wont be that many grids !