The New Sudoku Players' Forum

[blue]

Hi Colin,

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]

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]

I know, it's terrible
What a POS

I couldn't resist playing with Colin's idea.

Here's the beginning of the table:

Hidden Text: Show

Code: Select all

    N |     grids | Bands with N 5-clue puzzles
------+-----------+----------------------------
    0 |        17 |   1 224 237 254 307 413
   63 |        31 |  33  48
   78 |        35 | 101
   90 |        67 |  45  67 225
  108 |       103 | 247
  156 |       106 | 289
  168 |       109 | 104
  177 |       116 | 219
  213 |       122 | 240
  244 |       126 | 183
  252 |       245 |   4 415
  258 |       253 | 105
  300 |       266 | 100
  301 |       288 |  83
  309 |       311 | 133
  312 |       327 |  72
  324 |      2293 |   2 412 414
  326 |      2582 | 140
  331 |      2915 | 238
  374 |      3003 | 122
  378 |      3158 |  54
  410 |      3486 |  93
  421 |      3789 | 116
  485 |      4379 | 220
  490 |      4896 |  74
  499 |      5225 | 109
  527 |      5638 |  84
  529 |      6682 | 223
  539 |      7244 | 232
  540 |      7966 | 233
  543 |      8385 | 115
  546 |      8810 |  32
  594 |      8926 | 302
  692 |      9238 | 259
  777 |      9778 | 241
  852 |     10585 | 253 309
  864 |     13649 | 252 305
  972 |     13775 |  16
 1107 |     14014 |   8
 1131 |     17386 | 160 294
 1225 |     27243 | 152 218 226 230
 1275 |     32397 | 217 260
 1531 |     41776 | 222 229
 1577 |     45779 |  92
 1614 |     50774 |  39
 1626 |     57414 | 256 306
 1781 |     62505 | 119
 1783 |     67799 | 171
 1850 |     71996 | 245
 1858 |     89258 |  47 127
 1859 |    102558 |  46 124


I'll extract & test the first million grids, sometime soon.

Blue.

[blue]

Hi Colon,

well maybe just do the grids with 665 ? how many are there of those ?
Anyway work in progress !

I'm not really sure what you mean by "665".
Do you mean every grid where two bands don't have 5-clue puzzles, but the 3rd one does ? ... but doesn't have 4-clue ?

I did run the first ~1M where every band & stack had low 5-clue counts.
The display said I should have had (961565-961319) = 246 grids with no 668, but I only had 19, and some were duplicates.
I think I accidentally had two processes going at the file at the same time, and I Ctrl^C's out of one, and it trashed the file.
I'm running it again, but I'll be away for several hours now.

Later,
Blue.

[blue]

No, don't say that.
I couldn't stand that character.
I'm more the Rorschach/Comedian type.

Cheers.

[blue]

Hi Colin,

This shows the counts you were interested in (I hope).

Hidden Text: Show

Code: Select all

