blue wrote: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).
Extremely useful information for the LCT-20 project ...
Cheers!
MM
Low/Hi Clue Thresholds
Re: Low/Hi Clue Thresholds
by Mathimagics » Thu Jul 11, 2019 3:18 am
Thanks very much to blue for those figures (and the links)!
Extremely useful information for the LCT-20 project ...
Cheers!
MM
Extremely useful information for the LCT-20 project ...
Cheers!
MM
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: Low/Hi Clue Thresholds
by coloin » Sat Jul 13, 2019 12:15 am
....blue wrote: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
blue wrote: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
- Posts: 2494
- Joined: 05 May 2005
- Location: Devon
LCT20 - First Milestone
by Mathimagics » Sat Jul 13, 2019 5:29 am
.
LCT-20 project has reached its first milestone. We've hit 50% of the ED grids, yay!!
This has taken a month, but with fits and starts, not to mention MS Windows Update murdering my workforce at regular intervals ....
Anyway, currently we have 20C or better puzzles recorded for 2,777,685,274 grids ( 50.8%).
A full report, by Band and number of clues, is given below. 17C puzzles from Mladen, 18/19C puzzle contributions are from coloin.
The % for each band reflects total puzzles for that band.
Worker productivity has been improved. Workers beaver away at 20C puzzle generation by morphing. Puzzles thus mined are reduced to batches containing 1 x 20C puzzle for each different ED grid. Productivity is measured by the daily batch sizes.
Duplicate grid rates - when different worker processes "solve" the same ED grid - are fairly good. In any set of up to 64 batches, around 75-80% of the grids are distinct.
The catalog update process takes these batches (up to 64 at a time) and updates the catalog. Overall yield, the key indicator during this phase, is measured by the % of distinct grids in a batch set for which puzzles have not already been found.
The first such set had a yield of 100% (
amazing, huh??). This had declined to 67% by the time we had found puzzles for 25% of the grids. Now we have 50% of grids found, and the yield has declined to 35%. These rates appear to be just what one would expect, although I would of course leave any definitive statements in this area to the Sultan of Sampling (blue).
Mladen, I'm sure, will be pleased to know that the old workforce has been sacked, and the new workers do all sort/merge operations via qsort, ie in memory. One short burst of I/O of course to write the batch to disk. Each worker now produces 40-50 million distinct grid/puzzles per day, and I now have 5 of them running.
I have also discovered, to my horror, that the update process is heavily handicapped by the fact that drive D, on which the ED and LCT catalog files reside, is REALLY slow for read/write operations compared to C, my primary drive. But C is only 0.5TB and 50% full, so it can't hold even one of these catalogs completely (they are each 420GB). But I did at least get noticably reduced update-pass times by moving the 1st 100 bands (75%) of the LCT catalog (for which both read and write acess are needed) to the primary drive.
Cheers!
MM
LCT-20 project has reached its first milestone. We've hit 50% of the ED grids, yay!!
This has taken a month, but with fits and starts, not to mention MS Windows Update murdering my workforce at regular intervals ....
Anyway, currently we have 20C or better puzzles recorded for 2,777,685,274 grids ( 50.8%).
A full report, by Band and number of clues, is given below. 17C puzzles from Mladen, 18/19C puzzle contributions are from coloin.
The % for each band reflects total puzzles for that band.
Worker productivity has been improved. Workers beaver away at 20C puzzle generation by morphing. Puzzles thus mined are reduced to batches containing 1 x 20C puzzle for each different ED grid. Productivity is measured by the daily batch sizes.
Duplicate grid rates - when different worker processes "solve" the same ED grid - are fairly good. In any set of up to 64 batches, around 75-80% of the grids are distinct.
The catalog update process takes these batches (up to 64 at a time) and updates the catalog. Overall yield, the key indicator during this phase, is measured by the % of distinct grids in a batch set for which puzzles have not already been found.
The first such set had a yield of 100% (
amazing, huh??). This had declined to 67% by the time we had found puzzles for 25% of the grids. Now we have 50% of grids found, and the yield has declined to 35%. These rates appear to be just what one would expect, although I would of course leave any definitive statements in this area to the Sultan of Sampling (blue).Mladen, I'm sure, will be pleased to know that the old workforce has been sacked, and the new workers do all sort/merge operations via qsort, ie in memory. One short burst of I/O of course to write the batch to disk. Each worker now produces 40-50 million distinct grid/puzzles per day, and I now have 5 of them running.
I have also discovered, to my horror, that the update process is heavily handicapped by the fact that drive D, on which the ED and LCT catalog files reside, is REALLY slow for read/write operations compared to C, my primary drive. But C is only 0.5TB and 50% full, so it can't hold even one of these catalogs completely (they are each 420GB). But I did at least get noticably reduced update-pass times by moving the 1st 100 bands (75%) of the LCT catalog (for which both read and write acess are needed) to the primary drive.
Cheers!
MM
Band/Puzzle counts: Show
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: Low/Hi Clue Thresholds
by dobrichev » Sat Jul 13, 2019 9:58 am
What a big numbers!
I still can't realize how and why you organized the process by bands while mutations result in puzzles from random band. But I prefer explanation formulated at the final stages of the project, not now.
Did you use the results from symmetrical 18's thread in this forum?
I still can't realize how and why you organized the process by bands while mutations result in puzzles from random band. But I prefer explanation formulated at the final stages of the project, not now.
Did you use the results from symmetrical 18's thread in this forum?
- dobrichev
- 2016 Supporter
- Posts: 1863
- Joined: 24 May 2010
Re: Low/Hi Clue Thresholds
by coloin » Sat Jul 13, 2019 11:25 am
ive copied them here Afmob's exhaustive brilliant searchs !
dd-sym18.txt.zip- (11.05 KiB) Downloaded 216 times
- vertsymm18s.zip
- (4.28 KiB) Downloaded 257 times
- coloin
- Posts: 2494
- Joined: 05 May 2005
- Location: Devon
Re: Low/Hi Clue Thresholds
by Mathimagics » Sat Jul 13, 2019 11:35 am
dobrichev wrote:I still can't realize how and why you organized the process by bands while mutations result in puzzles from random band. But I prefer explanation formulated at the final stages of the project, not now.
Ok, but I will say just this - my ED catalog was originally generated by gsf's sudoku tool, and I ran it once on each band, and stored each result set in a separate file. Cloning it to use as LCT catalog means that grid index lookup in ED also gives the file offset in LCT ...
dobrichev wrote:Did you use the results from symmetrical 18's thread in this forum?
No, but I will certainly look in there at some stage. All 18C's and 19C's that I have recorded were all provided by coloin ...
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: Low/Hi Clue Thresholds
by blue » Sat Jul 13, 2019 7:19 pm
Hi Colin,
Yes, and for good measure, I checked them to make sure they had a 20, too.
It's certainly possible.
For "automorphic" grids the ratio of "no 19" to "no 20" grids was ~1200:1.
I didn't know what to expect, but I wondered if that might mean there were another ~4800 "non-automorphic" grids with no 20.
It's clear now, (for me, anyway), that there are nowhere near that many !
The ratio is more like 1/95, using JPF's count of 184,060,159,680 ED patterns, and my estimate of 1,934,000,000 18C puzzles (mentioned earlier in the thread).
It seems like you've shown that if an 18C/19C pattern has one puzzle, then it's many times more likely that the same pattern has another puzzle, than it is that a randomly chosen pattern of the same size, has at least one puzzle.
5.4 seconds to confirm "only one" 18, and 213 seconds to find 2709 19's (including the 63 non-minimals).
(Any confirmation(s) of the 2709 number ?)
Cheers,
Blue.
coloin wrote:....blue wrote: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]
Yes, and for good measure, I checked them to make sure they had a 20, too.
coloin wrote:i'm thinking probability-wise that the number of grids without a 20 is a lot less than 164 ... maybe only 4 ?
It's certainly possible.
For "automorphic" grids the ratio of "no 19" to "no 20" grids was ~1200:1.
I didn't know what to expect, but I wondered if that might mean there were another ~4800 "non-automorphic" grids with no 20.
It's clear now, (for me, anyway), that there are nowhere near that many !
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 !
The ratio is more like 1/95, using JPF's count of 184,060,159,680 ED patterns, and my estimate of 1,934,000,000 18C puzzles (mentioned earlier in the thread).
It seems like you've shown that if an 18C/19C pattern has one puzzle, then it's many times more likely that the same pattern has another puzzle, than it is that a randomly chosen pattern of the same size, has at least one puzzle.
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 ? !]
5.4 seconds to confirm "only one" 18, and 213 seconds to find 2709 19's (including the 63 non-minimals).
(Any confirmation(s) of the 2709 number ?)
Cheers,
Blue.
- blue
- Posts: 1045
- Joined: 11 March 2013
Re: Low/Hi Clue Thresholds
by coloin » Sat Jul 13, 2019 11:10 pm
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 ....
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
- Posts: 2494
- Joined: 05 May 2005
- Location: Devon
Kilometrestones?
by Mathimagics » Tue Jul 16, 2019 2:36 pm
Some minor milestones reached for LCT-20 today ...
The first version of WorkerX uses conventional weapons to find 20C puzzles on a grid - producing minimal puzzles by removing clues, repeating the process until we find a 20C or exceed an iteration limit. In this naive form, it is painfully slow, perhaps 0.3 grids/second, but with some simple improvements (reduce to 22C then do a limited vicinity search) it can be prodded into delivering aout 8 - 10 grids/sec. That would amount to a daily yield of 700K - 850K, so it suffices for now, it can finish off the smaller bands.
The real stage 2 work will require much heavier duty capability, and blue has indicated that we might get perhaps 200 grids/sec from code that he has, and has volunteered to consruct and deliver an app, and we very much look forward to that!
Meanwhile the stage 1 workers soldier on ... they are (rather amazingly) each still delivering between 15 and 20 million new grids a day (an effective yield of 170 - 230 new grids/second). This will inevitably decline, of course, but for now it's all systems go ...
Cheers,
MM
[EDIT] Today's bulk update results: now have 3,206,072,984 grids resolved ( 58.58%). Workers net yield (% of grids found that are new, ie unresolved) has dipped below 30% for the first time: 29.8%
- total grids ticked off has passed the 3 billion mark ...
- we have 100% coverage for Bands 300 - 416. This is of course a very small subset (2,097,068 grids) but it's a first time outing for the stage 2 worker process, aka WorkerX - these workers implement stage 2 of the pool reduction process, in which we attempt to reduce the unresolved grids by explicitly targeting them, looking for 20C puzzles. (Stage 3, the final stage, will rigorously test unresolved grids via a "Checker"-like process to determine their final status).
So we can state definitively that ALL grids in these bands have 20C or better puzzles.
The first version of WorkerX uses conventional weapons to find 20C puzzles on a grid - producing minimal puzzles by removing clues, repeating the process until we find a 20C or exceed an iteration limit. In this naive form, it is painfully slow, perhaps 0.3 grids/second, but with some simple improvements (reduce to 22C then do a limited vicinity search) it can be prodded into delivering aout 8 - 10 grids/sec. That would amount to a daily yield of 700K - 850K, so it suffices for now, it can finish off the smaller bands.
The real stage 2 work will require much heavier duty capability, and blue has indicated that we might get perhaps 200 grids/sec from code that he has, and has volunteered to consruct and deliver an app, and we very much look forward to that!
Meanwhile the stage 1 workers soldier on ... they are (rather amazingly) each still delivering between 15 and 20 million new grids a day (an effective yield of 170 - 230 new grids/second). This will inevitably decline, of course, but for now it's all systems go ...
Cheers,
MM
[EDIT] Today's bulk update results: now have 3,206,072,984 grids resolved ( 58.58%). Workers net yield (% of grids found that are new, ie unresolved) has dipped below 30% for the first time: 29.8%
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: Low/Hi Clue Thresholds
by coloin » Thu Jul 18, 2019 1:39 pm
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 ?
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
- Posts: 2494
- Joined: 05 May 2005
- Location: Devon
Re: Low/Hi Clue Thresholds
by blue » Fri Jul 19, 2019 12:42 pm
Exe files for Mathimagics ...
(deleted)
(deleted)
Last edited by blue on Fri Aug 02, 2019 2:05 am, edited 3 times in total.
- blue
- Posts: 1045
- Joined: 11 March 2013
Re: Low/Hi Clue Thresholds
by blue » Fri Jul 19, 2019 5:25 pm
Hi Colin,
That's a great idea
I hadn't done this until seeing your post, but maybe you did: I looked at the band types and 5-clue puzzle counts for the (so far) four known "no 20" grids. The results were:
All them had either all bands or all stacks having type 224.
The 5-clue counts are on the way way low end, too.
Sometime this weekend, I'll count how many grids have all bands & stacks with 5-clue counts <= N, for N's matching actual 5-clue counts.
Blue.
coloin wrote: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 ?
That's a great idea
I hadn't done this until seeing your post, but maybe you did: I looked at the band types and 5-clue puzzle counts for the (so far) four known "no 20" grids. The results were:
- Code: Select all
1, 1, 1,224,224,224 0, 0, 0, 0, 0, 0
4,224,224,224,224,224 252, 0, 0, 0, 0, 0
224,224,224,254,254,413 0, 0, 0, 0, 0, 0
224,224,224,225,225,414 0, 0, 0, 90, 90, 324
All them had either all bands or all stacks having type 224.
The 5-clue counts are on the way way low end, too.
Sometime this weekend, I'll count how many grids have all bands & stacks with 5-clue counts <= N, for N's matching actual 5-clue counts.
Blue.
- blue
- Posts: 1045
- Joined: 11 March 2013
Re: Low/Hi Clue Thresholds
by Mathimagics » Fri Jul 19, 2019 6:00 pm
LCT-20 Progress Report 20 Jul 2019
Thanks to him, we can now predict fairly accurately the time remaining. The stage 1 worker will run for another 3-5 days, until their yield declines to the point where they produce less than 16 million a day each, and we switch over to stage 2 and run BlueMagic20 instead. Completion times then become effectively linear, it just depends how many workers we can throw at it. But all indications point to completion within 14 days.
- grids resolved = 3,424,231,060 (62.57%)
- workers yield 26.4%, 21 million new grids per worker per day
- blue has delivered his app, which we have christened BlueMagic20. It finds 20C puzzles if they exist for specific grids, and can do so at an astonishing rate of 16 million a day!
Thanks to him, we can now predict fairly accurately the time remaining. The stage 1 worker will run for another 3-5 days, until their yield declines to the point where they produce less than 16 million a day each, and we switch over to stage 2 and run BlueMagic20 instead. Completion times then become effectively linear, it just depends how many workers we can throw at it. But all indications point to completion within 14 days.
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: Low/Hi Clue Thresholds
by blue » Fri Jul 19, 2019 6:17 pm
Mathimagics wrote:blue has delivered his app, which we have christened BlueMagic20. It finds 20C puzzles if they exist for specific grids, and can do so at an astonishing rate of 16 million a day!
Warning: It only finds 20's with a "668" clue count distribution in bands or stacks.
That seems to cover 99.999999% (or more) of the grids, though
- blue
- Posts: 1045
- Joined: 11 March 2013
Re: Low/Hi Clue Thresholds
by Mathimagics » Fri Jul 19, 2019 6:39 pm
OMG !!! 
You mean to say, that should there exist a grid with 20C puzzles, but none with a 668 pattern, then I might have to waste 5-10 seconds of my precious time re-testing that grid with my NotMagic20 app?
And that this might involve testing potentially1000's 100's dozens of grids?
I want a refund!
You mean to say, that should there exist a grid with 20C puzzles, but none with a 668 pattern, then I might have to waste 5-10 seconds of my precious time re-testing that grid with my NotMagic20 app?
And that this might involve testing potentially
I want a refund!
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
