Low/Hi Clue Thresholds

Everything about Sudoku that doesn't fit in one of the other sections

Re: Low/Hi Clue Thresholds

Postby coloin » Sat Aug 24, 2019 6:58 pm

workers have done well this week .... uploading now ...
im sure there are others who could contibute ! :D
C
coloin
 
Posts: 1815
Joined: 05 May 2005

Re: Low/Hi Clue Thresholds

Postby blue » Sat Aug 24, 2019 8:12 pm

For Mathimagics:

The LCT-19 version of BlueMagic is ready -- a Blue19.dll and an EXE that uses it.
It's still slow ... ~20.6 ms/grid @3.6 GHz, for random grids.
There's more bad news: next post.

<Zip file deleted>
--

I discovered two (bad) things about the BlueMagic app, for LCT-20, when I was converting it.

First, it had a bug:
Only 4 of the 6 bands/stacks were given an opertunity (if needed), to be the "8-clue" band for a 668 puzzle.
Fortunately (and amazingly), I guess ... the "if needed" part of that, never kicked in :!:

Second: I accidentally had part of the code using the 256-bit (YMM) registers.
I don't think it sped the code up, and unfortunatly it made the cores run hotter.
The result would be that "Turbo-boost", likely didn't work as well as it should have :(
Last edited by blue on Thu Oct 10, 2019 9:23 am, edited 1 time in total.
blue
 
Posts: 887
Joined: 11 March 2013

Re: Low/Hi Clue Thresholds

Postby blue » Sat Aug 24, 2019 9:17 pm

Bad news about Blue19 app/dll:

  1. It's very slow on grids with no 19.
    250 random such grids, took ~3.33 seconds each, on average, to process.
  2. Grids with a small number of 19's, can take just as long.
  3. The process that the "workers" use to generate grids with 19's -- {-1,+1} puzzle morphing -- is biased towards producing grids with "more 19's" than average. Think about it.
    What I confirmed, rather, was that it's biased towards producing grids that take less time for the Blue19 code to process.
    I ran off ~8M grids like that, and send a random 250000 of them though Blue19.
    The Blue19 phase, took only 2/3 the time that would have be expected for random grids.
  4. The upshot of (3), will be that the more the catalog gets pruned using the "workers" process, the longer will become the average "per grid" time, to handle the "still unresolved" grids.
blue
 
Posts: 887
Joined: 11 March 2013

Re: Low/Hi Clue Thresholds

Postby champagne » Sun Aug 25, 2019 2:46 am

blue wrote:Bad news about Blue19 app/dll:
It's very slow on grids with no 19.
250 random such grids, took ~3.33 seconds each, on average, to process.


Still a little too early to deliver numbers, but this seems the order of magnitude of the search of 17 distribution 665 on a solution grid known to have such a 17.( with the fresh code in test).
The 18 case would be worse in such a process

EDIT I made a test on the first 100 known 17 with distribution 665.
I got an average 6 seconds per solution grid having killed temporarily three ways to speed up the code due to bugs in the implementation.

Running the program to find the first 18 clues should be much faster in average

EDIT 2 same average 6 seconds with 1000 puzzles (running the 8 cores in parallel all of them working on the search of 17s)
Last edited by champagne on Sun Aug 25, 2019 3:57 pm, edited 4 times in total.
champagne
2017 Supporter
 
Posts: 6986
Joined: 02 August 2007
Location: France Brittany

Re: Low/Hi Clue Thresholds

Postby Mathimagics » Sun Aug 25, 2019 8:18 am

Hi blue!

Thanks for the Blue19 binaries, I will road-test it tonight.

blue wrote:I discovered two (bad) things about the BlueMagic app, for LCT-20, when I was converting it.
First, it had a bug:
Only 4 of the 6 bands/stacks were given an opertunity (if needed), to be the "8-clue" band for a 668 puzzle.
Fortunately (and amazingly), I guess ... the "if needed" part of that, never kicked in :!:

Perhaps 20C puzzles are sufficiently numerous that it rarely needs to look beyond the first band?

blue wrote:Second: I accidentally had part of the code using the 256-bit (YMM) registers.
I don't think it sped the code up, and unfortunatly it made the cores run hotter.
The result would be that "Turbo-boost", likely didn't work as well as it should have :(

I hadn't noticed any core-cooking, but will seek compensation anyway! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1390
Joined: 27 May 2015
Location: Canberra

Re: Low/Hi Clue Thresholds

Postby coloin » Sun Aug 25, 2019 10:59 am

champagne wrote:EDIT I made a test on the first 100 known 17 with distribution 665.
I got an average 6 seconds per solution grid having killed temporarily three ways to speed up the code due to bugs in the implementation.

Running the program to find the first 18 clues should be much faster in average


just a thought :idea: .... wouldnt it be better just to test for a 666/666 18C if this is the case .... and do a quick non-minimality check
or rather a lack of a 666/666 18C means there is no 17C [665] too
coloin
 
Posts: 1815
Joined: 05 May 2005

Re: Low/Hi Clue Thresholds

Postby coloin » Sun Aug 25, 2019 11:20 am

blue wrote:The process that the "workers" use to generate grids with 19's -- {-1,+1} puzzle morphing -- is biased towards producing grids with "more 19's" than average. Think about it.

well i suppose we will just have to see .... it will be interesting to see at what point the yield starts to drop
certainly those grids which only have a small number or 19C, there will be much less chance to find these puzzles.... There are 19C puzzles which are remote to {-1+1} and these wont be found, but i suppose we are relying on the fact that there will be many other 19C in that particular solution grid. This problem is predicted to be much worse for the 18C .
Interestingly a {-2+1} on our 1000 19C generated [slowly] almost as many [750] 18Cs ... so we wont be short of seeds ....
coloin
 
Posts: 1815
Joined: 05 May 2005

Re: Low/Hi Clue Thresholds

Postby champagne » Sun Aug 25, 2019 2:28 pm

coloin wrote:
champagne wrote:EDIT I made a test on the first 100 known 17 with distribution 665.
I got an average 6 seconds per solution grid having killed temporarily three ways to speed up the code due to bugs in the implementation.

Running the program to find the first 18 clues should be much faster in average


just a thought :idea: .... wouldnt it be better just to test for a 666/666 18C if this is the case .... and do a quick non-minimality check
or rather a lack of a 666/666 18C means there is no 17C [665] too


My first idea when I worked on blue's proposal for the search of 17's was to do in the same pass the 566;656;665 search.
Blue's warned me that the 665 pass could be very expensive, just due to the fact that we have many more valid 66 valid sub puzzles.
This is for the search of 17's and explain why there is a special pass with the relevant entry file to change the 665 pass in another 656 pass.

Showing that a solution grid can produce a 18/19 is quite a different case. You can stop at the first valid 18/19, so yes, here you can use the process for the distribution 666/667 in bands.
The same process can be applied for any distribution likely then assuming {clues band 1 <= clues band 2 <= clues band 3}; using if necessary a permutation of bands.
champagne
2017 Supporter
 
Posts: 6986
Joined: 02 August 2007
Location: France Brittany

Re: Low/Hi Clue Thresholds

Postby Mathimagics » Sun Aug 25, 2019 4:23 pm

I have tested Blue19, all is well there, and I am getting 39-40 grids/sec at the moment, which is more or less as originally expected based on blue's figures.

blue's "bad news" is not unexpected, and, I think, not really that bad. Blue19 will take longer per grid on average as the catalog is "pruned", sure, but average times will depend on the proportion of high-cost grids.

The bias in the {-1,+1} morph method is theoretically clear, but its actual impact on the LCT-19 processing is less so.

