## Pseudo code for X-Wing, Swordfish and Jellyfish

Programs which generate, solve, and analyze Sudoku puzzles

### Pseudo code for X-Wing, Swordfish and Jellyfish

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]] >> A) & 1 | ((g[l[Y]] >> A) & 1) << 1 |        ((g[l[Y]] >> A) & 1) << 2 | ((g[l[Y]] >> A) & 1) << 3 |        ((g[l[Y]] >> A) & 1) << 4 | ((g[l[Y]] >> A) & 1) << 5 |        ((g[l[Y]] >> A) & 1) << 6 | ((g[l[Y]] >> A) & 1) << 7 |        ((g[l[Y]] >> 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]] >> A) & 1 | ((g[l[y]] >> A) & 1) << 1 |          ((g[l[y]] >> A) & 1) << 2 | ((g[l[y]] >> A) & 1) << 3 |          ((g[l[y]] >> A) & 1) << 4 | ((g[l[y]] >> A) & 1) << 5 |          ((g[l[y]] >> A) & 1) << 6 | ((g[l[y]] >> A) & 1) << 7 |          ((g[l[y]] >> 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]] >> A) & 1 | ((g[l[X]] >> A) & 1) << 1 |            ((g[l[X]] >> A) & 1) << 2 | ((g[l[X]] >> A) & 1) << 3 |            ((g[l[X]] >> A) & 1) << 4 | ((g[l[X]] >> A) & 1) << 5 |            ((g[l[X]] >> A) & 1) << 6 | ((g[l[X]] >> A) & 1) << 7 |            ((g[l[X]] >> 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

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

### Re: Pseudo code for X-Wing, Swordfish and Jellyfish

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;              // Backup Basic Fish Candidate Line wise      for (y = Y; y < Y + 9; ++y)        k[y - Y] = (g[l[y]] >> a) & 1 | ((g[l[y]] >> a) & 1) << 1 |          ((g[l[y]] >> a) & 1) << 2 | ((g[l[y]] >> a) & 1) << 3 |          ((g[l[y]] >> a) & 1) << 4 | ((g[l[y]] >> a) & 1) << 5 |          ((g[l[y]] >> a) & 1) << 6 | ((g[l[y]] >> a) & 1) << 7 |          ((g[l[y]] >> a) & 1) << 8;      for (y = 0; y < 36; ++y)      {                      // Search X-Wing Candidate in Line 36 pair Cell positions        int A = k[T[y]],            K,            X = -1;        if (B[A] != 2 || A != k[T[y]])        {                    // Skip for X-Wing Candidate not found in Lines pair Cell positions          if (B[A] != 2)            y += 7 - T[y];          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]] >> K[Z]) & 1 | (k[T[y]] >> K[Z]) & 1 |            (k[T[y]] >> K[Z]) & 1 | (k[T[y]] >> K[Z]) & 1 |            (k[T[y]] >> K[Z]) & 1 | (k[T[y]] >> K[Z]) & 1 |            (k[T[y]] >> 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]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(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 : T[y]) + 1, (Y ? K : T[y]) + 1,          (Y ? T[y] : K) + 1, (Y ? T[y] : K) + 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 : T[y]) + 1, (Y ? K : T[y]) + 1,          (Y ? T[y] : K) + 1, (Y ? T[y] : K) + 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]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;        }      }      for (; y < 120; ++y)   // Search Swordfish Candidate in Line 84 triplet Cell positions      {        int A = k[T[y]] | k[T[y]] | k[T[y]],            K,            X = -1;        if (!k[T[y]] || !k[T[y]] || !k[T[y]] || B[A] != 3)        {                    // Skip for Sordfish Candidate not found in Lines triplet Cell positions          if (!k[T[y]] || B[k[T[y]]] > 3)          {            int A = {27,20,14, 9, 5, 2, 0};            y += A[T[y]];          }          else            if (!k[T[y]] || B[k[T[y]]] > 3)              y += 7 - T[y];          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]] >> K[Z]) & 1 | (k[T[y]] >> K[Z]) & 1 |            (k[T[y]] >> K[Z]) & 1 | (k[T[y]] >> K[Z]) & 1 |            (k[T[y]] >> K[Z]) & 1 | (k[T[y]] >> 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]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(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] + 1, T[y] + 1, T[y] + 1, K + 1, K + 1, K + 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] + 1, T[y] + 1, T[y] + 1, K + 1, K + 1, K + 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]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;        }      }      for (; y < 246; ++y)   // Search Jellyfish Candidate in Line 126 quad Cell positions      {        int A = k[T[y]] | k[T[y]] | k[T[y]] | k[T[y]],            K,            X = -1;        if (!k[T[y]] || !k[T[y]] || !k[T[y]] || !k[T[y]] || B[A] != 4)        {                    // Skip for Jellyfish Candidate not found in Line quad Cell positions          if (!k[T[y]] || B[k[T[y]]] > 4)          {            int A = {55,34,19, 9, 3, 0};            y += A[T[y]];          }          else            if (!k[T[y]] || B[k[T[y]]] > 4)            {              int A = {27,20,14, 9, 5, 2, 0};              y += A[T[y]];            }            else              if (!k[T[y]] || B[k[T[y]]] > 4)                y += 7 - T[y];          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]] >> K[Z]) & 1 | (k[T[y]] >> K[Z]) & 1 |            (k[T[y]] >> K[Z]) & 1 | (k[T[y]] >> K[Z]) & 1 |            (k[T[y]] >> 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]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(1 << a);          g[l[X][T[y]]] &= ~(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] + 1, T[y] + 1, T[y] + 1, T[y] + 1,          K + 1, K + 1, K + 1, K + 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] + 1, T[y] + 1, T[y] + 1, T[y] + 1,          K + 1, K + 1, K + 1, K + 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]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> X) & 1) << a;          g[l[X][T[y]]] |= ((k[T[y]] >> 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
rjamil

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