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: 665
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)
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: 665
Joined: 15 October 2014
Location: Karachi, Pakistan