The New Sudoku Players' Forum

[rjamil]

Hi everyone,

After I have converted my Boolean Sudoku Solver in to Binary Sudoku Solver program successfully, I am thinking to implement the Naked/Hidden pair, triplet and quad eliminations method.

I need your advise as how your solver eliminate programmatically if naked pair/triplet found within a chute, i.e., within three common cells of box and either row or column (within two units at a same time). I think, once naked pair/triplet found within a chute, the digits should be eliminated from remaining cells' possibilities/givens of affected box and either row or column at the same time. In this case, the naked pair/triplet is considered as found within both affected units.

Fyi, there are total 54 chutes in 9x9 Sudoku grid and there are three combinations of cells for searching naked pair within one chute; and one combination of cells for searching naked triplet within one chute.

Will a search routine find two/three digits combination within a chute first then remaining combination of two/three cells within a unit, i.e., row, column or box?

Will this method reduce the naked pair by 162 and triplet by 54 times searching?

[JasonLion]

Most commonly the search is only done within houses, and the two different houses that contain the kind of naked pairs you are talking about are considered as separate applications of the technique. There is nothing wrong with doing things the way you describe, though I suspect it will be a little slower.

[rjamil]

Hi Jason,

Thanks for the consideration.

First of all, I apologize for misunderstanding what is chute and wrongly mentioned instead of three box-line cells.

I think searching within three box-line cells for naked pair/triplet are exactly same as box-line intersection removal, or maybe I am wrong?

If we enumerate all combinations for pair and triplet, then we must eliminate 162 and 54 box-line combinations respectively.

R. Jamil

[rjamil]

Hi all,

I got one example from this site,

I need to know how naked pair {5,9} searched will affect the cells within row and box at the same time?

[rjamil]

Hi,

I am trying to code Naked/Hidden pair/triple elimination within one routine. Algorithm taken as per this site, Jongware explanation for triple in bit manipulation.

Here is my idea in C like pseudo code:

Code: Select all

  for(int y = 0; y < 27; ++y)
    for(int a = 0; a < 9; ++a)
      for(int aa = a + 1; aa < 9; ++aa)
      {
        if(bc[g[l[y][a]] | g[l[y][aa]]] == 2)
        {                    // Found Naked pair Candidates
                             // Backup unit other cells Candidates
                             // Remove Naked pair Candidates from unit other cells Candidates
          if(solve(p))
            return 1;
                             // Restore unit other cells Candidates
        }
        if(bc[g[l[y][a]] & g[l[y][aa]]] == 2)
        {                    // Found Hidden pair Candidates
                             // Backup cells Candidates
                             // Remove other than Hidden pair Candidates from cells Candidates
          if(solve(p))
            return 1;
                             // Restore cells Candidates
        }
        for(int aaa = aa + 1; aaa < 9; ++aaa)
        {
          if(bc[g[l[y][a]] | g[l[y][aa]] | g[l[y][aaa]]] == 3)
          {                  // Found Naked triple Candidates
                             // Backup unit other cells Candidates
                             // Remove Naked triple Candidates from unit other cells Candidates
            if(solve(p))
              return 1;
                             // Restore unit other cells Candidates
          }
          if(bc[(g[l[y][a]] & g[l[y][aa]]) |
            (g[l[y][a]] & g[l[y][aaa]]) |
            (g[l[y][aa]] & g[l[y][aaa]])] == 3)
          {                  // Found Hidden triple Candidates
                             // Backup cells Candidates
                             // Remove other than Hidden triple Candidates from cells Candidates
            if(solve(p))
              return 1;
                             // Restore cells Candidates
          }
        }
      }

Where:
int bc[512] containing Zhou's int TblNumberOne[512] array of 9 bits counts
int g[81] contains bit wise each cell candidates
int l[27][9] contains each unit's 9 cell positions
int p is current cell position
This piece of code is part of solve() function, comes after Naked and Hidden Single routine and before Box-Line elimination routine.

I haven't completed code and checked whether it is working or not. However, it is easy to implement Naked Quad by applying fourth loop and check if(bc[g[l[y][a]] | g[l[y][aa]] | g[l[y][aaa]] | g[l[y][aaaa]]] == 4).

Now, I need to know how to find Hidden Quad. Will any one give me some idea?

R. Jamil

[rjamil]

Hi,

I need someone's confirmation regarding Naked/Hidden Quad checking routine as per below given pseudo code:

Code: Select all

  for(int y = 0; y < 27; ++y)
    for(int A = 0; A < 9; ++A)
      for(int B = A + 1; B < 9; ++B)
        for(int C = B + 1; C < 9; ++C)
          for(int D = C + 1; D < 9; ++D)
          {
            if(bc[g[l[y][A]] | g[l[y][B]] | g[l[y][C]] | g[l[y][D]]] == 4)
            {                // Found Naked quad Candidates
                             // Backup unit other cells Candidates
                             // Remove Naked quad Candidates from unit other cells Candidates
              if(solve(p))
                return 1;
                             // Restore unit other cells Candidates
            }
            if(bc[(g[l[y][A]] & g[l[y][B]]) |
              (g[l[y][A]] & g[l[y][C]]) |
              (g[l[y][A]] & g[l[y][D]]) |
              (g[l[y][B]] & g[l[y][C]]) |
              (g[l[y][B]] & g[l[y][D]]) |
              (g[l[y][C]] & g[l[y][D]])] == 4)
            {                // Found Hidden quad Candidates
                             // Backup cells Candidates
                             // Remove other than Hidden quad Candidates from cells Candidates
              if(solve(p))
                return 1;
                             // Restore cells Candidates
            }
          }

R. Jamil

[rjamil]

Hi,

Noticed that my this post has been moved from 'Advanced solving techniques' to 'Software' index.

Anyway, now I am rethinking naked/hidden pair/triple searching by enumerating tuples within each unit. As per my understandings, for pair, there are total 36 combinations per unit; for triple, there are total 84 combinations per unit; for quad, there are total 151 combinations per unit; 27 units per 9x9 Sudoku board and 9 cells per unit. I have already enumerated units' cells in my program as l[27][9] array. Enumerating each tuple's combination per unit as follows:

Code: Select all

           T[271][9] = {     // Pair/Triple/Quad Tuples Cell positions first then remaining Unit Cell positions
                             // 36 Pairs
  { 0, 1, 2, 3, 4, 5, 6, 7, 8},
  { 0, 2, 1, 3, 4, 5, 6, 7, 8},
...
  { 0, 9, 1, 2, 3, 4, 5, 6, 7},
  { 1, 2, 0, 3, 4, 5, 6, 7, 8},
...
  { 1, 9, 0, 2, 3, 4, 5, 6, 7},
...
...
  { 7, 8, 0, 1, 2, 3, 4, 5, 6},
                             // 84 Triples
  { 0, 1, 2, 3, 4, 5, 6, 7, 8},
  { 0, 1, 3, 2, 4, 5, 6, 7, 8},
...
...
  { 6, 7, 8, 0, 1, 2, 3, 4, 5},
                             // 151 Quads
  { 0, 1, 2, 3, 4, 5, 6, 7, 8},
  { 0, 1, 2, 4, 3, 5, 6, 7, 8},
...
...
  { 5, 6, 7, 8, 0, 1, 2, 3, 4}
}

After enumerating all possible combinations of pair/triple/quad tuples, following proposed pseudo code will be used for searching:

Code: Select all

  for(int y = 0; y < 27; ++y)
    for(int a = 0; a < 36; ++a)
    {                        // Search Naked pairs
      if(bc[g[l[y][T[a][0]]] | g[l[y][T[a][1]]]] == 2)
      {
// Do naked pair elimination
      }
      if(bc[g[l[y][T[a][0]]] & g[l[y][T[a][1]]]] == 2)
      {
// Do Hidden pair elimination
      }
    }
    for(int a = 36; a < 120; ++a)
    {
//  Do Naked and Hidden Triple elimination checking
    }
    for( int a = 120; a < 271; ++a)
    {
// Do Naked and Hidden Quad elimination checking
    }

In this way, it will reduce 3 common cells within box-line combinations and enumerate both box-line Tuples in single array as follows:
For pair, first 2 common cells, one remaining common cell, 6 line other cells and then 6 box other cells; and
For Triple, first 3 common cells, 6 line other cells and then 6 box other cells.

R. Jamil
-----------------------------
All's well that ends well

[rjamil]

Hi all,

I have completed Naked/Hidden pair/triple/quad routine. However, since enumeration needs more time for hard coding, therefore, unable to test at the moment.

I am sharing my code here for any valuable feedbacks/comments/suggestions.