666/xxx 666/666 yyy/666 |      47519 |         17 |         17
665/xxx 665/665 yyy/665 |     228185 |         20 |         26
664/xxx 664/664 yyy/664 |     194843 |         11 |         36
663/xxx 663/663 yyy/663 |      62706 |          0 |          1
662/xxx 662/662 yyy/662 |         39 |          0 |          0
655/xxx 655/655 yyy/655 |    2591055 |        514 |        790
654/xxx 654/654 yyy/654 |   13528622 |       8971 |      13552
653/xxx 653/653 yyy/653 |    4567942 |        704 |       6676
652/xxx 652/652 yyy/652 |      10560 |          0 |          5
644/xxx 644/644 yyy/644 |   44030211 |      94448 |     185704
643/xxx 643/643 yyy/643 |   30838250 |      40804 |     222895
642/xxx 642/642 yyy/642 |      20553 |          0 |        165
633/xxx 633/633 yyy/633 |    6360840 |       1754 |      61338
632/xxx 632/632 yyy/632 |       8232 |          0 |         76
622/xxx 622/622 yyy/622 |         54 |          0 |          8
555/xxx 555/555 yyy/555 |   14411818 |      15455 |     173345
554/xxx 554/554 yyy/554 |  214493467 |    2211750 |    4632166
553/xxx 553/553 yyy/553 |   76484734 |     260697 |    2532325
552/xxx 552/552 yyy/552 |      65144 |          1 |       2198
544/xxx 544/544 yyy/544 | 1257024445 |   89415895 |  142418480
543/xxx 543/543 yyy/543 |  820360406 |   48904321 |  219150672
542/xxx 542/542 yyy/542 |     544118 |         36 |     181854
533/xxx 533/533 yyy/533 |  148019477 |    1862491 |   55362798
532/xxx 532/532 yyy/532 |     197632 |          1 |      78186
522/xxx 522/522 yyy/522 |        130 |          0 |        113
444/xxx 444/444 yyy/444 | 1750050402 |  409386989 | 1244946479
443/xxx 443/443 yyy/443 |  989657965 |  528186529 | 2410287584
442/xxx 442/442 yyy/442 |     318847 |        238 |    1984425
433/xxx 433/433 yyy/433 |   97372976 |   77655487 | 1221627908
432/xxx 432/432 yyy/432 |      27715 |        119 |    1726413
422/xxx 422/422 yyy/422 |         20 |          0 |        690
333/xxx 333/333 yyy/333 |    1211625 |    1206487 |  166800598
332/xxx 332/332 yyy/332 |          6 |          6 |     332752
322/xxx 322/322 yyy/322 |          0 |          0 |        257
222/xxx 222/222 yyy/222 |          0 |          0 |          6

[blue]

Hi Mladen,

Confirming 1x18 + 2709x19.
188 and 4000 seconds. Your code is both fast and correct.

Thanks for the confirmation.

[blue]

Hi Colin,

Quite a bit of catching up to do, from my end ...

Anyway work in progress !

The grids with low 5-clue counts, didn't produce anything new.
The only cases in the first ~1M, with no 668, were the 4+15 cases with automorphisms.
--4 with no 20C at all, and the other 15 listed in the "Grids containing a 21 but no 20" thread.
The next batch, bringing the total to ~10M tested, produced nothing.
The same 4+15 cases, came in testing the 666 and 665 grids.
I ran the 664 and 655 grids too (~2.8M grids) ... no hits.

With regard to my last post .... please could you check that the MCDB of the MC grid is 13 ....

....and i believe that there is quite a big number of ED double bands .... but at least only 44 classes !

There are 983,959,110 ED double bands.
The 44 classes that you have in mind, can be partitioned into 913,393 smaller classes too, going by the mini-column/"gangster-like" signatures in the filled bands. Canonical cases can be defined as having a (true) gangster signature in the missing band, and "gangster-like" signatures in the other bands that are minlex with respect to automorphisms of the signature in the missing band.

The MC grid has 6+6+27's:

Code: Select all

12...6......7....3.......5....5...9..64......8....1...312645978645978312978312645

I presume that all grids with triple band 224 are automorphic ?

No. Here's one with only the trivial automorphism, and a triple 224 in the stacks:

Code: Select all

123456789456789123789123456214365897365897214978214365541632978632978541897541632

[blue]

Hi Colin,

will blue’s magic program be slower or quicker at finding 667-19Cs .... just wondering !

It's slower by a factor of 27 -- about 129 milliseconds per grid, for random grids, on my machine.

For finding a 19C for a grid, it's faster to look first, for puzzles with >= 8 clues a band/stack.
The best order I've hit on so far, takes ~22.6 milliseconds per grid, for random grids.
On my machine, that's ~3,800,000 grids per day per core, and 1432 core*days to do the whole catalog.
Mathimagics' puzzle morphing code, will probably do a lot better than that, for a long time.

[blue]

PPS: LCT-20 is motoring through the unresolved grids, only 972,353,033 to go ...

Nice !

PS: blue, can you do some sampling and give estimates of the probability that a grid will (a) fail the 19C-8 test, (b) fail both tests?

I have these results from my earlier test of 10 million "no NTA" grids:

Code: Select all

3198/10,000,000 -- failed the "19-8c" test (limited to only one band having >= 8 clues)
 505/10,000,000 -- failed the "19-8c" and 667 tests
 461/10,000,000 -- failed the "19-8c", 667 and 577+757 tests
 461/10,000,000 -- failed those and 289/388 tests.

