The New Sudoku Players' Forum

[daj95376]

Okay, are there any eliminations that I'm missed?

There is r1c5<>6 and r5c7<>12 also.

Corrected in my software and the tables listed above.

... I now think {1267}-templates is better than <1267>-templates or <1267>-rookery or {1267]-rookery. Opinions?

I believe the proper use of set notation requires the entries to be separated by commas. If so, then you need {1,2,6,7}-templates. That's why I'd use the <1267>-templates notation with single-digit values.


Coloin: I can alter my template() routine to test all of the possible 4-template and 5-template scenarios; but, in the end, it would be easier to just write the 9-template scenario and eliminate all candidates that aren't in the solution. What will we learn from your suggestion?

[coloin]

Sorry ronk for using these two terms interchageably.
dobrichev used the great dukosos post when he analysed them. I believe some templates share a rookery. [hope its the right way round]
I think your <234> is the clearest..

To explain.....

we start with the pm board with all the possible positions of the unknown clues
you have calulated the possible templates at the 1-level.
as you go up a level - invalid template combinations will be lost.
at a given level if a particular pm is absent from all the remaining possible templates - then this is an elimination.
ronk suggested looking at the templates envolved in the SK loop in the Easter Monster puzzle.We saw a massive reduction of possible templates.

eliminations have to occur as there will be reduction in the possible templates as you increase the level.
We know this because at level 7 - its extremely likely that only one template combination will remain [the correct one].
The higher level you go up the greater the product of the original 1-templates.
There has to be a level where there is an elimination. There may be several at the same level - which will blurr things a bit.
I suppose when there is only one pm left in the whole column of the strings of the remaining templates - this has to be an insertion.

The reference to Sudoku Explainer - which doesnt use SK loops - but attributes a magic number to the complexity of the most difficult elimination. The first one in diamond puzzles.

C

[daj95376]

Coloin: I ran all 4-template scenarios, and <1267>-templates was the only one to generate eliminations.

[coloin]

Great - i think that is what we would have expected. I think we are not just interested in sioving the puzzle - but solving it as elegantly as possible.

Perhaps we need to think about another hard puzzle. Perhaps one which has been studied and someone has shown a step which solves it -

If you have time - Perhaps try a 8.3/8.3/8.3 of your choice. and see when the eliminations happen.

I get the feeling that the eliminations found will be similar to other researchers.

Not sure how to interpret a result such as "1 elimination was found with <1234>" I am sure ronk can see these things !

Of course performing the elimination and repeating the exercise should see the puzzle crumble.

All interesting.. and thanks.

C

[daj95376]

If you have time - Perhaps try a 8.3/8.3/8.3 of your choice. and see when the eliminations happen.

Coloin: Pretty much of a dud !!!

Code: Select all

 +-----------------------+
 | 5 . . | 2 3 . | . . . |
 | . . 8 | . . 5 | . . . |
 | . 6 . | . . . | 9 . . |
 |-------+-------+-------|
 | 1 . . | . . 4 | . 8 . |
 | 3 . . | . 6 . | . . 1 |
 | . 2 . | 9 . . | . 4 . |
 |-------+-------+-------|
 | . . 7 | . . . | 5 . . |
 | . . . | 1 . 7 | . . . |
 | . . . | . 4 . | . . 2 |
 +-----------------------+   # ED=8.6/8.6/8.5   Patrice

 +--------------------------------------------------------------------------------+
 |  5       1479    149     |  2       3       1689    |  14678   167     4678    |
 |  2479    13479   8       |  467     179     5       |  123467  12367   3467    |
 |  247     6       1234    |  478     178     18      |  9       12357   34578   |
 |--------------------------+--------------------------+--------------------------|
 |  1       579     569     |  357     257     4       |  2367    8       35679   |
 |  3       45789   459     |  578     6       28      |  27      2579    1       |
 |  678     2       56      |  9       1578    138     |  367     4       3567    |
 |--------------------------+--------------------------+--------------------------|
 |  24689   13489   7       |  368     289     23689   |  5       1369    34689   |
 |  24689   34589   234569  |  1       2589    7       |  3468    369     34689   |
 |  689     13589   13569   |  3568    4       3689    |  13678   13679   2       |
 +--------------------------------------------------------------------------------+
 # 171 eliminations remain