Code: Select all

  for(y = 0; y < 27; ++y)
  {
    int k[9] = {g[l[y][0]], g[l[y][1]], g[l[y][2]], g[l[y][3]],
      g[l[y][4]], g[l[y][5]], g[l[y][6]], g[l[y][7]], g[l[y][8]]};
                             // Backup unit Cells Candidates
    for(a = 0; a < 36; ++a)  // Search 36 pairs per unit
    {
      if(bc[k[0] | k[1]] == 2 &&
        bc[k[0] & (k[2] | k[3] | k[4] | k[5] | k[6] | k[7] | k[8])])
      {                      // Found Naked pair Candidates
                             // Remove Naked pair Candidates from unit other Cells Candidates
        g[l[y][T[a][2]]] &= ~k[0];
        g[l[y][T[a][3]]] &= ~k[0];
        g[l[y][T[a][4]]] &= ~k[0];
        g[l[y][T[a][5]]] &= ~k[0];
        g[l[y][T[a][6]]] &= ~k[0];
        g[l[y][T[a][7]]] &= ~k[0];
        g[l[y][T[a][8]]] &= ~k[0];
        if(solve(p))
          return 1;
        g[l[y][T[a][2]]] = k[2];
        g[l[y][T[a][3]]] = k[3];
        g[l[y][T[a][4]]] = k[4];
        g[l[y][T[a][5]]] = k[5];
        g[l[y][T[a][6]]] = k[6];
        g[l[y][T[a][7]]] = k[7];
        g[l[y][T[a][8]]] = k[8];
      }              // Restore unit other Cells Candidates
      if(bc[k[0] & k[1]] == 2 && bc[k[0] | k[1]] > 2)
      {                      // Found Hidden pair Candidates
                             // Remove other than Hidden pair Candidates from Cells Candidates
        g[l[y][T[a][0]]] &= k[0] & k[1];
        g[l[y][T[a][1]]] &= k[0] & k[1];
        if(solve(p))
          return 1;
        g[l[y][T[a][0]]] = k[0];
        g[l[y][T[a][1]]] = k[1];
      }                      // Restore Cells Candidates
    }
    for(a = 36; a < 120; ++a)  // Search 84 triples per unit
    {
      if(bc[k[0] | k[1] | k[2]] == 3 &&
        bc[(k[0] | k[1] | k[2]) & (k[3] | k[4] | k[5] | k[6] | k[7] | k[8])])
      {                      // Found Naked triple Candidates
                             // Remove Naked triple Candidates from unit other Cells Candidates
        g[l[y][T[a][3]]] &= ~(k[0] | k[1] | k[2]);
        g[l[y][T[a][4]]] &= ~(k[0] | k[1] | k[2]);
        g[l[y][T[a][5]]] &= ~(k[0] | k[1] | k[2]);
        g[l[y][T[a][6]]] &= ~(k[0] | k[1] | k[2]);
        g[l[y][T[a][7]]] &= ~(k[0] | k[1] | k[2]);
        g[l[y][T[a][8]]] &= ~(k[0] | k[1] | k[2]);
        if(solve(p))
          return 1;
        g[l[y][T[a][3]]] = k[3];
        g[l[y][T[a][4]]] = k[4];
        g[l[y][T[a][5]]] = k[5];
        g[l[y][T[a][6]]] = k[6];
        g[l[y][T[a][7]]] = k[7];
        g[l[y][T[a][8]]] = k[8];
      }              // Restore unit other Cells Candidates
      if(bc[k[0] & k[1] & k[2]] == 3 && bc[k[0] | k[1] | k[2]] > 3)
      {                      // Found Hidden triple Candidates
                             // Remove other than Hidden triple Candidates from Cells Candidates
        g[l[y][T[a][0]]] &= k[0] & k[1] & k[2];
        g[l[y][T[a][1]]] &= k[0] & k[1] & k[2];
        g[l[y][T[a][2]]] &= k[0] & k[1] & k[2];
        if(solve(p))
          return 1;
        g[l[y][T[a][0]]] = k[0];
        g[l[y][T[a][1]]] = k[1];
        g[l[y][T[a][2]]] = k[2];
      }                      // Restore Cells Candidates
    }
    for(a = 120; a < 271; ++a)  // Search 151 quads per unit
    {
      if(bc[k[0] | k[1] | k[2] | k[3]] == 4 &&
        bc[(k[0] | k[1] | k[2] | k[3]) & (k[4] | k[5] | k[6] | k[7] | k[8])])
      {                      // Found Naked quad Candidates
                             // Remove Naked quad Candidates from unit other Cells Candidates
        g[l[y][T[a][4]]] &= ~(k[0] | k[1] | k[2] | k[3]);
        g[l[y][T[a][5]]] &= ~(k[0] | k[1] | k[2] | k[3]);
        g[l[y][T[a][6]]] &= ~(k[0] | k[1] | k[2] | k[3]);
        g[l[y][T[a][7]]] &= ~(k[0] | k[1] | k[2] | k[3]);
        g[l[y][T[a][8]]] &= ~(k[0] | k[1] | k[2] | k[3]);
        if(solve(p))
          return 1;
        g[l[y][T[a][4]]] = k[4];
        g[l[y][T[a][5]]] = k[5];
        g[l[y][T[a][6]]] = k[6];
        g[l[y][T[a][7]]] = k[7];
        g[l[y][T[a][8]]] = k[8];
      }              // Restore unit other Cells Candidates
      if(bc[k[0] & k[1] & k[2] & k[3]] == 4 && bc[k[0] | k[1] | k[2] | k[3]] > 4)
      {                      // Found Hidden quad Candidates
                             // Remove other than Hidden quad Candidates from Cells Candidates
        g[l[y][T[a][0]]] &= k[0] & k[1] & k[2] & k[3];
        g[l[y][T[a][1]]] &= k[0] & k[1] & k[2] & k[3];
        g[l[y][T[a][2]]] &= k[0] & k[1] & k[2] & k[3];
        g[l[y][T[a][3]]] &= k[0] & k[1] & k[2] & k[3];
        if(solve(p))
          return 1;
        g[l[y][T[a][0]]] = k[0];
        g[l[y][T[a][1]]] = k[1];
        g[l[y][T[a][2]]] = k[2];
        g[l[y][T[a][3]]] = k[3];
      }                      // Restore Cells Candidates
    }
  }

