## What if Naked pair/triplet found within chute

Programs which generate, solve, and analyze Sudoku puzzles

### Re: What if Naked pair/triplet found within chute

Hi again,

Previously, I had coded for Hidden Single search routine for each unit separately as per Hidden Tuples search routine, i.e., row, column and box wise. Now, after rethinking, I have merged the same code into one check instead of three separate checks for separate unit.

Previously:
Hidden Text: Show
Code: Select all
`    int K = g[r[a]] & (g[r[a]] ^ (g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] |      g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]]));                             // Assign Hidden Candidates Row wise    if (B[K] == 1)           // Check Hidden Single Candidate Row wise      z = K;                 // Assign Hidden Single Candidate    else    {                        // Assign Hidden Candidates Column wise      K = g[r[a]] & (g[r[a]] ^ (g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] |        g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]]));      if (B[K] == 1)         // Check Hidden Single Candidate Column wise        z = K;               // Assign Hidden Single Candidate      else      {                      // Assign Hidden Candidates Box wise        K = g[r[a]] & (g[r[a]] ^ (g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] |          g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]]));        if (B[K] == 1)       // Check Hidden Single Candidate Box wise          z = K;             // Assign Hidden Single Candidate        else          continue;      }    }    x = a;                   // Assign Hidden Single Cell position    y = 1;                   // 1 Represent Hidden Single    goto NHSCF;`

Latest:
Hidden Text: Show
Code: Select all
`    int K = (g[r[a]] & (g[r[a]] ^ (g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] |      g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]]))) |      (g[r[a]] & (g[r[a]] ^ (g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] |      g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]]))) |      (g[r[a]] & (g[r[a]] ^ (g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] |      g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]] | g[w[r[a]]])));                             // Assign Hidden Single Candidates    if (!B[K])               // Skip for Hidden Single Candidate not found      continue;    z = K;                   // Assign Hidden Single Candidate    x = a;                   // Assign Hidden Single Cell position    y = 1;                   // 1 Represent Hidden Single    goto NHSCF;`

Note: Formula simplification possible as follows:
From: (cell & (cell ^ row)) | (cell & (cell ^ box)) | (cell & (cell ^ col))
To: cell & ((cell ^ row) | (cell ^ box) | (cell ^ col))

Updated 20160503:
Replace: if (!B[K])
With: if (!K)

R. Jamil
Last edited by rjamil on Tue May 03, 2016 4:51 pm, edited 1 time in total.
rjamil

Posts: 676
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: What if Naked pair/triplet found within chute

my program uses a SET based approach for solving hidden / naked subsets

I've also expanded the normal RN,CN,BN,RC spaces to include addition information outlined in more detail in this
Post

MY solver in the link show's a simplified version of increasing N digits for triples,quads which i wont out line in full here in}

not sure how much this approach can be used/help with as your using bitset's where i'm using Sets but the logic should be cross platform uniform .. as sets and bitwise operations are almost identical

some alternative notes:
a more compact compressed way to expand by n sizes would be to replace the "digits/postion" variables by a combination function to iterate through the sizes for each class type.

my program has a built in combination function and could do that, but for simplicity I choose to just modify my existing code by increasing it by n variables manually to cover triples,quads.
anyway on to my code....

Code: Select all
`{hidden pairs}procedure HP(k:integer);varxn,yn,n,n2,z:integer;beginFor xn:= 0 to 8 do  {xn sets which Sector is checked}    For n:= 1 to 8 do {digit 1}    for n2:= (n+1) to 9 do {digit 2}        begin                    If   (R[xn,n] > 0) and (R[xn,n] < 3 )             and (R[xn,n2] > 0) and (R[xn,n2] < 3 )             { checks the Sector{Row,Col,Box has an active digits sum of  <3}            { R,C,B are pre calculated total pencil mark count}            then              for yn:= 9 to 44 do {yn is a look up table to pre-calculated combination positions for 2 digits as a SET of [0..8]}                if Rn[xn,n] + Rn[xn,n2] = comboset2[yn]{Rn stores [sector, Col] as a set of positions [0..8] {Cy stores [sector, Row] a set of positions [0..8] {Bxy stores [sector, mini Row x mini col] as a set of positions [0..8] when the Rn,Cy,Bxy saved locals in both digits match the selected position combination of yn, then we have a match for hidden pair and can apply reductions to pencil marks}                   then                   begin                    active:= true;                     for z:= 0 to 8 do                       if z in comboset2[yn]                        then                           covered[rset[xn,z]]:= covered[rset[xn,z]] * [n,n2] * pm[rset[xn,z]];                  end;           If  (C[xn,n] > 0) and (C[xn,n] < 3 )           and (C[xn,n2] > 0) and (C[xn,n2] < 3 )            then              for yn:= 9 to 44 do                if Cn[xn,n] + Cn[xn,n2] = comboset2[yn]                 then                   begin                    active:= true;                     for z:= 0 to 8 do                       if z in comboset2[yn]                        then                           covered[Cset[xn,z]]:= covered[Cset[xn,z]] * [n,n2] * pm[Cset[xn,z]];                  end;           If  (b[xn,n] > 0) and (b[xn,n] < 3 )           and (b[xn,n2] > 0) and (b[xn,n2] < 3 )            then              for yn:= 9 to 44 do                if bn[xn,n] + bn[xn,n2] = comboset2[yn]                 then                   begin                    active:= true;                     for z:= 0 to 8 do                       if z in comboset2[yn]                        then                           covered[bset[xn,z]]:= covered[bset[xn,z]] * [n,n2] * pm[bset[xn,z]];                  end;        end;end;{hidden pair}`