(7)r123c9=r46c9-(7=2)r5c7-(2=8)r5c6-r6c56=(8-7)r6c1=r23c1-r1c2=(7)r1c789 => r2c78,r3c8<>7

(8=2)r5c6-(2=7)r5c7-(7=356)r6c379-(3=18)r36c6-loop => r5c8<>27, r4c79<>7, r179c6<>8

   c7b6  Locked Candidate 1              <> 2    r2c7
 r3  b2  Locked Candidate 1              <> 8    r3c9

......6.......................................................................... <1478>

(356=7)r6c379-(7=2)r5c7-(2=8)r5c6-(18=3)r36c6-(3=567)r6c379 => r6c5<>5, r6c1<>6

   c3b4  Locked Candidate 1              <> 6    r89c3

(2)r4c5=r5c6-(2=7)r5c7-(7=356)r6c379-(3)r6c6=UR=(7)r36c5 => r4c5<>7
(1=8)r3c6-(8=2)r5c6-(2=7)r5c7-(7=356)r6c379-(3=18)r36c6 =>  r1c6<>1

.7........7......7........7..................7................................... <1378>


Puzzle far from solved after five chains ... and very little help from 4-template analysis.

[coloin]

Well - its not unusual for sudoku puzzles to constanyly disprove conjectures.
The eliminations have to come at some stage. If loops envolve multiple <clues> maybe the eliminations do occur at the high level.
Maybe we should wait for champagne and allan barker to comment to see if there is worth in what we have been discussing.
Maybe Fata morgana has eliminations at the <4> level.............. C

[dobrichev]

Hi,

I don't know what "level n" is, but after the initial template eliminations there is a computationally cheap test whether each of the survived templates has at least one disjoint corresponding template for each of the remaining digits.

Here are the counts of the eliminations performed in this way (wide screen). 1,2,6 are reduced for Easter Monster if this has something in common to this debate.

Code: Select all

puzzle                                                                               pass 1 remaining templates    pass 2 eliminated templates
                                                                                   1   2   3   4  5  6  7   8   9  1  2  3  4 5  6 7 8 9
100000002090400050006000700050903000000070000000850040700000600030009080002000001 41  39 130  32 18 41  8 148  18  8  4  0  0 0  8 0 0 0 Easter Monster
000000039000001005003050800008090006070002000100400000009080050020000600400700000 47  37 108  38 32 96 52  12  16  0  0  0  0 0  0 0 0 0 Golden Nugget
000000012000000003002300400001800005060070800000009000008500000900040500470006000 65 111 109  34 12 50 73  24  47  0  0 15  0 0  0 0 0 0 Platinium Blonde
000000007020400060100000500090002040000800600600900000005003000030080020700004001 42  10 113  24 42 28 57 144  88  0  0  0  0 0  0 0 0 0 Tungston Rod
000000003001005600090040070000009050700000008050402000080020090003500100600000000 34 150  66 154  9 68 66  65   7 10 27 17 18 1 17 0 0 0 Fata Morgana
100000007020400060003000500090040000000062040000900800005000003060200080700001000 34  22  36  18 44 16 43  92 116  0  0  0  0 0  0 0 0 0 Silver Plate


Below is the code. Step D is the addition. The last resort brute force loop is suboptimal and is used only to check the puzzle uniqueness.

Hidden Text: Show

Code: Select all