[rjamil]

Hi all,

Wish to share my tuples generating routine in C as follows:

Code: Select all

#include <stdio.h>

int main(void)
{
  int x = 0;
   for(int a = 0; a < 9; ++a)
     for(int b = a + 1; b < 9; ++b)
      {
         ++x;
        printf("  { %d, %d", a, b);
        for(int e = 0; e < 9; ++e)
          if(e != a && e != b)
            printf(", %d", e);
        printf("} // %d\n", x);
      }
   for(int a = 0; a < 9; ++a)
     for(int b = a + 1; b < 9; ++b)
       for(int c = b + 1; c < 9; ++c)
        {
          ++x;
          printf("  { %d, %d, %d", a, b, c);
          for(int e = 0; e < 9; ++e)
            if(e != a && e != b && e != c)
              printf(", %d", e);
          printf("}, // %d\n", x);
        }
   for(int a = 0; a < 9; ++a)
     for(int b = a + 1; b < 9; ++b)
       for(int c = b + 1; c < 9; ++c)
         for(int d = c + 1; d < 9; ++d)
          {
            ++x;
            printf("  { %d, %d, %d, %d", a, b, c, d);
            for(int e = 0; e < 9; ++e)
              if(e != a && e != b && e != c && e != d)
                printf(", %d", e);
            printf("}, // %d\n", x);
          }
}

A minor correction in quad, i.e., total number of combination is 126 (I/o 151).

R. Jamil

[David P Bird]

Here's the basis of my spreadsheet function to find naked and hidden tuples that I wrote several years ago

The work grid is a 9x9 array of 'bitvalues' which are long integers that can be handled as sets of 9 bits, one for each digit.
There are also bitvalue arrays for the cell positions that contain each digit as a candidate in each house and masks that store the unassigned digits and cells in every house.

An advantage with spreadsheets is that they only recalculate cells when one of the cells they reference changes, which makes repeat checks very quick. The disadvantage is that functions can only return one argument and can't modify any other cells.

Function LockedSet(Vdomain As Range, PDomain As Range, VMask As Integer, PMask As Integer) As Integer

'Returns the bitvalue of the set of values in the smallest NS or HS in Vdomain or 0 if none exists
'The return value is for the naked locked set digits, use (Vmask - LockedSet) for the complementary hidden set
'Vdomain = the 9 cells for the house in the digit grid (V= values)
'Pdomain = the 9 cells for the house in the position grid (P = positions)
'VMask = the bitvalue of the unresolved digits
'Pmask = the bitvalue of the unresolved positions

