The New Sudoku Players' Forum

[rjamil]

Hi,

While I am studying X-Wing, Swordfish and Jellyfish elimination methods in order to implement in to my Bitwise Sudoku Solver program, got an idea. Here is proposed pseudo code for expert review and comments/suggestions please:

Code: Select all

  for (int A = 0; A < 9; ++A)// Check X-Wing for each candidate
    for (int Y = 0; Y < 8; ++Y)
    {                        // Check X-Wing for first Row Unit
      int K = (g[l[Y][0]] >> A) & 1 | ((g[l[Y][1]] >> A) & 1) << 1 |
        ((g[l[Y][2]] >> A) & 1) << 2 | ((g[l[Y][3]] >> A) & 1) << 3 |
        ((g[l[Y][4]] >> A) & 1) << 4 | ((g[l[Y][5]] >> A) & 1) << 5 |
        ((g[l[Y][6]] >> A) & 1) << 6 | ((g[l[Y][7]] >> A) & 1) << 7 |
        ((g[l[Y][8]] >> A) & 1) << 8

      if (B[K] != 2)
        continue;            // Skip first Row Unit for candidate found more than 2 unsolved Cell positions
      for (y = Y + 1; Y < 9; ++Y)
      {                      // Check X-Wing for second Row Unit
        if (K != (g[l[y][0]] >> A) & 1 | ((g[l[y][1]] >> A) & 1) << 1 |
          ((g[l[y][2]] >> A) & 1) << 2 | ((g[l[y][3]] >> A) & 1) << 3 |
          ((g[l[y][4]] >> A) & 1) << 4 | ((g[l[y][5]] >> A) & 1) << 5 |
          ((g[l[y][6]] >> A) & 1) << 6 | ((g[l[y][7]] >> A) & 1) << 7 |
          ((g[l[y][8]] >> A) & 1) << 8)
          continue;          // Skip second Row Unit if not equals to first Row Unit
        for (int X = K; a = b[X & -X] + 9; X &= X - 1)
                             // Check each Column Unit
          if (B[(g[l[X][0]] >> A) & 1 | ((g[l[X][1]] >> A) & 1) << 1 |
            ((g[l[X][2]] >> A) & 1) << 2 | ((g[l[X][3]] >> A) & 1) << 3 |
            ((g[l[X][4]] >> A) & 1) << 4 | ((g[l[X][5]] >> A) & 1) << 5 |
            ((g[l[X][6]] >> A) & 1) << 6 | ((g[l[X][7]] >> A) & 1) << 7 |
            ((g[l[X][8]] >> A) & 1) << 8] > 2)
          {                  // Found X-Wing
// do backup, eliminations then recursive call solve function then restore
          }
      }
    }

Similarly, for swordfish and Jellyfish, loop third row unit and forth row unit respectively and check union of first, second, third [and forth] row unit for candidate found between 2 and 3/4 unsolved cell positions.

Also, for column, repeat same steps in column loops and then row checking.

Note: there might be some error due unintentional typo mistakes as not yet checked, but hope that overall logic works.

R. Jamil

[rjamil]

Hi,

I have discarded my above mentioned proposed pseudo code for simple fishes (i.e., X-Wing, Swordfish and Jellyfish) and rethinking about coding as per Tuples. I am sharing here complete Simple Fish source code for review that isalmost completed but under testing mode.

Code: Select all

  for (a = 0; a < 9; ++a)    // Search Basic Fishes Candidate wise
    for (int Y = 0; Y < 10; Y += 9)
    {                        // Search Basic Fishes for each Candidate Line wise
      int k[9];              // Backup Basic Fish Candidate Line wise

      for (y = Y; y < Y + 9; ++y)
        k[y - Y] = (g[l[y][0]] >> a) & 1 | ((g[l[y][1]] >> a) & 1) << 1 |
          ((g[l[y][2]] >> a) & 1) << 2 | ((g[l[y][3]] >> a) & 1) << 3 |
          ((g[l[y][4]] >> a) & 1) << 4 | ((g[l[y][5]] >> a) & 1) << 5 |
          ((g[l[y][6]] >> a) & 1) << 6 | ((g[l[y][7]] >> a) & 1) << 7 |
          ((g[l[y][8]] >> a) & 1) << 8;
      for (y = 0; y < 36; ++y)
      {                      // Search X-Wing Candidate in Line 36 pair Cell positions
        int A = k[T[y][0]],
            K[2],
            X = -1;

        if (B[A] != 2 || A != k[T[y][1]])
        {                    // Skip for X-Wing Candidate not found in Lines pair Cell positions
          if (B[A] != 2)
            y += 7 - T[y][0];
          continue;
        }
        for (int L = A, Z = -1; L; L &= L - 1)
        {                    // Remove X-Wing Candidate from opposite Line other unsolved Cell positions
          K[++Z] = b[L & -L] - 1;
          if (!((k[T[y][2]] >> K[Z]) & 1 | (k[T[y][3]] >> K[Z]) & 1 |
            (k[T[y][4]] >> K[Z]) & 1 | (k[T[y][5]] >> K[Z]) & 1 |
            (k[T[y][6]] >> K[Z]) & 1 | (k[T[y][7]] >> K[Z]) & 1 |
            (k[T[y][8]] >> K[Z]) & 1))
            continue;        // Skip opposite Line for X-Wing Candidate not found in opposite Line other unsolved Cell positions
          X = K[Z] - Y + 9;
          g[l[X][T[y][2]]] &= ~(1 << a);
          g[l[X][T[y][3]]] &= ~(1 << a);
          g[l[X][T[y][4]]] &= ~(1 << a);
          g[l[X][T[y][5]]] &= ~(1 << a);
          g[l[X][T[y][6]]] &= ~(1 << a);
          g[l[X][T[y][7]]] &= ~(1 << a);
          g[l[X][T[y][8]]] &= ~(1 << a);
        }
        if (X < 0)
          continue;          // Skip for X-Wing Candidate not found in opposite Lines other unsolved Cell positions
#ifdef RJ
        printf ("%d) Found %s X-Wing for Candidate %d at r%d%dc%d%d\n",
          y, Y ? "Column wise" : "Row wise", a + 1,
          (Y ? K[0] : T[y][0]) + 1, (Y ? K[1] : T[y][1]) + 1,
          (Y ? T[y][0] : K[0]) + 1, (Y ? T[y][1] : K[1]) + 1);
#endif
        if (solve (p))
          return 1;
#ifdef RJ
        printf ("%d) Restore %s X-Wing for Candidate %d at r%d%dc%d%d\n",
          y, Y ? "Column wise" : "Row wise", a + 1,
          (Y ? K[0] : T[y][0]) + 1, (Y ? K[1] : T[y][1]) + 1,
          (Y ? T[y][0] : K[0]) + 1, (Y ? T[y][1] : K[1]) + 1);
#endif
        for (int L = A; L; L &= L - 1)
        {                    // Restore X-Wing Candidate to opposite Lines other unsolved Cell positions
          X = b[L & -L] - Y + 8;
          g[l[X][T[y][2]]] |= ((k[T[y][2]] >> X) & 1) << a;
          g[l[X][T[y][3]]] |= ((k[T[y][3]] >> X) & 1) << a;
          g[l[X][T[y][4]]] |= ((k[T[y][4]] >> X) & 1) << a;
          g[l[X][T[y][5]]] |= ((k[T[y][5]] >> X) & 1) << a;
          g[l[X][T[y][6]]] |= ((k[T[y][6]] >> X) & 1) << a;
          g[l[X][T[y][7]]] |= ((k[T[y][7]] >> X) & 1) << a;
          g[l[X][T[y][8]]] |= ((k[T[y][8]] >> X) & 1) << a;
        }
      }
      for (; y < 120; ++y)   // Search Swordfish Candidate in Line 84 triplet Cell positions
      {
        int A = k[T[y][0]] | k[T[y][1]] | k[T[y][2]],
            K[3],
            X = -1;

        if (!k[T[y][0]] || !k[T[y][1]] || !k[T[y][2]] || B[A] != 3)
        {                    // Skip for Sordfish Candidate not found in Lines triplet Cell positions
          if (!k[T[y][0]] || B[k[T[y][0]]] > 3)
          {
            int A[7] = {27,20,14, 9, 5, 2, 0};

            y += A[T[y][0]];
          }
          else
            if (!k[T[y][1]] || B[k[T[y][1]]] > 3)
              y += 7 - T[y][1];
          continue;
        }
        for (int L = A, Z = -1; L; L &= L - 1)
        {                    // Remove Swordfish Candidate from opposite Line other unsolved Cell positions
          K[++Z] = b[L & -L] - 1;
          if (!((k[T[y][3]] >> K[Z]) & 1 | (k[T[y][4]] >> K[Z]) & 1 |
            (k[T[y][5]] >> K[Z]) & 1 | (k[T[y][6]] >> K[Z]) & 1 |
            (k[T[y][7]] >> K[Z]) & 1 | (k[T[y][8]] >> K[Z]) & 1))
            continue;        // Skip opposite Line for Swordfish Candidate not found in opposite Line other unsolved Cell positions
          X = K[Z] - Y + 9;
          g[l[X][T[y][3]]] &= ~(1 << a);
          g[l[X][T[y][4]]] &= ~(1 << a);
          g[l[X][T[y][5]]] &= ~(1 << a);
          g[l[X][T[y][6]]] &= ~(1 << a);
          g[l[X][T[y][7]]] &= ~(1 << a);
          g[l[X][T[y][8]]] &= ~(1 << a);
        }
        if (X < 0)
          continue;          // Skip for Swordfish Candidate not found in opposite Lines other unsolved Cell positions
#ifdef RJ
        printf ("%d) Found %s Swordfish for Candidate %d at r%d%d%dc%d%d%d\n",
          y, Y ? "Column wise" : "Row wise", a + 1,
          T[y][0] + 1, T[y][1] + 1, T[y][2] + 1, K[0] + 1, K[1] + 1, K[2] + 1);
#endif
        if (solve (p))
          return 1;
#ifdef RJ
        printf ("%d) Restore %s Swordfish for Candidate %d at r%d%d%dc%d%d%d\n",
          y, Y ? "Column wise" : "Row wise", a + 1,
          T[y][0] + 1, T[y][1] + 1, T[y][2] + 1, K[0] + 1, K[1] + 1, K[2] + 1);
#endif
        for (int L = A; L; L &= L - 1)
        {                    // Restore Swordfish Candidate to opposite Lines other unsolved Cell positions
          X = b[L & -L] - Y + 8;
          g[l[X][T[y][3]]] |= ((k[T[y][3]] >> X) & 1) << a;
          g[l[X][T[y][4]]] |= ((k[T[y][4]] >> X) & 1) << a;
          g[l[X][T[y][5]]] |= ((k[T[y][5]] >> X) & 1) << a;
          g[l[X][T[y][6]]] |= ((k[T[y][6]] >> X) & 1) << a;
          g[l[X][T[y][7]]] |= ((k[T[y][7]] >> X) & 1) << a;
          g[l[X][T[y][8]]] |= ((k[T[y][8]] >> X) & 1) << a;
        }
      }
      for (; y < 246; ++y)   // Search Jellyfish Candidate in Line 126 quad Cell positions
      {
        int A = k[T[y][0]] | k[T[y][1]] | k[T[y][2]] | k[T[y][3]],
            K[4],
            X = -1;

        if (!k[T[y][0]] || !k[T[y][1]] || !k[T[y][2]] || !k[T[y][3]] || B[A] != 4)
        {                    // Skip for Jellyfish Candidate not found in Line quad Cell positions
          if (!k[T[y][0]] || B[k[T[y][0]]] > 4)
          {
            int A[6] = {55,34,19, 9, 3, 0};

            y += A[T[y][0]];
          }
          else
            if (!k[T[y][1]] || B[k[T[y][1]]] > 4)
            {
              int A[7] = {27,20,14, 9, 5, 2, 0};

              y += A[T[y][1]];
            }
            else
              if (!k[T[y][2]] || B[k[T[y][2]]] > 4)
                y += 7 - T[y][2];
          continue;
        }
        for (int L = A, Z = -1; L; L &= L - 1)
        {                    // Remove Jellyfish Candidate from opposite Line other unsolved Cell positions
          K[++Z] = b[L & -L] - 1;
          if (!((k[T[y][4]] >> K[Z]) & 1 | (k[T[y][5]] >> K[Z]) & 1 |
            (k[T[y][6]] >> K[Z]) & 1 | (k[T[y][7]] >> K[Z]) & 1 |
            (k[T[y][8]] >> K[Z]) & 1))
            continue;        // Skip for Jellyfish Candidate not found in opposite Line other unsolved Cell positions
          X = K[Z] - Y + 9;
          g[l[X][T[y][4]]] &= ~(1 << a);
          g[l[X][T[y][5]]] &= ~(1 << a);
          g[l[X][T[y][6]]] &= ~(1 << a);
          g[l[X][T[y][7]]] &= ~(1 << a);
          g[l[X][T[y][8]]] &= ~(1 << a);
        }
        if (X < 0)
          continue;          // Skip for Jellyfish Candidate not found in opposite Lines other unsolved Cell positions
#ifdef RJ
        printf ("%d) Found %s Jellyfish for Candidate %d at r%d%d%d%dc%d%d%d%d\n",
          y, Y ? "Column wise" : "Row wise", a + 1,
          T[y][0] + 1, T[y][1] + 1, T[y][2] + 1, T[y][3] + 1,
          K[0] + 1, K[1] + 1, K[2] + 1, K[3] + 1);
#endif
        if (solve (p))
          return 1;
#ifdef RJ
        printf ("%d) Restore %s Jellyfish for Candidate %d at r%d%d%d%dc%d%d%d%d\n",
          y, Y ? "Column wise" : "Row wise", a + 1,
          T[y][0] + 1, T[y][1] + 1, T[y][2] + 1, T[y][3] + 1,
          K[0] + 1, K[1] + 1, K[2] + 1, K[3] + 1);
#endif
        for (int L = A; L; L &= L - 1)
        {                    // Restore Jellyfish Candidate to opposite Lines other unsolved Cell positions
          X = b[L & -L] - Y + 8;
          g[l[X][T[y][4]]] |= ((k[T[y][4]] >> X) & 1) << a;
          g[l[X][T[y][5]]] |= ((k[T[y][5]] >> X) & 1) << a;
          g[l[X][T[y][6]]] |= ((k[T[y][6]] >> X) & 1) << a;
          g[l[X][T[y][7]]] |= ((k[T[y][7]] >> X) & 1) << a;
          g[l[X][T[y][8]]] |= ((k[T[y][8]] >> X) & 1) << a;
        }
      }
    }

Updated 20151113: If above code tested ok then I have another better plan idea to speed-up the code by replacing 9 digit-wise searching to only 3, i.e., searching pair, triplet and quad containing line combinations.

Updated:20151115: In 3 places, replace variable 'a' with 'y'.
Now code perfectly search basic fishes too.

R. Jamil