## New Solving Technique (I think)

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

### Re: New Solving Technique (I think)

Hi dobrichev,
There are indeed two different topics discussed in this thread:
- one using templates as in the pure form Ruud/pjb 's algorithm
- one using k-templates
I'm referring only to the first, with my definition for a template (equivalent to Ruud's and daj's) and associated concepts (compatibility, ...)

The algorithm wrt which I raised my questions was inspired by the pure form of Ruud's idea; there are no candidates and therefore no "additional eliminations".
By "template-single" I mean that, at the step under consideration, there remains only one possible template for the current digit, compatible (in the sense of my above definition) with the givens and the templates for the previous digits.
Using the 9! permutations of digits, the problem can be rephrased as: find a permutation that maximizes the number of final template-singles.

It is obvious that TD(P) =< 8 for any minimal P (once templates for 8 digits are fixed, there can only be one possibility for the 9th).
The 1st question is: is the real upper bound smaller?
The 2nd question is: is TD(P) somehow correlated with complexity? If the answer is negative, the whole idea may be of little value.
denis_berthier
2010 Supporter

Posts: 1261
Joined: 19 June 2007
Location: Paris

### Re: New Solving Technique (I think)

dobrichev wrote:Number of iterations of each of the 9 nested loops (code is here).

could you also post the way, how you fill the allTemplates[ ] please. That seems to be all i am missing to run it.
eleven

Posts: 1904
Joined: 10 February 2008

### Re: New Solving Technique (I think)

ronk wrote:Like Ruud wrote here, "I ... wonder if it could be used to detect new patterns and deductive rules."

That's my objective as I try to assimilate the work here.

This is Tungsten Rod stripped of all candidates other than the (157)Exocet digits with the rows of interest starred.
Code: Select all
` |-------------|-----------------|-------------| | 5   5       | 15   15    15   |     1   7   | *| 5       7   |      157#  157  | 1           |*  | 1   7   7   | 7    7     7    | 5           |  |-------------|-----------------|-------------|*| 5       17  | 157  157        | 17      5   |* | 5   157 17  |      157   157# |     157 5   |  |     157 17  |      157   157# | 17  157 5   |  |-------------|-----------------|-------------| |     1   5   | 17   17         | 7   7       | *|         1   | 157#       157  | 7       5   |*  | 7           | 5    5          |     5   1   |  |-------------|-----------------|-------------|`

From Exocet logic, if r2c5 holds (a) and r8c4 holds (b), r56c6 will hold (ab).
This requires r2b13 to hold (b), r4b46 to hold (ab), and r8b79 to hold (a)
If (ab) = (17) then whichever way round they occur in r4, one or other of r2 or r8 won't be able to hold either of them.
This therefore proves that (5) is a member of (ab) allowing it to be eliminated from 13 cells.

The configuration of (17) in r248c37 could possibly be considered to be an extension pattern to the basic Exocet one as I use it.

PS I'm using the Queens English spelling of Tungsten
David P Bird
2010 Supporter

Posts: 1040
Joined: 16 September 2008
Location: Middle England

### Re: New Solving Technique (I think)

could you also post the way, how you fill the allTemplates[ ] please. That seems to be all i am missing to run it.