The "19-8c" testing took almost all of the time ... ~25.6 ms per grid.
The change to being it down to 22.6 ms, was to look for 559 puzzles (for up to 6 bands/stacks) first,
and skip that combination when the other "19-8c" tests run.

In a shorter run for the "559 first" method (earlier today):

Code: Select all

71905/1,000,000 -- failed the "559" test
  321/1,000,000 -- failed the rest of the "19-8c" test
   50/1,000,000 -- failed the "19-8c" and 667 tests
   48/1,000,000 -- failed the "19-8c", 667 and 577+757 tests
   48/1,000,000 -- failed those and 289/388 tests.

[blue]

II had a quick look at the source code, could not spot anything wrong in ConsolidateList() where I think the crash occurred, likely fixed already.

It's odd that neither coloin nor me have seen this problem ...

If the problem persists, you might try reducing the batch size check at line 1189, eg change "3" to "2":

Code: Select all

      if (NMT > 0x3FFFFF) break;

It's amazing, that neither of you has seen a crash.
There's a definite problem in ConsolidateList().

Code: Select all

   void AddPuzzleN() {
      memcpy(XT, NT, 166); XT += 166;
      nx++;
      if (nx >= MAXN) {printf("[ERROR] merge table\n"); exit(0);}
      if (nc >= MAXC) return;
      memcpy(NC, NT, 166); NC += 166; nc++; 
      }

   void AddPuzzleM() {
      memcpy(XT, MT, 166);   XT += 166;
      nx++;
      if (nx >= MAXN) {printf("[ERROR] merge table\n"); exit(0);}
      }


A good start, would be to move the "[ERROR]" check lines to in front of the 'memcpy' lines that are (no doubt) causing the crashes.
Also MAXN should be changed to either TABSIZE or MAXC (for versions where MAXN is 12936648 and TABSIZE is only 0x7FFFFF).

The crash can happen in the following circumstance:

1. the incoming MTABLE has a lot of entries, but not enough to close out the "batch".
2. The incoming NTABLE, if it was collapsed to have only one puzzle per grid, and then stripped of puzzles for grids that appear in MTABLE ... would still be large enough so that combining it with MTABLE would cause writes past the end of XTABLE.

The issues that I saw with the ConsolidateList() code, were:

• There is no check for XTABLE being full, before writing to it -- related to the above.
  (The only check, before writing, is for CTABLE).
• endM should be set to 1 on entry, when MTABLE is empty, as (it seems) it is on the 1st call for a new batch.
• Entries in MTABLE that are "larger" than every entry in NTABLE, are lost in the merge.

[blue]

The patched source is available above, could you cast your eye over it?

It's better, but:

Code: Select all

      nx++; if (nx >= MAXN) {nx = MAXN; tFull = 1; return;}  // stop adding
      memcpy(XT, NT, 166); XT += 166;

should be more like:

Code: Select all

      memcpy(XT, NT, 166); XT += 166;
      if (++nx >= TBLSIZE) {tFull = 1; return;}  // stop adding

or (safer, I guess):

Code: Select all

      nx++; if (nx > TBLSIZE) {nx = TBLSIZE; tFull = 1; return;}  // stop adding
      memcpy(XT, NT, 166); XT += 166;

... TBLSIZE, not MAXN ... and either > instead of >=, or increment & check *after* adding the puzzle.

There are the other issues too:
1) int endM = NMT ? 0 : 1; // on entry
2) after the "F(nr, NNT)" loop, doing something like

Code: Select all

while (!tFull && mr < NMT) { AddPuzzleM(); mr++; MT += 166; }

---

PS: LCT-20 BlueMagic processing will be complete in 24 hours ...

Sounds good !
Still no new grids without a 668 puzzle ?

I've got something due to complete in ~22 hours, myself.

Then I'll work on an LCT-19 replacement for BlueMagic.
[ The tests I did before, ran in passes: "test grids; set #define's for next pass; recompile; loop". ]

[blue]

Hi Mathimagics,

Great work

Also, blue's table of "668 failures" is complete, no new cases were discovered.

Do we really know that it's complete, or only that nothing new was found in the 1,365,506,043 grids mentioned here ?

It's just a question.
If we don't know that it's complete, I'm not suggesting that you spend any time on the issue.

Cheers,
Blue.

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