Code: Select all
`{Naked pairs}procedure NP(k:integer);varxn,yn,n,n2,z:integer;beginFor xn:= 0 to 8 do {sector selection}  For n:= 0 to 7 do {position n1}     for n2:= (n+1) to 8 do {position n2}         begin           if(RC[xn,n] <> []) and (RC[xn,n2] <> [])           and (nm[rset[xn,n]] <3) and (nm[rset[xn,n2]] <3){nm[cell] stores a total count of pencil mark digits for a cellRC[sector,postion] stores a set of digits [1..9]  Rc checks that sector set isn't empty Rset[is index reference for calling cell position] Nm checks that a cells pm count is < 3 }            then             for yn:= 9 to 44 do  {yn is a look up table to pre-calculated combination of digits for 2 digits as a SET of [1..9]}              if ( RC[xn,n] + RC[xn,n2] = comboset[yn]){if the RC of both positions matches the set of yn digits then we found a naked set and can apply eliminations}                then                   begin                    active:= true;                     for z:= 0 to 8 do                       if  not (z in [n,n2] )                        then                           covered[rset[xn,z]]:= covered[rset[xn,z]] - comboset[yn];                  end;           if (RC[n,xn] <> []) and (RC[n2,xn] <> [])           and (nm[rset[n,xn]] < 3 ) and (nm[rset[n2,xn]] <3)            then             for yn:= 9 to 44 do              if (RC[n,xn] + RC[n2,xn] = comboset[yn] )                then                   begin                    active:= true;                     for z:= 0 to 8 do                       if  not (z in [n,n2] )                        then                           covered[Cset[xn,z]]:= covered[Cset[xn,z]] - comboset[yn];                  end;           if (Bs[xn,n] <> []) and (BS[xn,n2] <> [])           and (nm[bset[xn,n]] < 3) and (nm[bset[xn,n2]] <3)            then             for yn:= 9 to 44 do              if (BS[xn,n] + Bs[xn,n2] = comboset[yn] )               then                   begin                    active:= true;                     for z:= 0 to 8 do                       if  not (z in [n,n2] )                        then                           covered[Bset[xn,z]]:= covered[Bset[xn,z]] - comboset[yn];                  end;        end;end;{naked pair}`
Last edited by StrmCkr on Mon Apr 25, 2016 9:02 pm, edited 1 time in total.
Some do, some teach, the rest look it up. StrmCkr

Posts: 1303
Joined: 05 September 2006

### Re: What if Naked pair/triplet found within chute

Hi StrmCkr,

Let me explain my bitwise Naked and Hidden pair routine here for easy understanding.
Code: Select all
`For sector = 1 to 27 {i.e., for 9 rows + 9 cols + 9 boxes}Begin  Let unsolved = number of unsolved cells per sector  if unsolved is less then 4 then loop next For sector  For pair = 1 to 36 {pre defined pair cells and other cells for each sector}  Begin    If either pair's first or second cell is solved then loop next For pair    Let pmN = union of sector's pair first and second cells pencil marks    Let pmO = union of sector's pair third to ninth cells pencil marks    If number of pmN pencil marks is equals to 2 then Naked pair found    Begin      If any one or more of pmN pencil marks found in pmO pencil marks then Make a Naked pair move    End If    Let pmH = pmN AND (pmN NOT pmO) {This is a secret move}    If number of pmH Hidden pencil marks is equals to 2 then Make a Hidden pair move  End For pairEnd For sector`

Corrected: Let pmH = pmN AND (pmN OR pmO)