unsigned long long templates::nSol(const char *p) {
   //~80 puzzles/second for Gordon Royle's list of 17s (500/s initialization only), 400/s w/o guessing
   bm128 clues[9]; //positions of the givens for each digit
   bm128 invalid[9]; //forbidden positions for each digit

//Take a puzzle. Example from Patterns Game.
//... ..1 ..2
//..3 .4. .5.
//.6. 7. .8..
//
//..6 ... .7.
//.4. .2. ..3
//1.. ..4 9..
//
//..8 ..9 5..
//.7. 8.. .6.
//6.. .5. ... ER=6.6/6.6/6.6 - joel64, patterns game 146
//
//Step A. Prepare 9 81-bit masks, one per digit. Example for digit 7.
//.*. *** .*2
//.*3 *** .*.
//*** 7** ***
//
//*** *** *7*
//.*. *2. ***
//1*. *.4 ***
//
//*** *.9 5*.
//*7* *** ***
//*** *5. .*. Digit 7 step A1: set all visible cells
//
//
//.*. *** .**
//.** *** .*.
//*** 7** ***
//
//*** *** *7*
//.*. **. ***
//**. *.* ***
//
//*** *.* **.
//*7* *** ***
//*** **. .*. Digit 7 step A2: set all givens <> 7
//
//
//.*. *** .**
//.** *** .*.
//*** .** ***
//
//*** *** *.*
//.*. **. ***
//**. *.* ***
//
//*** *.* **.
//*.* *** ***
//*** **. .*. Digit 7 mask: only 6 from the 46656 possible templates are disjoint to this mask
//
//Step B. Apply the 9 masks over all 46656 templates. Store all disjoint to the mask templates as candidates for the respective digit.
//
//Template distribution 36 28 54 28 14  4  6 14 42    product=301112598528 sum=226
//
//Step C. Perform some basic eliminations (none of them is required for this example puzzle).
//
//Step D. Remove all templates that have no at least one disjoint template for each of the other digits.
//Repeat until solution found or no more eliminations exist.
//
//Template distribution  1  1  1  1  1  1  1  1  1    product=1            sum=9 (example puzzle solved)
//
//Steps E-Y. Still unknown.
//
//Step Z. Last resort: Reorder digits (relabel) in accending order by number of templates, perform 9 nested loops, find all disjoint templates.
//
//No-solution condition: A digit with 0 template candidates.
//Single-solution condition: 9 disjoint templates remain, one for each digit.
//Multiple-solution condition: More than one possibility to form 9 disjoint templates, one for each digit.
//
//The basic methods include:
//- Solve a cell if only templates for one of the digits hit it. Remove the templates for the same digit that not hit the solved cell.
//- Solve a digit if there is a cell covered by only one template. Remove rest of the templates for this digit. Remove the templates for other digits that hit the solved digit.
//- Other methods, suggested (not yet) by experts.
//
//Step B rate is ~500 puzzles/sec.
//Generating large amount of solutions for multiple-solution puzzle is expected to be fairly fast.

   bm128 allClues; //all givens
   unsigned short invalids[46656]; //bit (d - 1) is set if the respective template is forbidden for digit d.
   int kTemplCount[9];
   int validCount[9]; //how many valid templates remain for each digit
   unsigned long long ret = 0;
#ifdef __INTEL_COMPILER
#pragma noparallel
#endif //__INTEL_COMPILER
   for(int t = 0; t < 46656; t++)
      invalids[t] = 0; //initially there are no invalid templates
   for(int d = 0; d < 9; d++) {
      clues[d].clear(); //initially there are no clues
      validCount[d] = 46656; //initially every digit has 46656 valid templates
      invalid[d].clear(); //initially all digits have no invalid positions
      kTemplCount[d] = 0;
   }
   allClues.clear();
   for(int c = 0; c < 81; c++) {
      int d = p[c];
      if(d--) { //work with zero based digits 0..8
         clues[d].setBit(c); //cell c is given for digit d
         allClues.setBit(c); //cell c is given
         for(int r = 0; r < 20; r++) { //all templates visible from the given are invalid
            invalid[d].setBit(affectedCells[c][r]); //related cell r can't contain the same digit d
         }
      }
   }
   for(int d = 0; d < 9; d++) {
      bm128 rest; //all givens but d
      rest = allClues;
      rest ^= clues[d];
      invalid[d] |= rest; //d can't share cells with other givens
   }
   //the only one missing bit in the houses of the givens in invalid[] guaranees also the existence of the givens
   for(int t = 0; t < 46656; t++) {
      for(int d = 0; d < 9; d++) {
         bm128 tt = allTemplates[t];
         tt &= invalid[d]; //find forbidden positions for digit d in template t
         if(!tt.isZero()) { //invalid template for this digit
            invalids[t] |= Digit2Bitmap[d + 1]; //mark the respective bit
            validCount[d]--; //one less template candidate
         }
      }
   }

   //for(int c = 0; c < 81; c++) {
   //   printf("%c", p[c] + '0');
   //}
   //printf("\n");

   int tCount = 0; //all template candidates
   int tCounts[9]; //template candidates per digit
   int solvedDigits = 0;
   unsigned long long rating = 1;
   for(int d = 0; d < 9; d++) {
      tCount += validCount[d];
      tCounts[d] = 0;
      printf("%d ", validCount[d]);
      rating *= validCount[d];
      if(validCount[d] == 1)
         solvedDigits |= Digit2Bitmap[d + 1];
   }
   printf("\t%llu (pass 1) tCount = %d\n", rating, tCount);

   bm128 **digitTemplates[9]; //9 pointers to arrays of the valid templates
   digitTemplates[0] = (bm128**)malloc(tCount * sizeof(bm128*));
   for(int d = 0; d < 9 - 1; d++) {
      digitTemplates[d + 1] = digitTemplates[d] + validCount[d];
   }

   //obtain pointers to the valid templates
   for(int t = 0; t < 46656; t++) {
      if(511 == (invalids[t] & 511))
         continue; //nothing to do with entirely invalid template
      for(int d = 0; d < 9; d++) {
         if(0 == (invalids[t] & Digit2Bitmap[d + 1])) {
            digitTemplates[d][tCounts[d]++] = &allTemplates[t];
         }
      }
   }

   bool repeat;
   do {
restart:
      repeat = false;
      //fix the templates which are the only candidate for a cell
      bm128 allPoss;
      allPoss.clear();
      bm128 duplicates;
      duplicates.clear();
      for(int d = 0; d < 9; d++) {
         bm128 newSolvedCells;
         newSolvedCells -= clues[d];
         for(int t = 0; t < validCount[d]; t++) {
            duplicates |= (allPoss & *digitTemplates[d][t]);
            allPoss |= *digitTemplates[d][t];
            newSolvedCells &= *digitTemplates[d][t];
         }
         //add to newly solved cells these having this digit as only candidate
         bm128 allDigitPoss = maskLSB[81].m128i_m128i;
         for(int d2 = 0; d2 < 9; d2++) {
            if(d2 == d)
               continue;
            for(int t2 = 0; t2 < validCount[d2]; t2++) {
               allDigitPoss.clearBits(*digitTemplates[d2][t2]);
            }
         }
         allDigitPoss.clearBits(clues[d]);
         if(!allDigitPoss.isZero()) {
            int firstRemoved = -1;
            for(int t = 0; t < validCount[d]; t++) {
               bm128 notSolvedCell = allDigitPoss;
               notSolvedCell.clearBits(*digitTemplates[d][t]);
               if(!notSolvedCell.isZero()) {
                  //a candidate template with missing solved cell is invalid
                  digitTemplates[d][t] = NULL;
                  if(firstRemoved == -1) {
                     firstRemoved = t;
                  }
               }
            }
            if(firstRemoved != -1) {
               //cleanup the NULL template pointers
               int t2 = firstRemoved;
               for(int t1 = firstRemoved + 1; t1 < validCount[d]; t1++) {
                  if(digitTemplates[d][t1])
                     digitTemplates[d][t2++] = digitTemplates[d][t1];
               }
               validCount[d] = t2;
               repeat = true; //perform next pass
               if(t2 == 0) {
                  printf("No valid template for digit %d.\n", d + 1); //no solution
                  goto exit;
               }
               if(t2 == 1) {
                  clues[d] = *digitTemplates[d][0];; //solved digit
                  solvedDigits |= Digit2Bitmap[d + 1];
               }
               goto restart; //???
            }
            newSolvedCells |= allDigitPoss;
         }
         //eliminate contradicting templates from other digits for newly solved cells
         if(!newSolvedCells.isZero()) {
            clues[d] |= newSolvedCells;
            for(int d2 = 0; d2 < 9; d2++) {
               if(d2 == d)
                  continue;
               int firstRemoved = -1;
               for(int t2 = 0; t2 < validCount[d2]; t2++) {
                  if(!newSolvedCells.isDisjoint(*digitTemplates[d2][t2])) {
                     //remove this template from the list
                     digitTemplates[d2][t2] = NULL;
                     if(firstRemoved == -1)
                        firstRemoved = t2;
                  }
               }
               if(firstRemoved != -1) {
                  //cleanup the NULL template pointers
                  int t2 = firstRemoved;
                  for(int t1 = firstRemoved + 1; t1 < validCount[d2]; t1++) {
                     if(digitTemplates[d2][t1])
                        digitTemplates[d2][t2++] = digitTemplates[d2][t1];
                  }
                  validCount[d2] = t2;
                  repeat = true; //perform next pass
                  if(t2 == 0) {
                     printf("No valid template for digit %d.\n", d2 + 1); //no solution
                     goto exit;
                  }
                  if(t2 == 1) {
                     clues[d2] = *digitTemplates[d2][0];; //solved digit
                     solvedDigits |= Digit2Bitmap[d2 + 1];
                  }
                  //goto restart; //20% slower
               }
            }
            goto restart; //1% slower
         }
      }
      bm128 uniques = allPoss;
      uniques ^= duplicates;
      for(int d = 0; d < 9 && (!uniques.isZero()); d++) { //exit the loop when uniques exhausted
         if(validCount[d] == 1) {
            //it is OK a solved digit to occur once in all template candidates
            uniques.clearBits(*digitTemplates[d][0]); //cleanup uniques
            continue;
         }
         for(int t = 0; t < validCount[d]; t++) {
            if(!digitTemplates[d][t]->isDisjoint(uniques)) {
               validCount[d] = 1; //solve this digit
               solvedDigits |= Digit2Bitmap[d + 1];
               digitTemplates[d][0] = digitTemplates[d][t]; //assign pointer
               clues[d] = *digitTemplates[d][0];
               uniques.clearBits(*digitTemplates[d][0]); //cleanup uniques
               repeat = true;
               //goto restart; //1.3% faster for newSolvedCells disabled
            }
         }
      }
      if(repeat && solvedDigits != 511)
         goto restart;

      //filter out templates which haven't at least one disjoint template for each of the rest digits
      tCount = 0;
      for(int d1 = 0; d1 < 9; d1++) {
         int firstRemoved = -1;
         for(int t1 = 0; t1 < validCount[d1]; t1++) {
            //find at least one disjoint template from the rest digits
            int disjointCount = 0;
            for(int d2 = 0; d2 < 9; d2++) {
               if(d1 == d2)
                  continue;
               for(int t2 = 0; t2 < validCount[d2]; t2++) {
                  if(digitTemplates[d1][t1]->isDisjoint(*digitTemplates[d2][t2])) {
                     disjointCount++;
                     break; //stop at first found
                  }
               }
            }
            if(disjointCount < 8) { //invalid template [d1][t1]
               //remove this template from the list
               digitTemplates[d1][t1] = NULL;
               if(firstRemoved == -1)
                  firstRemoved = t1;
            }
         }
         if(firstRemoved != -1) {
            //cleanup the NULL template pointers
            int t2 = firstRemoved;
            for(int t1 = firstRemoved + 1; t1 < validCount[d1]; t1++) {
               if(digitTemplates[d1][t1])
                  digitTemplates[d1][t2++] = digitTemplates[d1][t1];
            }
            validCount[d1] = t2;
            repeat = true; //perform next pass
            if(t2 == 0) {
               printf("No valid template for digit %d.\n", d1 + 1); //no solution
               goto exit;
            }
            if(t2 == 1) {
               clues[d1] = *digitTemplates[d1][0];; //solved digit
               solvedDigits |= Digit2Bitmap[d1 + 1];
            }
            //goto restart; //~8% slower
         }
      }
      rating = 1;
      tCount = 0;
      for(int d = 0; d < 9; d++) {
         printf("%d ", validCount[d]);
         rating *= validCount[d];
         tCount += validCount[d];
      }
      printf("\t%llu (pass 2) tCount = %d\n", rating, tCount);
   } while(repeat && (solvedDigits != 511)); //some template removed and the rest of the templates are still not unique

   //rating = 1;
   //tCount = 0;
   //for(int d = 0; d < 9; d++) {
   //   printf("%d\t", validCount[d]);
   //   rating *= validCount[d];
   //   tCount += validCount[d];
   //}
   //printf("%d\t%llu\n", tCount, rating);

   //if(tCount > 9) ret = 2; else ret = 1; goto exit;

   if(tCount > 9) {
      //find 9 disjoint templates
      kTemplCount[0] = validCount[0];
      for(int t1 = 0; t1 < validCount[0]; t1++) {
         for(int t2 = 0; t2 < validCount[1]; t2++) {
            bm128 t12 = *digitTemplates[0][t1];
            if(!digitTemplates[1][t2]->isDisjoint(t12))
               continue;
            kTemplCount[1]++;
            t12 |= *digitTemplates[1][t2];
            for(int t3 = 0; t3 < validCount[2]; t3++) {
               if(!digitTemplates[2][t3]->isDisjoint(t12))
                  continue;
               kTemplCount[2]++;
               bm128 t123 = t12;
               t123 |= *digitTemplates[2][t3];
               for(int t4 = 0; t4 < validCount[3]; t4++) {
                  if(!digitTemplates[3][t4]->isDisjoint(t123))
                     continue;
                  kTemplCount[3]++;
                  bm128 t1234 = t123;
                  t1234 |= *digitTemplates[3][t4];
                  for(int t5 = 0; t5 < validCount[4]; t5++) {
                     if(!digitTemplates[4][t5]->isDisjoint(t1234))
                        continue;
                     kTemplCount[4]++;
                     bm128 t12345 = t1234;
                     t12345 |= *digitTemplates[4][t5];
                     for(int t6 = 0; t6 < validCount[5]; t6++) {
                        if(!digitTemplates[5][t6]->isDisjoint(t12345))
                           continue;
                        kTemplCount[5]++;
                        bm128 t123456 = t12345;
                        t123456 |= *digitTemplates[5][t6];
                        for(int t7 = 0; t7 < validCount[6]; t7++) {
                           if(!digitTemplates[6][t7]->isDisjoint(t123456))
                              continue;
                           kTemplCount[6]++;
                           bm128 t1234567 = t123456;
                           t1234567 |= *digitTemplates[6][t7];
                           for(int t8 = 0; t8 < validCount[7]; t8++) {
                              if(!digitTemplates[7][t8]->isDisjoint(t1234567))
                                 continue;
                              kTemplCount[7]++;
                              bm128 t12345678 = t1234567;
                              t12345678 |= *digitTemplates[7][t8];
                              for(int t9 = 0; t9 < validCount[8]; t9++) {
                                 if(!digitTemplates[8][t9]->isDisjoint(t12345678))
                                    continue;
                                 kTemplCount[8]++;
                                 ret++;
                                 //bm128 t123456789 = t12345678;
                                 //t123456789 |= *digitTemplates[8][t9];
                                 if(ret % 10000 == 0) {
                                    printf("Sol: %llu", ret);
                                    for(int d = 0; d < 8; d++) {
                                       printf("\t%d", kTemplCount[d]); //kTemplCount[8] is the number of solutions
                                    }
                                    printf("\n");
                                 }
                              }
                           }
                        }
                     }
                  }
               }
            }
         }
      }
      for(int d = 0; d < 9; d++) {
         printf("%d ", kTemplCount[d]); //kTemplCount[8] is the number of solutions
      }
      printf("\t(pass 3) tCount=%d\n", tCount);
   }
exit:
   free(digitTemplates[0]);
   return ret;
}