What is clear is that at some point, Blue19 will be more efficient than the morph method. Perhaps not with 25% of the grids unresolved, as was the case with LCT-20, but probably later, say around the 10-15% mark.

It is also possible that the morph method will run out of steam sooner than LCT-20 did, and this will probably shift the predicted crossover back towards 25%.

Only time will tell ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1390
Joined: 27 May 2015
Location: Canberra

Re: Low/Hi Clue Thresholds

Postby blue » Sun Aug 25, 2019 8:32 pm

coloin wrote:
blue wrote:The process that the "workers" use to generate grids with 19's -- {-1,+1} puzzle morphing -- is biased towards producing grids with "more 19's" than average. Think about it.

well i suppose we will just have to see .... it will be interesting to see at what point the yield starts to drop

The good news is that as the yield rate falls, the newly discovered grids will shift towards the "high cost" end of the spectrum.
That's is in line with what Mathimagics was saying about what might happen with the "crossover" point, I think.

coloin wrote:This problem is predicted to be much worse for the 18C .

Since most grids (~82%) don't have an 18C, and since most that do, only have one 18C (~11%) ... "much worse" may be an understatement.

coloin wrote:Interestingly a {-2+1} on our 1000 19C generated [slowly] almost as many [750] 18Cs ... so we wont be short of seeds ....

Yes ... interesting !

Cheers,
Blue.
blue
 
Posts: 887
Joined: 11 March 2013

Re: Low/Hi Clue Thresholds

Postby champagne » Mon Aug 26, 2019 6:41 am

blue wrote:Since most grids (~82%) don't have an 18C, and since most that do, only have one 18C (~11%) ... "much worse" may be an understatement.

And this is also be very bad to apply the 17 search process for the first 18 search
champagne
2017 Supporter
 
Posts: 6986
Joined: 02 August 2007
Location: France Brittany

LCT-19 Progress

Postby Mathimagics » Wed Aug 28, 2019 2:14 pm

At the end of week 2, we have:
Code: Select all
 known 17-19C:   144,490,098
 added    19C:   975,263,602  Week 1
                 917,301,757  Week 2
               =============
               2,037,055,457


Many thanks for the contributions from coloin and 1to9only! 8-)

Most of those contributions have been delivered in the past week, so the closeness of the figures for Week1 and Week 2 is deceptive.

The average yield at the end of week 1 was just over 50%, but now, at the end of week 2, it has declined to around 37%.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1390
Joined: 27 May 2015
Location: Canberra

Re: Low/Hi Clue Thresholds

Postby dinev » Wed Aug 28, 2019 3:59 pm

Hi, Mathimagics!
I am interested in your project and today started the process of generation. So far have made two batches. Till the end of the day I can manage another two. I use Gen19J.exe , the other app has some problems starting. I tested some of the grids for what I am interested in (pattern games). I am satisfied.
Cheers,
Dinev
dinev
 
Posts: 133
Joined: 19 September 2018

Re: Low/Hi Clue Thresholds

Postby coloin » Fri Aug 30, 2019 4:26 pm

Great to have you on board
I'm uploading my next batches soon .... and we will see if we are just generating puzzles in grids with a plethora of 19C ..... hope not !
If this is so and there are many grids out there with a paucity of 19C then maybe we need to somehow change our method of attack - as ever the sudoku space doesnt make it easy
coloin
 
Posts: 1815
Joined: 05 May 2005

Grid Canonicaliser Tool

Postby Mathimagics » Sat Aug 31, 2019 5:42 am

For dinev, here is the grid canonicaliser tool.

Usage: canonicalise infile [outfile]

This tool simply takes an input file of solution grids, converts them to CF (using dobrichev's canonical form functions from GridChecker) and writes the ED grids to outfile if specified, otherwise to standard output.

Canonicalise.zip
Canonicalise tool (Win64)
(45.19 KiB) Downloaded 14 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 1390
Joined: 27 May 2015
Location: Canberra

PreviousNext

Return to General