Similarly, for Naked and Hidden triple:
Code: Select all
`For sector = 1 to 27 {i.e., for 9 rows + 9 cols + 9 boxes}Begin  Let unsolved = number of unsolved cells per sector  if unsolved is less then 6 then loop next For sector  For triple = 1 to 84 {pre defined triple cells and other cells for each sector}  Begin    If either triple's first or second or third cell is solved then loop next For triple    Let pmN = union of sector's triple first, second and third cells pencil marks    Let pmO = union of sector's triple forth to ninth cells pencil marks    If number of pmN pencil marks is equals to 3 then Naked triple found    Begin      If any one or more of pmN pencil marks found in pmO pencil marks then Make a Naked triple move    End If    Let pmH = pmN AND (pmN NOT pmO) {This is a secret move}    If number of pmH Hidden pencil marks is equals to 3 then Make a Hidden triple move  End For tripleEnd For sector`

And, for Naked and Hidden Quad:
Code: Select all
`For sector = 1 to 27 {i.e., for 9 rows + 9 cols + 9 boxes}Begin  Let unsolved = number of unsolved cells per sector  if unsolved is less then 8 then loop next For sector  For quad = 1 to 126 {pre defined quad cells and other cells for each sector}  Begin    If either quad's first or second or third or forth cell is solved then loop next For quad    Let pmN = union of sector's quad first, second, third and forth cells pencil marks    Let pmO = union of sector's quad fifth to ninth cells pencil marks    If number of pmN pencil marks is equals to 4 then Naked quad found    Begin      If any one or more of pmN pencil marks found in pmO pencil marks then Make a Naked quad move    End If    Let pmH = pmN AND (pmN NOT pmO) {This is a secret move}    If number of pmH Hidden pencil marks is equals to 4 then Make a Hidden quad move  End For quadEnd For sector`

R. Jamil
rjamil

Posts: 676
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: What if Naked pair/triplet found within chute

looks like we are doing the same thing, i just use different on load defined spaces that add over head but decreases my code executions run time.

Code: Select all
` Let pmH = pmN AND (pmN NOT pmO) {This is a secret move}    If number of pmH Hidden pencil marks is equals to 2 then Hidden pair found      Make a Hidden pair move`

not really a secret move, since each completed set has an equal and opposite set of complementing size
it dose and a nice short cut to your code.
N + H {size + complement}
1 + 8
2 + 7
3 + 6
4 + 5
5 + 4
6 + 3
7 + 2
8 + 1
Some do, some teach, the rest look it up. StrmCkr

Posts: 1303
Joined: 05 September 2006

### Re: What if Naked pair/triplet found within chute

Hi StrmCkr,

Your code is also based on setwise theory; and, in my opinion, looks like same routine as used in David P. Bird's and brian turner's Sudoku solver, i.e., N-loops for N-subsets.

R. Jamil
rjamil

Posts: 676
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: What if Naked pair/triplet found within chute

Hi,

I found another link showing naked triplet within a mini-line (i.e., either mini-row or mini-column) claiming as Y-Wing. This is not normally thought of as a Y-Wing, but rather as a naked triplet.

My question is that, for Y-Wings, there are two types of elimination, either only one cell OR five cells from where elimination will occur. Am I right?

Is it possible to enumerate both types of Y-Wing separately so that three cells containing Y-Wing satisfied candidates with (a) one cell for elimination; and (b) five cells for eliminations?

Let for example, consider a 9x9 Sudoku matrix whose top left cell labeled 0, top right cell labeled 8, bottom left cell labeled 72 and bottom right cell labeled 80.
Code: Select all
`00 01 02 03 04 05 06 07 0809 10 11 12 13 14 15 16 1718 19 20 21 22 23 24 25 2627 28 29 30 31 32 33 34 3536 37 38 39 40 41 42 43 4445 46 47 48 49 50 51 52 5354 55 56 57 58 59 60 61 6263 64 65 66 67 68 69 70 7172 73 74 75 76 77 78 79 80`

For first type of Y-Wing, create two dimensions array of n and 4 values, where n represent number of possible combinations and 4 represent three Y-Wing cells and one elimination cell. (int yw1[n];)
yw1 = {0,3,9,12}; Is this the first combination? or {0,3,27,30}, i.e., all four cells lying in different boxes?
yw1 = {0,4,9,13};
...
yw1 = {0,8,9,17};
yw1 = {0,3,18,21};
...
...
yw1[n] = {68,71,77,80};

For second type of Y-Wing, int yw2[m];
yw2 = {1,3,9,0,2,12,13,14}; is this the first one? i.e., only two boxes used?
...
...
yw2[m] = {68,71,76,66,67,78,79,80};

R. Jamil
rjamil

Posts: 676
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: What if Naked pair/triplet found within chute

Hi,

I have coded prototype for Y-Wings and sharing here for programmers' reviews/comments:
Code: Select all
`// Global variables declarationint B; // contains count bitwise candidates     W = {  {19,25,46,52, 0, 0, 0, 0}, {10,12,64,66, 0, 0, 0, 0},  { 4, 6,76,78, 0, 0, 0, 0}, {18,25,27,34, 0, 0, 0, 0},  { 1,11,73,10,19,56,65,74}, {65,54,66,57,58,59,63,64},  {66, 3,77, 5,14,23,57,75}, {18,10,63, 0, 9,55,64,73},  {20, 1,23, 3, 4, 5,18,19}, {20,10,25,15,16,17,18,19},  {70,43,78,33,42,51,61,79}, {11,18,65, 2,20,54,63,72},  {33,43,69,42,51,61,70,79}};  for (a = 0; a < 4; ++a)    // Search Y-Wings Type 1  {    if (B[g[W[a]] | g[W[a]] | g[W[a]]] == 3 &&      !(g[W[a]] & g[W[a]] & g[W[a]]) &&      (g[W[a]] & g[W[a]] & g[W[a]]))    {      int k = g[W[a]];      g[W[a]] &= ~(g[W[a]] & g[W[a]]);      printf ("%d) Found Y-Wing in Cells %d %d %d remove candidate %d from cell %d\n",        a, W[a], W[a], W[a], b[g[W[a]] & g[W[a]]], W[a]);      if (solve(p))        return 1;      printf ("%d) Restore Y-Wing in Cells %d %d %d remove candidate %d from cell %d\n",        a, W[a], W[a], W[a], b[g[W[a]] & g[W[a]]], W[a]);      g[W[a]] = k;      return 0;    }    if (B[g[W[a]] | g[W[a]] | g[W[a]]] == 3 &&      !(g[W[a]] & g[W[a]] & g[W[a]]) &&      (g[W[a]] & g[W[a]] & g[W[a]]))    {      int k = g[W[a]];      g[W[a]] &= ~(g[W[a]] & g[W[a]]);      printf ("%d) Found Y-Wing in Cells %d %d %d remove candidate %d from cell %d\n",        a, W[a], W[a], W[a], b[g[W[a]] & g[W[a]]], W[a]);      if (solve(p))        return 1;      printf ("%d) Restore Y-Wing in Cells %d %d %d remove candidate %d from cell %d\n",        a, W[a], W[a], W[a], b[g[W[a]] & g[W[a]]], W[a]);      g[W[a]] = k;      return 0;    }    if (B[g[W[a]] | g[W[a]] | g[W[a]]] == 3 &&      !(g[W[a]] & g[W[a]] & g[W[a]]) &&      (g[W[a]] & g[W[a]] & g[W[a]]))    {      int k = g[W[a]];      g[W[a]] &= ~(g[W[a]] & g[W[a]]);      printf ("%d) Found Y-Wing in Cells %d %d %d remove candidate %d from cell %d\n",        a, W[a], W[a], W[a], b[g[W[a]] & g[W[a]]], W[a]);      if (solve(p))        return 1;      printf ("%d) Restore Y-Wing in Cells %d %d %d remove candidate %d from cell %d\n",        a, W[a], W[a], W[a], b[g[W[a]] & g[W[a]]], W[a]);      g[W[a]] = k;      return 0;    }    if (B[g[W[a]] | g[W[a]] | g[W[a]]] == 3 &&      !(g[W[a]] & g[W[a]] & g[W[a]]) &&      (g[W[a]] & g[W[a]] & g[W[a]]))    {      int k = g[W[a]];      g[W[a]] &= ~(g[W[a]] & g[W[a]]);      printf ("%d) Found Y-Wing in Cells %d %d %d remove candidate %d from cell %d\n",        a, W[a], W[a], W[a], b[g[W[a]] & g[W[a]]], W[a]);      if (solve(p))        return 1;      printf ("%d) Restore Y-Wing in Cells %d %d %d remove candidate %d from cell %d\n",        a, W[a], W[a], W[a], b[g[W[a]] & g[W[a]]], W[a]);      g[W[a]] = k;      return 0;    }  }  for (; a < 14; ++a)         // Search Y-Wings Type 2    if (B[g[W[a]] | g[W[a]] | g[W[a]]] == 3 &&      !(g[W[a]] & g[W[a]] & g[W[a]]) && (g[W[a]] & g[W[a]] &      (g[W[a]] | g[W[a]] | g[W[a]] | g[W[a]] | g[W[a]])))    {      int k = {g[W[a]], g[W[a]], g[W[a]], g[W[a]], g[W[a]]};      g[W[a]] &= ~(g[W[a]] & g[W[a]]);      g[W[a]] &= ~(g[W[a]] & g[W[a]]);      g[W[a]] &= ~(g[W[a]] & g[W[a]]);      g[W[a]] &= ~(g[W[a]] & g[W[a]]);      g[W[a]] &= ~(g[W[a]] & g[W[a]]);      printf ("%d) Found Y-Wing in Cells %d %d %d remove candidate %d from cells %d %d %d %d %d\n",        a, W[a], W[a], W[a], b[g[W[a]] & g[W[a]]],        W[a], W[a], W[a], W[a], W[a]);      if (solve(p))        return 1;      printf ("%d) Restore Y-Wing in Cells %d %d %d remove candidate %d from cells %d %d %d %d %d\n",        a, W[a], W[a], W[a], b[g[W[a]] & g[W[a]]],        W[a], W[a], W[a], W[a], W[a]);      g[W[a]] = k;      g[W[a]] = k;      g[W[a]] = k;      g[W[a]] = k;      g[W[a]] = k;      return 0;    }`

Tested against Sudoku puzzles:
Code: Select all
`060350080005000042700020900000001000270006000509070008000100050000030000080000403900040000000600031020000090000700020002935600070002000060000073510009000000080009007000400060070030090203000005047609000000000908130200000705080070020090001000500600000002208000400000520896030080057000060000720090080574012000002000701800000009000000001004060208070320400900018000005000600000540009008037040609080300100000000091700050700801000008469000073000000000396000000000280000684500000902001020007940`

Note: Added another Sudoku puzzle taken from Example 1 & 2.
Added all 4 Exemplars from above link too.

R. Jamil
rjamil

Posts: 676
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: What if Naked pair/triplet found within chute

Hi,

After thorough investigating, come to the conclusion that for XY-Wing, (i) a Hinge (Pivot) and two pincers (wings) cells contain exactly 3 candidates; and (ii) each cell contain exactly 2 different candidates from other cells.

There are two types of cell coordinates:

First type of XY-Wing contains exactly same four cells as per X-Wing (Fish) format but all cells lying in different four boxes, i.e., shares two rows and two columns but not boxes. One Pincer shares row with Pivot cell and another shares column with Pivot cell. Removes common Pincers' candidate from only one cell. For first (or starting) cell combinations is A1, A4, D1 and D4. There are further four combinations to be check for XY-Wing:
Hinge Pincers Removal
1. A1 A4 D1 D4
2. A4 A1 D4 D1
3. D1 A1 D4 A4
4. D4 A4 D1 A1
Second type of XY-Wing shares two lines (i.e., either rows or columns) and two boxes within one chute (i.e., either band or stack) but not necessary to share both rows and columns like X-Wing. One Pincer shares line and another shares box with Pivot cell. Removes common Pincer's candidate from 1 to 5 cells. For first (or starting) cell combinations is Hinge A1, Pincer A4, Pincer B1 and Removes common Pincer's candidate from A2, A3, B4, B5 and B6.

Trying to enumerate all possible combinations of first type of moves gives 729 that further produce 4 moves each:
Code: Select all
`for (int a = 0; a < 54; a +=9)  for (int b = a; b < a + 6; ++b)  {    if (!g[b])      continue;    for (int c = a + (b < a + 3 ? 3 : 6); b < a + 9; ++b)    {      if (!g[c])        continue;      for (int d = a < 27 ? 27 : 54; d < 81; d +=9)      {        int e = d + c - a;        if (!g[d] || !g[e])          continue;// perform all four permutations of b, c, d and e;      }    }  }`

Similarly, XYZ-Wing has only one type and is same coordinates as XY-Wing type 2 but the Pivot cell contains all three candidates. But removal cells are only 2 instead of 5 that shares all three cells, i.e., a Hinge and 2 Pincers cells.

Am I going in right direction?

R. Jamil

First corrected on 16th-Oct-2016:
Added XY-Wing type 1 code.
Added in XYZ-Wing definition.
rjamil

Posts: 676
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: What if Naked pair/triplet found within chute

Hi all,

JasonLion wrote: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.

I think, my opening post's query about naked pair and triple found within mini-line are Locked pair and Locked triple moves respectively.

R. Jamil
rjamil

Posts: 676
Joined: 15 October 2014
Location: Karachi, Pakistan

Previous