Call a Single function to see if any unassigned cell only contains a single digit (a naked single) or if any unassigned digit only occurs in a single position (a hidden single) if no hit then -
Loop through pairs of unassigned digits
.. Determine the set of cells that contain either of them (= Home Cells)
..... and the combined candidate values they hold (= Home Values)
.. Away Cells = PMask – Home Cells
.. Get the combined Away Cell Values
.. Common Values = Home Values AND Away Values
.. If Common Values = 0 go to to next pair (there are no eliminations to make)
.. If Home Cell Count = Home Value Count then the home set is a naked set
.. If Home Cell Count = (Home Value Count – Common Value Count) then the away set is a naked set
Next Pair

If further naked sets are found the function saves the naked/hidden set combination with the smallest set. It only reports the naked set so when it returns the complementary hidden set is calculated and the smaller of the two sets is reported to the user.

It appears that this routine could miss a tuple when there are 9 unresolved cells but I couldn't compose a case to prove that, and in practice I have never been aware of one. (I bet Blue could find one though.)

DPB
.
TAGdpbCoding

[Edit corrected blunder in pseudo code (in red)]

[blue]

Hi David,

It appears that this routine could miss a tuple when there are 9 unresolved cells but I couldn't compose a case to prove that, and in practice I have never been aware of one. (I bet Blue could find one though.)

I'm at a loss here.

Some parts of your "pseudocode/algorithm" seem to make sense, but I'm in a situation where I can't seem to get a start on completing a story like the following: Suppose there's a naked (or hidden) set of N<=4 cells, in house 'h'. Then the algorithm will find it because "...".

Aside: is N=5 in a house with no filled cell(s), the case where you thought I might be able to find something ?

I'm confused here too:

(...)
'VMask = the bitvalue of the unresolved digits
'Pmask = the bitvalue of the unresolved positions

Call a Single function (...) if no hit then -
Loop through pairs of unassigned digits
.. Determine the set of cells that contain either of them (= Home Cells)
..... and the combined candidate values they hold (= Home Values)
.. Away Values = VMask – Home Values
.. Common Values = Home Values AND Away Values
.. If Common Values = 0 go to to next pair (there are no eliminations to make)
(....)
Next Pair

It seems like "Away Values" is being defined as the relative complement of "Home Values" -- "relative" w/rsp to the mask of values that are still unplaced in the house. With that, it seems like "<Common Values> := <Home Values> AND <Away Values>" would always be zero ... an empty bitmask ... and that nothing would ever happen.

Really, I couldn't hope to get started without resolving that issue, but even if you said to remove the line in red, above, I would be at a loss to complete the story. I don't know how to say it well, but the entire process (in that it involves only pairs of digits) seems to be too far removed from actual task at hand, to actually be capable of finding everything that's available ... even if we disregarded houses with 9 empty cells.

Tell me a story. Get me started.
My fingers are crossed, that I'm missing the boat, somewhere in here ...

Best Regards,
Blue.

[David P Bird]

Hi Blue. Sorry in trying to simplify the code I messed up one part of it (in red below).

Here is a test puzzle I used back then to provide an example.

.....1..2.2..3.4....452..6...7.....1.62...38.9.....2...8..635....5.8..4.7..9.....

Code: Select all

 *--------------------------*--------------------------*--------------------------*
 | 3568    3579    3689     | 4678    479     <1>      | 789     3579    <2>      |
 | 1568    <2>     1689     | 678     <3>     6789     | <4>     1579    5789     |
 | 138     1379    <4>      | <5>     <2>     789      | 1789    <6>     3789     |
 *--------------------------*--------------------------*--------------------------*
 | 3458    345     <7>      | 2368-4  459     268-459  | 69      59      <1>      |
 | 145     <6>     <2>      | 147     14579   4579     | <3>     <8>     4579     |
 | <9>     1345    138      | 368-147 1457    68-457   | <2>     57      4567     |
 *--------------------------*--------------------------*--------------------------*
 | 124     <8>     19       | 1247    <6>     <3>      | <5>     1279    79       |
 | 1236    139     <5>      | 127     <8>     27       | 1679    <4>     3679     |
 | <7>     134     136      | <9>     145     245      | 168     123     368      |
 *--------------------------*--------------------------*--------------------------*

There is a (2368)HiddenQuad:r46c46 with the complementary naked quint (14579)r46c5,r5c456

Loop through pairs of unassigned digits in box5 (we get to the (26) pair)
.. Determine the set of cells that contain either of them (= Home Cells) (the 4 quad cells)
..... and the combined candidate values they hold (= Home Values) (all 9 digits!)
.. Away Cells = PMask – Home Cells (the 5 complementary cells)
.. Get the combined Away Cell Values (the locked quint digits)
.. Common Values = Home Values AND Away Values (all 5 locked quint digits)
.. If Common Values = 0 go to to next pair (there are no eliminations to make) (not so)
.. If Home Cell Count = Home Value Count then the home set is a naked set (4 <> 9, => miss)
.. If Home Cell Count = (Home Value Count – Common Value Count) then the away set is a naked set (4 = (9-5) => hit)
Next Pair

The same tuples will be found again when (28) & (68) are used as seed pairs.

The thinking was that any naked set bigger than a single must hold 2 locked digits so use seed pairs and look for their containing cells and the other digits they contain.
Alternatively a pair could be locked in a hidden set, therefore make it a two-tailed test.
When a naked set exists the complementary hidden set will contain some or all of the naked set digits and these are the ones that will be eliminated. If there are no common digits it means that all these eliminations have already been made.

With small unsolved cell numbers this routine must find all possible tuples but I anticipated above some number of unsolved cells I would have to use triples to seed the search as it would be possible for some tuples to slip through undetected. However on testing I found that I could never get this to happen!

David

[blue]

Hi David,

Thanks for the update.

With small unsolved cell numbers this routine must find all possible tuples but I anticipated above some number of unsolved cells I would have to use triples to seed the search as it would be possible for some tuples to slip through undetected.

That seems to be the case.
(Small) naked sets with large hidden complements, can be missed.
There are two examples below.

Code: Select all

.47....5............9...6.2.........56...71.....4..32.7.36..541....32..81..5....3

15 singles, 2 locked candidates -->

+--------------------+-------------------+-------------+
| 36     4     7     | 2   16      136   | 8   5    9  |
| 2368   1358  12568 | 89  5689    35689 | 4   13   7  |
| 38     1358  9     | 7   4       358   | 6   13   2  |
+--------------------+-------------------+-------------+
| 23489  1389  1248  | 89* 125689  15689 | 79* 789* 56 |
| 5      6     28    | 3   289     7     | 1   89   4  |
| 89     7     18    | 4   15689   15689 | 3   2    56 |
+--------------------+-------------------+-------------+
| 7      2     3     | 6   89      89    | 5   4    1  |
| 469    59    456   | 1   3       2     | 79  679  8  |
| 1      89    68    | 5   7       4     | 2   69   3  |
+--------------------+-------------------+-------------+

 * The naked triple in r4 isn't found.

Code: Select all

82...7...7..4..29.5...3...6..5..6.3938.........45..6......5.......8....29.....4..

23 singles, 1 naked pair (c5) -->

+-------------+----------------+------------------+
| 8   2    1  | 69    69  7    | 35    45     345 |
| 7   6    3  | 4     1   5    | 2     9      8   |
| 5   4    9  | 2     3   8    | 17    17     6   |
+-------------+----------------+------------------+
| 2   7    5  | 1     4   6    | 8     3      9   |
| 3   8    6  | 79    27  29   | 15    145    145 |
| 1   9    4  | 5     8   3    | 6     2      7   |
+-------------+----------------+------------------+
| 46  13*  28 | 3679  5   1249 | 1379  1678   13* |
| 46  135  7  | 8     69  149  | 1359  156    2   |
| 9   135  28 | 367   27  12   | 4     15678  135 |
+-------------+----------------+------------------+

 * The naked pair in r7 isn't found.

[rjamil]

Hi David & Blue,

Thanks for your kind consideration and detailed responses.

It appears that this routine could miss a tuple when there are 9 unresolved cells but I couldn't compose a case to prove that, and in practice I have never been aware of one. (I bet Blue could find one though.)

(Small) naked sets with large hidden complements, can be missed.

I am working for Bitwise searching through each combination of Cells in Unit (or House) for Naked/Hidden tuples as follows:

Code: Select all

  for(y = 0; y < 27; ++y)    // Search Naked/Hidden Tuples Candidates within each Unit
  {
    int k[10] = {g[l[y][0]], g[l[y][1]], g[l[y][2]], g[l[y][3]],
          g[l[y][4]], g[l[y][5]], g[l[y][6]], g[l[y][7]], g[l[y][8]], 0};

    for(a = 0; a < 36; ++a)  // Search 36 pairs per Unit
    {
      if(!k[T[a][0]] || !k[T[a][1]])
        continue;            // Check empty Cell Candidate
      k[9] = k[T[a][0]] | k[T[a][1]];
      if(B[k[9]] == 2 && k[9] & (k[T[a][2]] | k[T[a][3]] |
        k[T[a][4]] | k[T[a][5]] | k[T[a][6]] | k[T[a][7]] | k[T[a][8]]))
      {                      // Found Naked pair Candidates
        g[l[y][T[a][2]]] &= ~k[9];
        g[l[y][T[a][3]]] &= ~k[9];
        g[l[y][T[a][4]]] &= ~k[9];
        g[l[y][T[a][5]]] &= ~k[9];
        g[l[y][T[a][6]]] &= ~k[9];
        g[l[y][T[a][7]]] &= ~k[9];
        g[l[y][T[a][8]]] &= ~k[9];
        if(solve(p))
          return 1;
        g[l[y][T[a][2]]] = k[T[a][2]];
        g[l[y][T[a][3]]] = k[T[a][3]];
        g[l[y][T[a][4]]] = k[T[a][4]];
        g[l[y][T[a][5]]] = k[T[a][5]];
        g[l[y][T[a][6]]] = k[T[a][6]];
        g[l[y][T[a][7]]] = k[T[a][7]];
        g[l[y][T[a][8]]] = k[T[a][8]];
      }

      k[9] = ~(k[T[a][2]] | k[T[a][3]] | k[T[a][4]] | k[T[a][5]] |
        k[T[a][6]] | k[T[a][7]] | k[T[a][8]] | W[s[l[y][T[a][2]]]] |
        W[s[l[y][T[a][3]]]] | W[s[l[y][T[a][4]]]] | W[s[l[y][T[a][5]]]] |
        W[s[l[y][T[a][6]]]] | W[s[l[y][T[a][7]]]] | W[s[l[y][T[a][8]]]]) & 511;
      if(B[k[9]] == 2 && B[k[T[a][0]] | k[T[a][1]]] > 2)
      {                      // Found Hidden pair Candidates
        g[l[y][T[a][0]]] &= k[9];
        g[l[y][T[a][1]]] &= k[9];
        if(solve(p))
          return 1;
        g[l[y][T[a][0]]] = k[T[a][0]];
        g[l[y][T[a][1]]] = k[T[a][1]];
      }
    }

    for(; a < 120; ++a)      // Search 84 triples per Unit
    {
      if(!k[T[a][0]] || !k[T[a][1]] || !k[T[a][2]])
        continue;            // Check empty Cell Candidate
      k[9] = k[T[a][0]] | k[T[a][1]] | k[T[a][2]];
      if(B[k[9]] == 3 && k[9] & (k[T[a][3]] | k[T[a][4]] |
        k[T[a][5]] | k[T[a][6]] | k[T[a][7]] | k[T[a][8]]))
      {                      // Found Naked triple Candidates
        g[l[y][T[a][3]]] &= ~k[9];
        g[l[y][T[a][4]]] &= ~k[9];
        g[l[y][T[a][5]]] &= ~k[9];
        g[l[y][T[a][6]]] &= ~k[9];
        g[l[y][T[a][7]]] &= ~k[9];
        g[l[y][T[a][8]]] &= ~k[9];
        if(solve(p))
          return 1;
        g[l[y][T[a][3]]] = k[T[a][3]];
        g[l[y][T[a][4]]] = k[T[a][4]];
        g[l[y][T[a][5]]] = k[T[a][5]];
        g[l[y][T[a][6]]] = k[T[a][6]];
        g[l[y][T[a][7]]] = k[T[a][7]];
        g[l[y][T[a][8]]] = k[T[a][8]];
      }

      k[9] = ~(k[T[a][3]] | k[T[a][4]] | k[T[a][5]] | k[T[a][6]] | k[T[a][7]] |
        k[T[a][8]] | W[s[l[y][T[a][3]]]] | W[s[l[y][T[a][4]]]] |
        W[s[l[y][T[a][5]]]] | W[s[l[y][T[a][6]]]] | W[s[l[y][T[a][7]]]] |
        W[s[l[y][T[a][8]]]]) & 511;
      if(B[k[9]] == 3 && B[k[T[a][0]] | k[T[a][1]] | k[T[a][2]]] > 3)
      {                      // Found Hidden triple Candidates
        g[l[y][T[a][0]]] &= k[9];
        g[l[y][T[a][1]]] &= k[9];
        g[l[y][T[a][2]]] &= k[9];
        if(solve(p))
          return 1;
        g[l[y][T[a][0]]] = k[T[a][0]];
        g[l[y][T[a][1]]] = k[T[a][1]];
        g[l[y][T[a][2]]] = k[T[a][2]];
      }
    }

    for(; a < 246; ++a)      // Search 126 quads per Unit
    {
      if(!k[T[a][0]] || !k[T[a][1]] || !k[T[a][2]] || !k[T[a][3]])
        continue;            // Check empty Cell Candidate
      k[9] = k[T[a][0]] | k[T[a][1]] | k[T[a][2]] | k[T[a][3]];
      if(B[k[9]] == 4 && k[9] & (k[T[a][4]] | k[T[a][5]] |
        k[T[a][6]] | k[T[a][7]] | k[T[a][8]]))
      {                      // Found Naked quad Candidates
        g[l[y][T[a][4]]] &= ~k[9];
        g[l[y][T[a][5]]] &= ~k[9];
        g[l[y][T[a][6]]] &= ~k[9];
        g[l[y][T[a][7]]] &= ~k[9];
        g[l[y][T[a][8]]] &= ~k[9];
        if(solve(p))
          return 1;
        g[l[y][T[a][4]]] = k[T[a][4]];
        g[l[y][T[a][5]]] = k[T[a][5]];
        g[l[y][T[a][6]]] = k[T[a][6]];
        g[l[y][T[a][7]]] = k[T[a][7]];
        g[l[y][T[a][8]]] = k[T[a][8]];
      }
      k[9] = ~(k[T[a][4]] | k[T[a][5]] | k[T[a][6]] | k[T[a][7]] | k[T[a][8]] |
        W[s[l[y][T[a][4]]]] | W[s[l[y][T[a][5]]]] | W[s[l[y][T[a][6]]]] |
        W[s[l[y][T[a][7]]]] | W[s[l[y][T[a][8]]]]) & 511;
      if(B[k[9]] == 4 && B[k[T[a][0]] | k[T[a][1]] | k[T[a][2]] | k[T[a][3]]] > 4)
      {                      // Found Hidden quad Candidates
        g[l[y][T[a][0]]] &= k[9];
        g[l[y][T[a][1]]] &= k[9];
        g[l[y][T[a][2]]] &= k[9];
        g[l[y][T[a][3]]] &= k[9];
        if(solve(p))
          return 1;
        g[l[y][T[a][0]]] = k[T[a][0]];
        g[l[y][T[a][1]]] = k[T[a][1]];
        g[l[y][T[a][2]]] = k[T[a][2]];
        g[l[y][T[a][3]]] = k[T[a][3]];
      }
    }
  }

Where:
y integer iterates 27 times for each Unit
k array is used to keep 9 Cells original Candidates for rollback purpose
g array holds 81 Cells 9 Candidates (givens)
l array holds 9 Cell positions per Unit
a integer iterates 36 times for each pair combination per Unit
T array holds 246 enumerated combinations of 9 Cells per Unit (tuples), i.e., first 36 for pair, next 84 for triple and last 126 for quad
B array holds 512 enumerated combinations of 9 bit count
W array holds 10 enumerated single bit per digit, i.e., { 0, 1, 2, 4, 8, 16, 32, 64, 128, 256}.
p integer iterates empty cell position.

please note that the code is not finalized yet as I am still under testing phase of my routine. However, thanks for providing such an appropriate example puzzles for rigorous testing purpose.

Updated 20151007:
I made some fine tuning in Hidden tuples, i.e., included filled cells checking.
I have checked and found both Naked and Hidden Tuples are now working fine.
I have taken only one puzzle from this for Hidden Quad checking purpose:

Code: Select all

901500046425090081860010020502000000019000460600000002196040253200060817000001694

Regards,
R. Jamil

[David P Bird]

Blue, thank you very much for proving that my suspicions were right - excellent work!

Regarding your second example, when I converted my VB routine into pseudo code I missed a trap that catches that situation. As I accumulate the cells that contain the seed digits I count those that exactly match that pair so if a naked pair exists it is returned immediately and the function quits. (Looking at the code so long after I wrote it I thought that this was just a time-saving measure.)

So now the question is what is the maximum number of unresolved cells that my routine (as it stands) is guaranteed to find every tuple?

The function is called repeatedly as the grid is reduced at the start of a puzzle and during that phase I wouldn't use an extended routine. This is because the chances are high that it wouldn't be needed because A) the tuples in those houses could be found anyway and B) that other eliminations will come to the rescue.

David
.