Here it is.
Hidden Text: Show
Code: Select all
`struct templates {   bm128 allTemplates[46656];   bm128 colTemplates[9][5184];   void init();   unsigned long long nSol(const char *p);   templates();   void getComplementaryTemplates();   //void get3rookeries();   void get2templates();   void get3templates();   void templatePlus1();   void templates2rookeries();};templates::templates() {   init();}void templates::init() {   int nTemplates = 0;   for(int r1c = 0; r1c < 9; r1c++) { //row 1 columns      int r1box = r1c / 3;      int nColTemplates = 0;      for(int r2c = 0; r2c < 9; r2c++) {         int r2box = r2c / 3;         if(r2box == r1box)            continue;         for(int r3c = 0; r3c < 9; r3c++) {            int r3box = r3c / 3;            if(r3box == r1box || r3box == r2box)               continue;            for(int r4c = 0; r4c < 9; r4c++) {               int r4box = r4c / 3;               if(r4c == r1c || r4c == r2c || r4c == r3c)                  continue;               for(int r5c = 0; r5c < 9; r5c++) {                  int r5box = r5c / 3;                  if(r5box == r4box || r5c == r1c || r5c == r2c || r5c == r3c)                     continue;                  for(int r6c = 0; r6c < 9; r6c++) {                     int r6box = r6c / 3;                     if(r6box == r4box || r6box == r5box || r6c == r1c || r6c == r2c || r6c == r3c)                        continue;                     for(int r7c = 0; r7c < 9; r7c++) {                        int r7box = r7c / 3;                        if(r7c == r1c || r7c == r2c || r7c == r3c || r7c == r4c || r7c == r5c || r7c == r6c)                           continue;                        for(int r8c = 0; r8c < 9; r8c++) {                           int r8box = r8c / 3;                           if(r8box == r7box || r8c == r1c || r8c == r2c || r8c == r3c || r8c == r4c || r8c == r5c || r8c == r6c)                              continue;                           for(int r9c = 0; r9c < 9; r9c++) {                              int r9box = r9c / 3;                              if(r9box == r7box || r9box == r8box || r9c == r1c || r9c == r2c || r9c == r3c || r9c == r4c || r9c == r5c || r9c == r6c)                                 continue;                              //this combination of r1c..r9c conforms Sudoku rules for valid locations of a single digit                              bm128 t;                              t.clear();                              t.setBit(r1c);                              t.setBit(9 + r2c);                              t.setBit(18 + r3c);                              t.setBit(27 + r4c);                              t.setBit(36 + r5c);                              t.setBit(45 + r6c);                              t.setBit(54 + r7c);                              t.setBit(63 + r8c);                              t.setBit(72 + r9c);                              allTemplates[nTemplates++] = t;                              colTemplates[r1c][nColTemplates++] = t;                           }                        }                     }                  }               }            }         }      }   }}void countSolutions () {   templates x;   char buf[1000];   while(fgets(buf, sizeof(buf), stdin)) {      ch81 puz;      puz.fromString(buf);      printf("%s", buf);      x.nSol(puz.chars);   }}`

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;   ch81 prBuf; //print buffer for debugging/explaining#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:      printf("\nSurvived templates\n");      for(int d = 0; d < 9; d++) {         for(int t = 0; t < validCount[d]; t++) {            digitTemplates[d][t]->toMask81('1' + d, prBuf.chars);            printf("%81.81s\t%d\n", prBuf.chars, t + 1);         }      }      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]; //all cells except givens are candidates for digit d         for(int t = 0; t < validCount[d]; t++) {            duplicates |= (allPoss & *digitTemplates[d][t]);            allPoss |= *digitTemplates[d][t];            newSolvedCells &= *digitTemplates[d][t]; //d is not in this cell for at least one template, leave cell unsolved.         }         //add to newly solved cells these having this digit as only candidate         bm128 allDigitPoss = maskLSB[81].m128i_m128i; //all cells are candidates for digit 2         for(int d2 = 0; d2 < 9; d2++) {            if(d2 == d)               continue;            for(int t2 = 0; t2 < validCount[d2]; t2++) {               allDigitPoss.clearBits(*digitTemplates[d2][t2]); //exclude cells where at least one <> d candidate exists            }         }         allDigitPoss.clearBits(clues[d]); //remove also previously known givens         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 conflict;            for(int d2 = 0; d2 < 9; d2++) {               if(d1 == d2)                  continue;               conflict = 1;               for(int t2 = 0; t2 < validCount[d2]; t2++) {                  if(digitTemplates[d1][t1]->isDisjoint(*digitTemplates[d2][t2])) {                     conflict = 0;                     break; //stop at first found                  }               }               if(conflict) { //invalid template [d1][t1]                  //remove this template from the list                  printf("\nElimination of template %d for digit %d due to conflict with each of the templates for digit %d.\n", t1 + 1, d1 + 1, d2 + 1); //no solution                  digitTemplates[d1][t1] = NULL;                  if(firstRemoved == -1)                     firstRemoved = t1;                  break;               }            }         }         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;}`

