The New Sudoku Players' Forum

[denis_berthier]

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.

[eleven]

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

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

[David P Bird]

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

[dobrichev]

Mladen,
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);
   }
}


Meanwhile I made some minor modifications on the previously published code. Here is the latest version.

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

[daj95376]

Mladen,
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();
};


[eleven]

Here it is.

Many thanks.

[dobrichev]

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]

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

[denis_berthier]

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)

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
[add some exit condition]

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.

What "additional eliminations" are?

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

[dobrichev]

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

[denis_berthier]

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):

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.
Can your program compute TD(P)?

[daj95376]

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.

[ronk]

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.

[daj95376]

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

[ronk]

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