[coloin]

Well that is neat [if i understand it]. But that only eliminates templates. It is not surprising that the templates in EM which are lost are similar to those connected to the SK loop.

The <n> level refers to the n-rookery eg 4-rookery with <1267> clue values.

It looks like we would be up to the <5> and more level before eliminations are made in our hard puzzles.

Insertions all come in before <8> as i said before.

C

[champagne]

Hi all,

coloin pushes me through pm to share my experience in that discussion.

As I am on the beach for several weeks, I do it from memory.

I use a specific technic in my solver for hardest puzzles.

That process is derived form Allan Barker model based on sets analysis.

I apply that model in quite specific conditions that are not so far from what is discussed here.

I take the PM at the point where the "simple" chains are not sufficient.

I named "floor" the partial PM specific to one candidate. This is likely the same as a rookery, but I am not 100% sure.

I combine several floors and look for the possible eliminations with such a combination.

By construction, if a puzzle has an EXOCET pattern (many of the hardest puzzles have one), the lowest number of floors to have an elimination is at maximum

3 if it is a "fata morgana" type EXOCET
4 if it is a "Golden Nugget" type EXOCET.

As far as I remember, I have never seen a puzzle requiring more than 5 floors to come to an elimination when the puzzle was locked. This can come from memory with a SK loop pattern.

