The New Sudoku Players' Forum

[coloin]

workers have done well this week .... uploading now ...
im sure there are others who could contibute !
C

[blue]

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

[blue]

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.

[champagne]

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)

[Mathimagics]

Hi blue!

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

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?

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!

[coloin]

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 .... 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]

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

[champagne]

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

[Mathimagics]

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

[blue]

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.

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.

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.

[champagne]

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

[Mathimagics]

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!

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%.

[dinev]

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

[coloin]

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

[Mathimagics]

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 177 times