The New Sudoku Players' Forum

[rjamil]

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]][0]] | g[w[r[a]][1]] | g[w[r[a]][2]] |
      g[w[r[a]][3]] | g[w[r[a]][4]] | g[w[r[a]][5]] | g[w[r[a]][6]] | g[w[r[a]][7]]));
                             // 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]][12]] | g[w[r[a]][13]] | g[w[r[a]][14]] |
        g[w[r[a]][15]] | g[w[r[a]][16]] | g[w[r[a]][17]] | g[w[r[a]][18]] | g[w[r[a]][19]]));
      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]][6]] | g[w[r[a]][7]] | g[w[r[a]][8]] |
          g[w[r[a]][9]] | g[w[r[a]][10]] | g[w[r[a]][11]] | g[w[r[a]][12]] | g[w[r[a]][13]]));
        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]][0]] | g[w[r[a]][1]] | g[w[r[a]][2]] |
      g[w[r[a]][3]] | g[w[r[a]][4]] | g[w[r[a]][5]] | g[w[r[a]][6]] | g[w[r[a]][7]]))) |
      (g[r[a]] & (g[r[a]] ^ (g[w[r[a]][6]] | g[w[r[a]][7]] | g[w[r[a]][8]] | g[w[r[a]][9]] |
      g[w[r[a]][10]] | g[w[r[a]][11]] | g[w[r[a]][12]] | g[w[r[a]][13]]))) |
      (g[r[a]] & (g[r[a]] ^ (g[w[r[a]][12]] | g[w[r[a]][13]] | g[w[r[a]][14]] |
      g[w[r[a]][15]] | g[w[r[a]][16]] | g[w[r[a]][17]] | g[w[r[a]][18]] | g[w[r[a]][19]])));
                             // 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

[StrmCkr]

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);
var
xn,yn,n,n2,z:integer;
begin

For 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);
var
xn,yn,n,n2,z:integer;
begin

For 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 cell
RC[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}

[rjamil]

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 pair
End For sector

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

Added:
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 triple
End 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 quad
End For sector

R. Jamil

[StrmCkr]

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

[rjamil]

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]

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 08
09 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33 34 35
36 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53
54 55 56 57 58 59 60 61 62
63 64 65 66 67 68 69 70 71
72 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][4];)
yw1[0] = {0,3,9,12}; Is this the first combination? or {0,3,27,30}, i.e., all four cells lying in different boxes?
yw1[1] = {0,4,9,13};
...
yw1[5] = {0,8,9,17};
yw1[6] = {0,3,18,21};
...
...
yw1[n] = {68,71,77,80};

For second type of Y-Wing, int yw2[m][8];
yw2[0] = {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]

Hi,

I have coded prototype for Y-Wings and sharing here for programmers' reviews/comments:

Code: Select all

// Global variables declaration
int B[513]; // contains count bitwise candidates
     W[99][8] = {
  {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][0]] | g[W[a][1]] | g[W[a][2]]] == 3 &&
      !(g[W[a][0]] & g[W[a][1]] & g[W[a][2]]) &&
      (g[W[a][1]] & g[W[a][2]] & g[W[a][3]]))
    {
      int k = g[W[a][3]];
      g[W[a][3]] &= ~(g[W[a][1]] & g[W[a][2]]);
      printf ("%d) Found Y-Wing in Cells %d %d %d remove candidate %d from cell %d\n",
        a, W[a][0], W[a][1], W[a][2], b[g[W[a][1]] & g[W[a][2]]], W[a][3]);
      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][0], W[a][1], W[a][2], b[g[W[a][1]] & g[W[a][2]]], W[a][3]);
      g[W[a][3]] = k;
      return 0;
    }
    if (B[g[W[a][0]] | g[W[a][1]] | g[W[a][3]]] == 3 &&
      !(g[W[a][0]] & g[W[a][1]] & g[W[a][3]]) &&
      (g[W[a][0]] & g[W[a][2]] & g[W[a][3]]))
    {
      int k = g[W[a][2]];
      g[W[a][2]] &= ~(g[W[a][0]] & g[W[a][3]]);
      printf ("%d) Found Y-Wing in Cells %d %d %d remove candidate %d from cell %d\n",
        a, W[a][0], W[a][1], W[a][3], b[g[W[a][0]] & g[W[a][3]]], W[a][2]);
      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][0], W[a][1], W[a][3], b[g[W[a][0]] & g[W[a][3]]], W[a][2]);
      g[W[a][2]] = k;
      return 0;
    }
    if (B[g[W[a][0]] | g[W[a][2]] | g[W[a][3]]] == 3 &&
      !(g[W[a][0]] & g[W[a][2]] & g[W[a][3]]) &&
      (g[W[a][0]] & g[W[a][1]] & g[W[a][3]]))
    {
      int k = g[W[a][1]];
      g[W[a][1]] &= ~(g[W[a][0]] & g[W[a][3]]);
      printf ("%d) Found Y-Wing in Cells %d %d %d remove candidate %d from cell %d\n",
        a, W[a][0], W[a][2], W[a][3], b[g[W[a][0]] & g[W[a][3]]], W[a][1]);
      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][0], W[a][2], W[a][3], b[g[W[a][0]] & g[W[a][3]]], W[a][1]);
      g[W[a][1]] = k;
      return 0;
    }
    if (B[g[W[a][1]] | g[W[a][2]] | g[W[a][3]]] == 3 &&
      !(g[W[a][1]] & g[W[a][2]] & g[W[a][3]]) &&
      (g[W[a][0]] & g[W[a][1]] & g[W[a][2]]))
    {
      int k = g[W[a][0]];
      g[W[a][0]] &= ~(g[W[a][1]] & g[W[a][2]]);
      printf ("%d) Found Y-Wing in Cells %d %d %d remove candidate %d from cell %d\n",
        a, W[a][1], W[a][2], W[a][3], b[g[W[a][1]] & g[W[a][2]]], W[a][0]);
      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][1], W[a][2], W[a][3], b[g[W[a][1]] & g[W[a][2]]], W[a][0]);
      g[W[a][0]] = k;
      return 0;
    }
  }
  for (; a < 14; ++a)         // Search Y-Wings Type 2
    if (B[g[W[a][0]] | g[W[a][1]] | g[W[a][2]]] == 3 &&
      !(g[W[a][0]] & g[W[a][1]] & g[W[a][2]]) && (g[W[a][1]] & g[W[a][2]] &
      (g[W[a][3]] | g[W[a][4]] | g[W[a][5]] | g[W[a][6]] | g[W[a][7]])))
    {
      int k[5] = {g[W[a][3]], g[W[a][4]], g[W[a][5]], g[W[a][6]], g[W[a][7]]};
      g[W[a][3]] &= ~(g[W[a][1]] & g[W[a][2]]);
      g[W[a][4]] &= ~(g[W[a][1]] & g[W[a][2]]);
      g[W[a][5]] &= ~(g[W[a][1]] & g[W[a][2]]);
      g[W[a][6]] &= ~(g[W[a][1]] & g[W[a][2]]);
      g[W[a][7]] &= ~(g[W[a][1]] & g[W[a][2]]);
      printf ("%d) Found Y-Wing in Cells %d %d %d remove candidate %d from cells %d %d %d %d %d\n",
        a, W[a][0], W[a][1], W[a][2], b[g[W[a][1]] & g[W[a][2]]],
        W[a][3], W[a][4], W[a][5], W[a][6], W[a][7]);
      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][0], W[a][1], W[a][2], b[g[W[a][1]] & g[W[a][2]]],
        W[a][3], W[a][4], W[a][5], W[a][6], W[a][7]);
      g[W[a][3]] = k[0];
      g[W[a][4]] = k[1];
      g[W[a][5]] = k[2];
      g[W[a][6]] = k[3];
      g[W[a][7]] = k[4];
      return 0;
    }

Tested against Sudoku puzzles:

Code: Select all

060350080005000042700020900000001000270006000509070008000100050000030000080000403
900040000000600031020000090000700020002935600070002000060000073510009000000080009
007000400060070030090203000005047609000000000908130200000705080070020090001000500
600000002208000400000520896030080057000060000720090080574012000002000701800000009
000000001004060208070320400900018000005000600000540009008037040609080300100000000
091700050700801000008469000073000000000396000000000280000684500000902001020007940

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

R. Jamil

[rjamil]

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]

Hi all,

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