In fact, in my solver, I never use directly the results of that search. It's to close to a pure T&E solution.

I nervertheless use it to build the big rank 0 or nearly rank 0 logic based on specific patterns.

The program detects EXOCETS in a different way. (and finds the SK loop as a chain)

champagne

[David P Bird]

Champagne, like you I have reservations about the methods that I will employ. In my case I'll only employ patterns if they have a general proof, so I tried to find one for your Exocet eliminations and started a thread in the Programmers forum on the topic. I should quickly admit that it took me far too long to realise that the signature pattern of four cells in the same band of boxes isn't sufficient to guarantee the eliminations and further checks are required.

In the context using templates the following points may be helpful:

In all cases the Exocet digits will not exist as givens in the band containing the signature pattern. This provides a search method based on colouring: taking one band at a time, identify the digits that don’t occur as givens anywhere in that band. If there are at least three of them, colour the cells containing only these candidates red, and colour those containing none of them blue.

The required signature pattern is:

| 1 1 2 | ` ` ` | ` ` ` |
| ` ` ` | ` ` 2 | ` ` _ |
| ` ` ` | ` ` _ | ` ` 2 |

1 = contains only non-givens, 2 = contains no non-givens, _ = cells where non-Exocet candidates may possibly be eliminated.

As can be seen, there must be a diagonal of mini-lines containing at least one blue cell, one of which must accompanied by two red cells.

The Exocet digits are the combined candidates in the pair of red cells and give the templates to check. (Fata Morgana has 3 and Golden Nugget 4 as you say).

Certainly if the search is made before any multi-digit inference paths have been used, the two elimination cells will both contain the full set of Exocet digits in addition to any exclusion digits – this is the way you identify the signature pattern, but I'm not sure if it will always be true otherwise.

I've been looking without success for a puzzle where the use of multi-digit chains will reduce a set of cells to an Exocet pattern that has eliminations. So far it seems that either they are present from the start or not at all. For an example of a double Exocet signature pattern with no exclusions see the second grid in < this post >

David PB

[ronk]

For an example of a double Exocet signature pattern with no exclusions see the second grid in < this post >

As you've observed, the three-digit ALS or four-digit AALS is only part of the requirement for this pattern.

[champagne]

Champagne,

. So far it seems that either they are present from the start or not at all. For an example of a double Exocet signature pattern with no exclusions see the second grid in < this post >

David PB

I had a look to the thread you indicate here and feel I would have to add a comment in that thread as well. This is not a forum I follow on a regular basis, but I think I am registered.

To come to your point.

I also tried to see whether EXOCETS had a specific pattern that could be a base for the search.
As you I have been disappointed.

One important point that most seem to have forgotten is the underlying logic of the EXOCET. Here is the process applied by my solver to find them.

a) Find 2 cells that could be a base for an EXOCET (four digits, same row or column, same box)
b) study separately each floor (rookery??) and look for unavoidable pairs of candidates out of the base.
c) see if some pairs are shared by the four digits, then you have an exocet pattern.

That process detects all EXOCETs and makes no assumption on the final pattern, but I believe that they all have the pattern you describe.
That process also finds "quasi EXOCETS" as in "platinium blonde".

You can find a wider collection of EXOCETS in my database for hardest

here

but EXOCET can be found in much easier puzzles.

The process applied to find unavoidable pairs is also a brute force process, but it is applied in a very limited context, so I considered that it was acceptable, applied to very hard puzzles.

On top of that, if one uses as clue the pattern you mention, it is just a validation of a potential target for the EXOCET.

Last but not least, on a solver point of view, direct eliminations is one point, the main property of the EXOCET remains important:

if "ab" is the couple of digits solving the base, then "ab" is the couple of digits solving the target.

champagne

[daj95376]

Well that is neat [if i understand it]. But that only eliminates templates. It is not surprising that the templates in EM which are lost are similar to those connected to the SK loop.

The <n> level refers to the n-rookery eg 4-rookery with <1267> clue values.

It looks like we would be up to the <5> and more level before eliminations are made in our hard puzzles.

Insertions all come in before <8> as i said before.

I was of the opinion that the more templates used ... then more eliminations would result. Now, that doesn't seem to be true. Consider these results using 7-templates.

Code: Select all

 +-----------------------+
 | . . . | . . . | . . 7 |
 | . 2 . | 4 . . | . 6 . |
 | 1 . . | . . . | 5 . . |
 |-------+-------+-------|
 | . 9 . | . . 2 | . 4 . |
 | . . . | 8 . . | 6 . . |
 | 6 . . | 9 . . | . . . |
 |-------+-------+-------|
 | . . 5 | . . 3 | . . . |
 | . 3 . | . 8 . | . 2 . |
 | 7 . . | . . 4 | . . 1 |
 +-----------------------+  # Tungston Rod

     b3  Naked  Quad                     <> 1389 r1c7,r3c9

 +--------------------------------------------------------------------------------+
 |  34589   4568    34689   |  12356   123569  15689   |  24      1389    7       |
 |  3589    2       3789    |  4       13579   15789   |  1389    6       389     |
 |  1       4678    346789  |  2367    23679   6789    |  5       389     24      |
 |--------------------------+--------------------------+--------------------------|
 |  358     9       1378    |  13567   13567   2       |  1378    4       358     |
 |  2345    1457    12347   |  8       13457   157     |  6       13579   2359    |
 |  6       14578   123478  |  9       13457   157     |  12378   13578   2358    |
 |--------------------------+--------------------------+--------------------------|
 |  2489    1468    5       |  1267    12679   3       |  4789    789     4689    |
 |  49      3       1469    |  1567    8       15679   |  479     2       4569    |
 |  7       68      2689    |  256     2569    4       |  389     3589    1       |
 +--------------------------------------------------------------------------------+
 # 186 eliminations remain

Value Templates
  1  =    30
  2  =    10
  3  =    75
  4  =    24
  5  =    42
  6  =    28
  7  =    57
  8  =    97
  9  =    56

 <1234578>-templates     r5c8<>9
   elims = 1

 <1234678>-templates     r4c4,r456c5<>5
   elims = 4

 <1235678>-templates     r2c5<>3
   elims = 1

 <1245678>-templates     r4c4<>3
   elims = 1


Yes, there are also examples of 7-templates that perform more eliminations, but you can't say that just any 7-template will be productive.

Code: Select all

 <1234567>-templates     r1c1<>35; r1c4<>25; r1c5<>239; r2c5<>139; r2c6<>57;
                         r3c3<>47; r3c5<>36; r4c4<>357; r4c7<>13; r56c5<>15;
                         r5c8<>39; r6c7<>23; r3c9<>2; r3c2,r1c7,r78c9<>4;
                         r5c1,r49c5,r18c6,r56c9<>5; r78c4<>6;
                         r3c6,r5c3,r6c3,r7c57<>7; r4c1,r6c2<>8
   elims = 50

 <1345678>-templates     r2c5<>39; r3c5<>36; r4c4<>35; r1c5<>3; r3c2,r7c9<>4;
                         r15c1,r1c4,r4569c5,r128c6,r56c9<>5; r78c4<>6;
                         r3c36,r7c7<>7; r17c2<>8; r8c79<>9
   elims = 30


[ronk]

I was of the opinion that the more templates used ... then more eliminations would result. Now, that doesn't seem to be true.

I think the "more templates leads to more eliminations" concept holds as one adds a template for another digit. IOW <abcdef>-templates results in at least the same eliminations as <abcde>-templates. Comparing the results of <abcde>-templates to <abdfgh>-templates is meaningless AFAIK.

On the high end, 9-templates directly provides the solution, obviously. Can 8-templates also lead to the solution? In a valid puzzle requiring only 8 clue values, most likely so, but in general, I'm not so sure.

For the Tungsten (Tungston) Rod above, if you have the time, I would like to know the eliminations for <134567>-templates.

[daj95376]

For the Tungsten Rod above, I would like to know the eliminations for <134567>-templates.

All of the 6-template results:

Code: Select all

 <123467>-templates      r4c4,r456c5<>5
   elims = 4
   combinations = 19561

 <123567>-templates      r2c5<>3
   elims = 1
   combinations = 3922

 <124567>-templates      r4c4<>3
   elims = 1
   combinations = 3337

 <134567>-templates      r2c5<>39; r3c5<>36; r4c4<>35; r1c5<>3; r3c2<>4;
                         r15c1,r1c4,r4569c5,r128c6,r56c9<>5; r78c4<>6;
                         r3c36,r7c7<>7
   elims = 25
   combinations = 282

 <134678>-templates      r4c4,r456c5<>5
   elims = 4
   combinations = 57666

 <135678>-templates      r2c5<>3
   elims = 1
   combinations = 2963

 <145678>-templates      r4c4<>3
   elims = 1
   combinations = 3536