Cheers,
MD
dobrichev
2016 Supporter

Posts: 1622
Joined: 24 May 2010

### Re: New Solving Technique (I think)

dobrichev wrote:
could you also post the way, how you fill the allTemplates[ ] please. That seems to be all i am missing to run it.

Here it is.

If I follow your logic correctly, then the memory contents of allTemplates and colTemplates are identical. You can cut your memory usage by using a union and only filling allTemplates.

Code: Select all
`struct templates {   union {      bm128 allTemplates[46656];      bm128 colTemplates[9][5184];   } all_col;   void init();   unsigned long long nSol(const char *p);   templates();   void getComplementaryTemplates();   //void get3rookeries();   void get2templates();   void get3templates();   void templatePlus1();   void templates2rookeries();};`
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

### Re: New Solving Technique (I think)

dobrichev wrote:Here it is.

Many thanks.
eleven

Posts: 1904
Joined: 10 February 2008

### Re: New Solving Technique (I think)

daj95376 wrote:If I follow your logic correctly, then the memory contents of allTemplates and colTemplates are identical. You can cut your memory usage by using a union and only filling allTemplates.

For some of the other functions I need 2 copies, one of them to be modified during the execution. Agree that the population of the array(s) can be optimized but for this task this is of no importance. Working with row-minlex normalized grids exploits the symmetry that in the first row the value is identical to the column number. That is where I use colTemplates array.
dobrichev
2016 Supporter

Posts: 1622
Joined: 24 May 2010

### Re: New Solving Technique (I think)

denis_berthier wrote:The algorithm wrt which I raised my questions was inspired by the pure form of Ruud's idea; there are no candidates and therefore no "additional eliminations".

At least initial givens must be taken into consideration at some point. Doing it at "initialization" phase (no matter how it is implemented and whether "additional eliminations" are performed) all templates passing the test(s) become "candidates". I think there is no contradiction with Ruud's idea. The alternative to loop over all 46K templates and each time to test template against initial givens doesn't add value (I think).
What "additional eliminations" are? I agree this is another matter and for the purposes of the rating a good start point is not to involve complex logic there, or better no logic at all.

Cheers,
MD
dobrichev
2016 Supporter

Posts: 1622
Joined: 24 May 2010

### Re: New Solving Technique (I think)

dobrichev wrote:
denis_berthier wrote:The algorithm wrt which I raised my questions was inspired by the pure form of Ruud's idea; there are no candidates and therefore no "additional eliminations".

At least initial givens must be taken into consideration at some point. Doing it at "initialization" phase (no matter how it is implemented and whether "additional eliminations" are performed) all templates passing the test(s) become "candidates". I think there is no contradiction with Ruud's idea. The alternative to loop over all 46K templates and each time to test template against initial givens doesn't add value (I think).

I think the answers are in my definitions in a previous post, which I recall here:
(in italics, the place where the givens and previous templates are taken into account)

denis_berthier wrote:
Definition: a template is a set of 9 cells such that no two of them see each other.
Definition: two templates are compatible if they are disjoint (as sets of cells).
Definition: a template for a digit k is a template all the cells of which are assigned value k.
Definition: given a puzzle P, a template T for a digit k is compatible with the clues of P if:
- all the clues for digit k in P are in cells of T,
- all the clues for other digits in P are in cells not in T.

Definition: Sudoku problem: find 9 templates, one for each digit, such that:
- each of them is compatible with the clues,
- they are pairwise compatible.

Basic resolution procedure: depth-first-search (DFS), with maximum depth 9
for i=1 to 9
- choose the next template Ti (in the fixed vector of templates) for number i, compatible with the clues and (for i>1) with the previously chosen Tj's
- if no such template can be found, backtrack to the previous value of i

Output (as usual for DFS):
Depending on the exit condition: either 0, 1, n, or all the solutions

Range of application:
any puzzle, with 0, 1 or more solutions

There are no candidates, nowhere. Indeed, templates play the role candidates would play in the usual DFS search.
This is a completely different view of the Sudoku problem.
I think this is the original idea of Ruud. (When candidates are added in the landscape and rules are mixed in, this idea is lost).

The test wrt clues/givens must be made at each step, as clues may contain any digit.

You used this expression. I don't. I have no eliminations.
denis_berthier
2010 Supporter

Posts: 1261
Joined: 19 June 2007
Location: Paris

### Re: New Solving Technique (I think)

Think about "template candidate for a digit" and "template candidate elimination" instead of pencilmark candidate/elimination.
dobrichev
2016 Supporter

Posts: 1622
Joined: 24 May 2010

### Re: New Solving Technique (I think)

dobrichev wrote:Think about "template candidate for a digit" and "template candidate elimination" instead of pencilmark candidate/elimination.

Thanks for repeating what I wrote (except I should have written templates-for-a-digit instead of templates):
denis_berthier wrote:There are no candidates, nowhere. Indeed, templates play the role candidates would play in the usual DFS search.

But it shows we are now on the same line.
denis_berthier
2010 Supporter

Posts: 1261
Joined: 19 June 2007
Location: Paris

### Re: New Solving Technique (I think)

FWIW, Solving a puzzle using templates[46656]:

Code: Select all
`    struct {        bitmap  clues_this_value,     // cells containing this  value  as a clue                clues_other_values;   // cells containing other values as a clue    }   values[10];`

1) Zero values[].

2) Scan the puzzle and set cell information in values[1..9] based on clues encountered.

3) Create a list of indices for all templates[] entries that contain values[i=1].clues_this_value as a subset ... and does not intersect values[i=1].clues_other_values.

4) Repeat step (3) creating lists for i = 2..9 .

5) Find an index from each list such that none of the corresponding templates intersect each other.

6) Assign cell values using the template associated with each index.

NOTE: I never used the words candidate or elimination.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

### Re: New Solving Technique (I think)

daj95376, why program a "pure form" of templating? Merely use pencilmarks, disable all other techniques, and accept only the implicit eliminations of digit assignments (singles) found with the templating technique.

If I'm understanding the "pure form" correctly, the resulting solution path will be the same [edit: when search order is the same].

This then allows a programmed solver to be easily switched between the "pure form" of templating and one combined other logic techniques.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

### Re: New Solving Technique (I think)

ronk wrote:daj95376, why program a "pure form" of templating? Merely use pencilmarks, disable all other techniques, and accept only the implicit eliminations of digit assignments (singles) found with the templating technique.

Hello Ron,

Ruud's/pjb's technique seems to be the focus of the latest discussions. As such, I simply provided an algorithm where the discussions could concentrate on step (5) and get past the other details. That said, my solver doesn't have steps (5 & 6) incorporated as part of the templates() routine. So, I can't just disable other techniques and let templates() solve the puzzle.

BTW: When working with pencilmarks/grid, the data structure needs to be altered and the template must be a subset of "value[~].clues_solved_candidates" in step (3) -- instead of the other way around.

Regards, Danny
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

### Re: New Solving Technique (I think)

daj95376 wrote:BTW: When working with pencilmarks/grid, the data structure needs to be altered and the template must be a subset of "value[~].clues_solved_candidates_grid" in step (3) -- instead of the other way around.

This may be the "partial templates" to which denis_berthier referred not too many posts ago. I simply don't see the need for them. Did you use "partial templates" within your templates() pre-screen for GFF() too?

[edit: IMO the "partial templates" term is oxymoronic.]
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext