The New Sudoku Players' Forum

[rjamil]

Hi all,

I missed setbb forum.

I have installed Windows based C-Free 5 Pro IDE, which uses MinGW5 as default compiler.

I have tried to write Boolean Sudoku solver program in C++. implemented Naked, Hidden Single and Box-Row/Column intersections.

Here is my source code, which is well commented:

Code: Select all

#include <stdio.h>
#include <time.h>

char q,                      // Number of empty Cell positions
     r[81],                  // Used for sorting and eliminating empty Cell positions
     s[81];                  // Sudoku empty 81 Cell positions Board wise

static int bd[512] = {       // Boolean to Digit
          0,        1,        2,       21,        3,       31,       32,      321,
          4,       41,       42,      421,       43,      431,      432,     4321,
          5,       51,       52,      521,       53,      531,      532,     5321,
         54,      541,      542,     5421,      543,     5431,     5432,    54321,
          6,       61,       62,      621,       63,      631,      632,     6321,
         64,      641,      642,     6421,      643,     6431,     6432,    64321,
         65,      651,      652,     6521,      653,     6531,     6532,    65321,
        654,     6541,     6542,    65421,     6543,    65431,    65432,   654321,
          7,       71,       72,      721,       73,      731,      732,     7321,
         74,      741,      742,     7421,      743,     7431,     7432,    74321,
         75,      751,      752,     7521,      753,     7531,     7532,    75321,
        754,     7541,     7542,    75421,     7543,    75431,    75432,   754321,
         76,      761,      762,     7621,      763,     7631,     7632,    76321,
        764,     7641,     7642,    76421,     7643,    76431,    76432,   764321,
        765,     7651,     7652,    76521,     7653,    76531,    76532,   765321,
       7654,    76541,    76542,   765421,    76543,   765431,   765432,  7654321,
          8,       81,       82,      821,       83,      831,      832,     8321,
         84,      841,      842,     8421,      843,     8431,     8432,    84321,
         85,      851,      852,     8521,      853,     8531,     8532,    85321,
        854,     8541,     8542,     5421,     8543,    85431,    85432,   854321,
         86,      861,      862,     8621,      863,     8631,     8632,    86321,
        864,     8641,     8642,    86421,     8643,    86431,    86432,   864321,
        865,     8651,     8652,    86521,     8653,    86531,    86532,   865321,
       8654,    86541,    86542,   865421,    86543,   865431,   865432,  8654321,
         87,      871,      872,     8721,      873,     8731,     8732,    87321,
        874,     8741,     8742,    87421,     8743,    87431,    87432,   874321,
        875,     8751,     8752,    87521,     8753,    87531,    87532,   875321,
       8754,    87541,    87542,   875421,    87543,   875431,   875432,  8754321,
        876,     8761,     8762,    87621,     8763,    87631,    87632,   876321,
       8764,    87641,    87642,   876421,    87643,   876431,   876432,  8764321,
       8765,    87651,    87652,   876521,    87653,   876531,   876532,  8765321,
      87654,   876541,   876542,  8765421,   876543,  8765431,  8765432, 87654321,
          9,       91,       92,      921,       93,      931,      932,     9321,
         94,      941,      942,     9421,      943,     9431,     9432,    94321,
         95,      951,      952,     9521,      953,     9531,     9532,    95321,
        954,     9541,     9542,    95421,     9543,    95431,    95432,   954321,
         96,      961,      962,     9621,      963,     9631,     9632,    96321,
        964,     9641,     9642,    96421,     9643,    96431,    96432,   964321,
        965,     9651,     9652,    96521,     9653,    96531,    96532,   965321,
       9654,    96541,    96542,   965421,    96543,   965431,   965432,  9654321,
         97,      971,      972,     9721,      973,     9731,     9732,    97321,
        974,     9741,     9742,    97421,     9743,    97431,    97432,   974321,
        975,     9751,     9752,    97521,     9753,    97531,    97532,   975321,
       9754,    97541,    97542,   975421,    97543,   975431,   975432,  9754321,
        976,     9761,     9762,    97621,     9763,    97631,    97632,   976321,
       9764,    97641,    97642,   976421,    97643,   976431,   976432,  9764321,
       9765,    97651,    97652,   976521,    97653,   976531,   976532,  9765321,
      97654,   976541,   976542,  9765421,   976543,  9765431,  9765432, 97654321,
         98,      981,      982,     9821,      983,     9831,     9832,    98321,
        984,     9841,     9842,    98421,     9843,    98431,    98432,   984321,
        985,     9851,     9852,    98521,     9853,    98531,    98532,   985321,
       9854,    98541,    98542,    95421,    98543,   985431,   985432,  9854321,
        986,     9861,     9862,    98621,     9863,    98631,    98632,   986321,
       9864,    98641,    98642,   986421,    98643,   986431,   986432,  9864321,
       9865,    98651,    98652,   986521,    98653,   986531,   986532,  9865321,
      98654,   986541,   986542,  9865421,   986543,  9865431,  9865432, 98654321,
        987,     9871,     9872,    98721,     9873,    98731,    98732,   987321,
       9874,    98741,    98742,   987421,    98743,   987431,   987432,  9874321,
       9875,    98751,    98752,   987521,    98753,   987531,   987532,  9875321,
      98754,   987541,   987542,  9875421,   987543,  9875431,  9875432, 98754321,
       9876,    98761,    98762,   987621,    98763,   987631,   987632,  9876321,
      98764,   987641,   987642,  9876421,   987643,  9876431,  9876432, 98764321,
      98765,   987651,   987652,  9876521,   987653,  9876531,  9876532, 98765321,
     987654,  9876541,  9876542, 98765421,  9876543, 98765431, 98765432,987654321};

static char w[81][20] = {    // Affected empty 20 Cell positions
  { 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20,27,36,45,54,63,72},
  { 0, 2, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20,28,37,46,55,64,73},
  { 0, 1, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20,29,38,47,56,65,74},
  { 0, 1, 2, 4, 5, 6, 7, 8,12,13,14,21,22,23,30,39,48,57,66,75},
  { 0, 1, 2, 3, 5, 6, 7, 8,12,13,14,21,22,23,31,40,49,58,67,76},
  { 0, 1, 2, 3, 4, 6, 7, 8,12,13,14,21,22,23,32,41,50,59,68,77},
  { 0, 1, 2, 3, 4, 5, 7, 8,15,16,17,24,25,26,33,42,51,60,69,78},
  { 0, 1, 2, 3, 4, 5, 6, 8,15,16,17,24,25,26,34,43,52,61,70,79},
  { 0, 1, 2, 3, 4, 5, 6, 7,15,16,17,24,25,26,35,44,53,62,71,80},
  { 0, 1, 2,10,11,12,13,14,15,16,17,18,19,20,27,36,45,54,63,72},
  { 0, 1, 2, 9,11,12,13,14,15,16,17,18,19,20,28,37,46,55,64,73},
  { 0, 1, 2, 9,10,12,13,14,15,16,17,18,19,20,29,38,47,56,65,74},
  { 3, 4, 5, 9,10,11,13,14,15,16,17,21,22,23,30,39,48,57,66,75},
  { 3, 4, 5, 9,10,11,12,14,15,16,17,21,22,23,31,40,49,58,67,76},
  { 3, 4, 5, 9,10,11,12,13,15,16,17,21,22,23,32,41,50,59,68,77},
  { 6, 7, 8, 9,10,11,12,13,14,16,17,24,25,26,33,42,51,60,69,78},
  { 6, 7, 8, 9,10,11,12,13,14,15,17,24,25,26,34,43,52,61,70,79},
  { 6, 7, 8, 9,10,11,12,13,14,15,16,24,25,26,35,44,53,62,71,80},
  { 0, 1, 2, 9,10,11,19,20,21,22,23,24,25,26,27,36,45,54,63,72},
  { 0, 1, 2, 9,10,11,18,20,21,22,23,24,25,26,28,37,46,55,64,73},
  { 0, 1, 2, 9,10,11,18,19,21,22,23,24,25,26,29,38,47,56,65,74},
  { 3, 4, 5,12,13,14,18,19,20,22,23,24,25,26,30,39,48,57,66,75},
  { 3, 4, 5,12,13,14,18,19,20,21,23,24,25,26,31,40,49,58,67,76},
  { 3, 4, 5,12,13,14,18,19,20,21,22,24,25,26,32,41,50,59,68,77},
  { 6, 7, 8,15,16,17,18,19,20,21,22,23,25,26,33,42,51,60,69,78},
  { 6, 7, 8,15,16,17,18,19,20,21,22,23,24,26,34,43,52,61,70,79},
  { 6, 7, 8,15,16,17,18,19,20,21,22,23,24,25,35,44,53,62,71,80},
  { 0, 9,18,28,29,30,31,32,33,34,35,36,37,38,45,46,47,54,63,72},
  { 1,10,19,27,29,30,31,32,33,34,35,36,37,38,45,46,47,55,64,73},
  { 2,11,20,27,28,30,31,32,33,34,35,36,37,38,45,46,47,56,65,74},
  { 3,12,21,27,28,29,31,32,33,34,35,39,40,41,48,49,50,57,66,75},
  { 4,13,22,27,28,29,30,32,33,34,35,39,40,41,48,49,50,58,67,76},
  { 5,14,23,27,28,29,30,31,33,34,35,39,40,41,48,49,50,59,68,77},
  { 6,15,24,27,28,29,30,31,32,34,35,42,43,44,51,52,53,60,69,78},
  { 7,16,25,27,28,29,30,31,32,33,35,42,43,44,51,52,53,61,70,79},
  { 8,17,26,27,28,29,30,31,32,33,34,42,43,44,51,52,53,62,71,80},
  { 0, 9,18,27,28,29,37,38,39,40,41,42,43,44,45,46,47,54,63,72},
  { 1,10,19,27,28,29,36,38,39,40,41,42,43,44,45,46,47,55,64,73},
  { 2,11,20,27,28,29,36,37,39,40,41,42,43,44,45,46,47,56,65,74},
  { 3,12,21,30,31,32,36,37,38,40,41,42,43,44,48,49,50,57,66,75},
  { 4,13,22,30,31,32,36,37,38,39,41,42,43,44,48,49,50,58,67,76},
  { 5,14,23,30,31,32,36,37,38,39,40,42,43,44,48,49,50,59,68,77},
  { 6,15,24,33,34,35,36,37,38,39,40,41,43,44,51,52,53,60,69,78},
  { 7,16,25,33,34,35,36,37,38,39,40,41,42,44,51,52,53,61,70,79},
  { 8,17,26,33,34,35,36,37,38,39,40,41,42,43,51,52,53,62,71,80},
  { 0, 9,18,27,28,29,36,37,38,46,47,48,49,50,51,52,53,54,63,72},
  { 1,10,19,27,28,29,36,37,38,45,47,48,49,50,51,52,53,55,64,73},
  { 2,11,20,27,28,29,36,37,38,45,46,48,49,50,51,52,53,56,65,74},
  { 3,12,21,30,31,32,39,40,41,45,46,47,49,50,51,52,53,57,66,75},
  { 4,13,22,30,31,32,39,40,41,45,46,47,48,50,51,52,53,58,67,76},
  { 5,14,23,30,31,32,39,40,41,45,46,47,48,49,51,52,53,59,68,77},
  { 6,15,24,33,34,35,42,43,44,45,46,47,48,49,50,52,53,60,69,78},
  { 7,16,25,33,34,35,42,43,44,45,46,47,48,49,50,51,53,61,70,79},
  { 8,17,26,33,34,35,42,43,44,45,46,47,48,49,50,51,52,62,71,80},
  { 0, 9,18,27,36,45,55,56,57,58,59,60,61,62,63,64,65,72,73,74},
  { 1,10,19,28,37,46,54,56,57,58,59,60,61,62,63,64,65,72,73,74},
  { 2,11,20,29,38,47,54,55,57,58,59,60,61,62,63,64,65,72,73,74},
  { 3,12,21,30,39,48,54,55,56,58,59,60,61,62,66,67,68,75,76,77},
  { 4,13,22,31,40,49,54,55,56,57,59,60,61,62,66,67,68,75,76,77},
  { 5,14,23,32,41,50,54,55,56,57,58,60,61,62,66,67,68,75,76,77},
  { 6,15,24,33,42,51,54,55,56,57,58,59,61,62,69,70,71,78,79,80},
  { 7,16,25,34,43,52,54,55,56,57,58,59,60,62,69,70,71,78,79,80},
  { 8,17,26,35,44,53,54,55,56,57,58,59,60,61,69,70,71,78,79,80},
  { 0, 9,18,27,36,45,54,55,56,64,65,66,67,68,69,70,71,72,73,74},
  { 1,10,19,28,37,46,54,55,56,63,65,66,67,68,69,70,71,72,73,74},
  { 2,11,20,29,38,47,54,55,56,63,64,66,67,68,69,70,71,72,73,74},
  { 3,12,21,30,39,48,57,58,59,63,64,65,67,68,69,70,71,75,76,77},
  { 4,13,22,31,40,49,57,58,59,63,64,65,66,68,69,70,71,75,76,77},
  { 5,14,23,32,41,50,57,58,59,63,64,65,66,67,69,70,71,75,76,77},
  { 6,15,24,33,42,51,60,61,62,63,64,65,66,67,68,70,71,78,79,80},
  { 7,16,25,34,43,52,60,61,62,63,64,65,66,67,68,69,71,78,79,80},
  { 8,17,26,35,44,53,60,61,62,63,64,65,66,67,68,69,70,78,79,80},
  { 0, 9,18,27,36,45,54,55,56,63,64,65,73,74,75,76,77,78,79,80},
  { 1,10,19,28,37,46,54,55,56,63,64,65,72,74,75,76,77,78,79,80},
  { 2,11,20,29,38,47,54,55,56,63,64,65,72,73,75,76,77,78,79,80},
  { 3,12,21,30,39,48,57,58,59,66,67,68,72,73,74,76,77,78,79,80},
  { 4,13,22,31,40,49,57,58,59,66,67,68,72,73,74,75,77,78,79,80},
  { 5,14,23,32,41,50,57,58,59,66,67,68,72,73,74,75,76,78,79,80},
  { 6,15,24,33,42,51,60,61,62,69,70,71,72,73,74,75,76,77,79,80},
  { 7,16,25,34,43,52,60,61,62,69,70,71,72,73,74,75,76,77,78,80},
  { 8,17,26,35,44,53,60,61,62,69,70,71,72,73,74,75,76,77,78,79}},
            l[27][9] = {     // Empty 9 Cell positions for Hidden Singles Row, Column and Box wise
  { 0, 1, 2, 3, 4, 5, 6, 7, 8}, { 9,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}, { 0, 9,18,27,36,45,54,63,72},
  { 1,10,19,28,37,46,55,64,73}, { 2,11,20,29,38,47,56,65,74},
  { 3,12,21,30,39,48,57,66,75}, { 4,13,22,31,40,49,58,67,76},
  { 5,14,23,32,41,50,59,68,77}, { 6,15,24,33,42,51,60,69,78},
  { 7,16,25,34,43,52,61,70,79}, { 8,17,26,35,44,53,62,71,80},
  { 0, 1, 2, 9,10,11,18,19,20}, { 3, 4, 5,12,13,14,21,22,23},
  { 6, 7, 8,15,16,17,24,25,26}, {27,28,29,36,37,38,45,46,47},
  {30,31,32,39,40,41,48,49,50}, {33,34,35,42,43,44,51,52,53},
  {54,55,56,63,64,65,72,73,74}, {57,58,59,66,67,68,75,76,77},
  {60,61,62,69,70,71,78,79,80}},
            j[54][15] = {    // Empty 3 Cell positions either Box-Row or Box-Column wise and affected empty 6+6 Cell positions for Intersection Removal
  { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20},
  { 3, 4, 5, 0, 1, 2, 6, 7, 8,12,13,14,21,22,23},
  { 6, 7, 8, 0, 1, 2, 3, 4, 5,15,16,17,24,25,26},
  { 9,10,11,12,13,14,15,16,17, 0, 1, 2,18,19,20},
  {12,13,14, 9,10,11,15,16,17, 3, 4, 5,21,22,23},
  {15,16,17, 9,10,11,12,13,14, 6, 7, 8,24,25,26},
  {18,19,20,21,22,23,24,25,26, 0, 1, 2, 9,10,11},
  {21,22,23,18,19,20,24,25,26, 3, 4, 5,12,13,14},
  {24,25,26,18,19,20,21,22,23, 6, 7, 8,15,16,17},
  {27,28,29,30,31,32,33,34,35,36,37,38,45,46,47},
  {30,31,32,27,28,29,33,34,35,39,40,41,48,49,50},
  {33,34,35,27,28,29,30,31,32,42,43,44,51,52,53},
  {36,37,38,39,40,41,42,43,44,27,28,29,45,46,47},
  {39,40,41,36,37,38,42,43,44,30,31,32,48,49,50},
  {42,43,44,36,37,38,39,40,41,33,34,35,51,52,53},
  {45,46,47,48,49,50,51,52,53,27,28,29,36,37,38},
  {48,49,50,45,46,47,51,52,53,30,31,32,39,40,41},
  {51,52,53,45,46,47,48,49,50,33,34,35,42,43,44},
  {54,55,56,57,58,59,60,61,62,63,64,65,72,73,74},
  {57,58,59,54,55,56,60,61,62,66,67,68,75,76,77},
  {60,61,62,54,55,56,57,58,59,69,70,71,78,79,80},
  {63,64,65,66,67,68,69,70,71,54,55,56,72,73,74},
  {66,67,68,63,64,65,69,70,71,57,58,59,75,76,77},
  {69,70,71,63,64,65,66,67,68,60,61,62,78,79,80},
  {72,73,74,75,76,77,78,79,80,54,55,56,63,64,65},
  {75,76,77,72,73,74,78,79,80,57,58,59,66,67,68},
  {78,79,80,72,73,74,75,76,77,60,61,62,69,70,71},
  { 0, 9,18,27,36,45,54,63,72, 1, 2,10,11,19,20},
  {27,36,45, 0, 9,18,54,63,72,28,29,37,38,46,47},
  {54,63,72, 0, 9,18,27,36,45,55,56,64,65,73,74},
  { 1,10,19,28,37,46,55,64,73, 0, 2, 9,11,18,20},
  {28,37,46, 1,10,19,55,64,73,27,29,36,38,45,47},
  {55,64,73, 1,10,19,28,37,46,54,56,63,65,72,74},
  { 2,11,20,29,38,47,56,65,74, 0, 1, 9,10,18,19},
  {29,38,47, 2,11,20,56,65,74,27,28,36,37,45,46},
  {56,65,74, 2,11,20,29,38,47,54,55,63,64,72,73},
  { 3,12,21,30,39,48,57,66,75, 4, 5,13,14,22,23},
  {30,39,48, 3,12,21,57,66,75,31,32,40,41,49,50},
  {57,66,75, 3,12,21,30,39,48,58,59,67,68,76,77},
  { 4,13,22,31,40,49,58,67,76, 3, 5,12,14,21,23},
  {31,40,49, 4,13,22,58,67,76,30,32,39,41,48,50},
  {58,67,76, 4,13,22,31,40,49,57,59,66,68,75,77},
  { 5,14,23,32,41,50,59,68,77, 3, 4,12,13,21,22},
  {32,41,50, 5,14,23,59,68,77,30,31,39,40,48,49},
  {59,68,77, 5,14,23,32,41,50,57,58,66,67,75,76},
  { 6,15,24,33,42,51,60,69,78, 7, 8,16,17,25,26},
  {33,42,51, 6,15,24,60,69,78,34,35,43,44,52,53},
  {60,69,78, 6,15,24,33,42,51,61,62,70,71,79,80},
  { 7,16,25,34,43,52,61,70,79, 6, 8,15,17,24,26},
  {34,43,52, 7,16,25,61,70,79,33,35,42,44,51,53},
  {61,70,79, 7,16,25,34,43,52,60,62,69,71,78,80},
  { 8,17,26,35,44,53,62,71,80, 6, 7,15,16,24,25},
  {35,44,53, 8,17,26,62,71,80,33,34,42,43,51,52},
  {62,71,80, 8,17,26,35,44,53,60,61,69,70,78,79}};

long n,                      // Number of guesses Board wise
     h;                      // Number of Hidden Singles Board wise

bool g[81][9];               // Candidates empty Cell position wise

long b2d(char p)             // Convert Candidates from boolean to digits
{
  int z = (g[p][0] ? 1 : 0) + (g[p][1] ? 2 : 0) + (g[p][2] ? 4 : 0)
        + (g[p][3] ? 8 : 0) + (g[p][4] ? 16 : 0) + (g[p][5] ? 32 : 0)
        + (g[p][6] ? 64 : 0) + (g[p][7] ? 128 : 0) + (g[p][8] ? 256 : 0);

  return bd[z];
}

bool solve(char p)
{
  char a,
       x = p,
       y;

  long z = b2d(r[x]);

  for(a = p + 1; z > 9 && a < q; a++)
    if(z > b2d(r[a]))        // Check least Candidates empty Cell position wise
    {
      x = a;
      z = b2d(r[x]);
      if (z < 10)            // Found Naked Single Candidate
        goto NHSCF;
    }
    for(char zr, rr, b = 0; b < 27; b++)
    {
      for(a = 0; a < 9; a++)
      {
        for(rr = 0, y = 0; y < 9; y++)
          if(g[l[b][y]][a])  // Check Hidden Candidate
          {
            rr++;
            zr = y;
          }
        if(rr == 1)          // Found Hidden Single Candidate
        {
          for(h++, z = a + 1, a = l[b][zr], x = p; x < q; x++)
            if(r[x] == a)
              goto NHSCF;
        }
      }
    }
    for(char b = 0; b < 54; b++)
      for(a = 0; a < 9; a++)
        if(g[j[b][0]][a] || g[j[b][1]][a] || g[j[b][2]][a])
        {                    // Check Candidate within empty 3 Cell positions either Box-Row or Box-Column wise
          if(g[j[b][3]][a] || g[j[b][4]][a] || g[j[b][5]][a] || g[j[b][6]][a] || g[j[b][7]][a] || g[j[b][8]][a])
          {                  // Check Candidate within affected empty 6 Cell positions either Row or Column wise
            if(!(g[j[b][9]][a] || g[j[b][10]][a] || g[j[b][11]][a] || g[j[b][12]][a] || g[j[b][13]][a] || g[j[b][14]][a]))
            {                // Check Candidate within affected empty 6 Cells positions Box wise
              bool k[6] = { 0, 0, 0, 0, 0, 0};

              for(y = 3; y < 9; y++)
                if(g[j[b][y]][a])
                {            // Backup Candidate within affected empty 6 Cell positions either Row or Column wise
                  k[y - 3] = 1;
                  g[j[b][y]][a] = 0;
                }
              if(solve(p))
                return 1;
              for(y = 3; y < 9; y++)
                if(k[y - 3]) // Restore Candidate within affected empty 6 Cell positions either Row or Column wise
                  g[j[b][y]][a] = 1;
            }
          }
          else if(g[j[b][9]][a] || g[j[b][10]][a] || g[j[b][11]][a] || g[j[b][12]][a] || g[j[b][13]][a] || g[j[b][14]][a])
          {                  // Check Candidate within affected empty 6 Cell positions Box wise
            bool k[6] = { 0, 0, 0, 0, 0, 0};

            for(y = 9; y < 15; y++)
              if(g[j[b][y]][a])
              {              // Backup Candidate within affected empty 6 Cell positions Box wise
                k[y - 9] = 1;
                g[j[b][y]][a] = 0;
              }
            if(solve(p))
              return 1;
            for(y = 9; y < 15; y++)
              if(k[y - 9])   // Restore Candidate within affected empty 6 Cell positions Box wise
                g[j[b][y]][a] = 1;
          }
        }
NHSCF:
  if(x > p)                  // Check define Cell position for sorting and eliminating
  {
    a = r[p];
    r[p] = r[x];
    r[x] = a;
  }
  for(; (s[r[p]] = z % 10) > 0; n++, z /= 10)
  {
    bool k[29] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

    for(a = 0; a < 9; a++)   // Backup define Cell position Candidates wise
      if(g[r[p]][a])
      {
        k[a + 20] = 1;
        g[r[p]][a] = 0;
      }
    for(a = 0; a < 20; a++)  // Backup Candidate within affected empty 20 Cell positions wise
      if(g[w[r[p]][a]][s[r[p]] - 1])
      {
        if(b2d(w[r[p]][a]) < 10)
          break;
        k[a] = 1;
        g[w[r[p]][a]][s[r[p]] - 1] = 0;
      }
    if(a > 19 && (p + 1 >= q || solve(p + 1)))
      return 1;              // If either all empty Cell positions defined or recursive solve for next empty Cell position
    for(a = 0; a < 9; a++)   // Restore Candidates define Cell position wise
      if(k[a + 20])
        g[r[p]][a] = 1;
    for(a = 0; a < 20; a++)  // Restore Candidate within affected empty 20 Cell positions wise
      if(k[a])
        g[w[r[p]][a]][s[r[p]] - 1] = 1;
  }
  return 0;
}

bool check(char p, char q)
{
  for(char a = 0; a < 20; a++)
    if(s[w[p][a]] == q)      // Check duplicate Candidate within affected empty 20 Cell positions wise
      return 0;
  return 1;
}

bool invalid(void)
{
  for(char p = 0; p < 81; p++)
    if(!s[p])                // Found empty Cell position
    {
      for(char a = 0; a < 9; a++)
        g[p][a] = check(p, a + 1);
                             // Check and assign Candidate for empty Cell positions
      if(!b2d(p))            // Check no Candidate assigned
        return 1;
      r[q++] = p;            // Assign empty Cell position for sorting and eliminating
    }
    else if(!check(p, s[p])) // Check all pre define Cell positions constraint
      return 1;
  return 0;
}

int main(void)
{
  char a = 0,
       m;

  float c,
        d = 0,
        e = 0,
        f = 0;

  long i = 0,
       t = 0,
       u = 0,
       v = 0;

  FILE *o = fopen("sudoku.txt", "r");

  if(o == NULL)
    printf("Unable to open sudoku.txt file for read !!");
  else do
    if((m = fgetc(o)) != 10 && m != EOF && a < 81)
      s[a++] = m >= '1' && m <= '9' ? m - '0' : 0;
                             // Assign digit to pre define Cell position
    else if(m == 10 || m == EOF)
      {
        while(a < 81)
          s[a++] = 0;        // Clear remaining empty Cell positions
        n = h = q = 0;
        c = clock();
        if(invalid())
        {
          c = (clock() - c) / CLOCKS_PER_SEC * 1000;
          d += c;
          printf("%ld) Error: Invalid Sudoku! # I%ld", ++t, ++i);
        }
        else if(solve(0))
        {
          c = (clock() - c) / CLOCKS_PER_SEC * 1000;
          e += c;
          printf("%ld) ", ++t);
          for(a = 0; a < 81; a++)
            printf("%c", s[a] ? s[a] + '0' : '.');
          printf(" # S%ld", ++v);
        }
        else
        {
          c = (clock() - c) / CLOCKS_PER_SEC * 1000;
          f += c;
          printf("%ld) Error: Unsolvable Sudoku! # U%ld", ++t, ++u);
        }
        printf(" # N%ld # H%ld # %f\n", n, h, c);
        a = 0;
      }
  while(m != EOF);
  printf("=======================================\n");
  printf("Total Sudoku puzzle read   : %ld\n", t);
  printf("Total time for all puzzles : %f\n", d + e + f);
  printf("Average time per puzzle    : %f\n", t ? (d + e + f) / t : 0);
  printf("Number of invalid puzzles  : %ld\n", i);
  printf("Time for invalid puzzles   : %f\n", d);
  printf("Average time per invalid   : %f\n", i ? d / i : 0);
  printf("Number of solved puzzles   : %ld\n", v);
  printf("Time for solved puzzles    : %f\n", e);
  printf("Average time per solved    : %f\n", v ? e / v : 0);
  printf("Number of unsolved puzzle  : %ld\n", u);
  printf("Time for unsolved puzzles  : %f\n", f);
  printf("Average time per unsolved  : %f\n", u ? f / u : 0);
  if(fclose(o) == EOF)
    printf("Unable to close sudoku.txt file !!");
}

R. Jamil

Edit 20170113
Subject included "Bitwise/" word.

[rjamil]

Hi all,

I worked hard to speed-up my RJSolver.CPP (as source provided above, which I stopped working due setbb.com/sudoku forum dead).

My new improvements solely based on speed instead of logic.

Here is the source code (probably the last one, except bugs rectifying and/or any suggestions for improvements implementing) for your valuable comments/feedback.

I would like to welcome serious Sudoku programmers to comment, especially on my Intersection Removal routine.

Code: Select all

#include <stdio.h>
#include <time.h>

int q,                       // Number of empty Cell positions
    r[81],                   // Used for sorting and eliminating empty Cell positions
    s[81],                   // Sudoku empty 81 Cell positions Board wise
    g[81][9],                // Candidates empty Cell position wise
    n,                       // Number of guesses Board wise
    h;                       // Number of Hidden Singles Board wise

static int bd[512] = {       // Boolean to Digit
          0,        1,        2,       21,        3,       31,       32,      321,
          4,       41,       42,      421,       43,      431,      432,     4321,
          5,       51,       52,      521,       53,      531,      532,     5321,
         54,      541,      542,     5421,      543,     5431,     5432,    54321,
          6,       61,       62,      621,       63,      631,      632,     6321,
         64,      641,      642,     6421,      643,     6431,     6432,    64321,
         65,      651,      652,     6521,      653,     6531,     6532,    65321,
        654,     6541,     6542,    65421,     6543,    65431,    65432,   654321,
          7,       71,       72,      721,       73,      731,      732,     7321,
         74,      741,      742,     7421,      743,     7431,     7432,    74321,
         75,      751,      752,     7521,      753,     7531,     7532,    75321,
        754,     7541,     7542,    75421,     7543,    75431,    75432,   754321,
         76,      761,      762,     7621,      763,     7631,     7632,    76321,
        764,     7641,     7642,    76421,     7643,    76431,    76432,   764321,
        765,     7651,     7652,    76521,     7653,    76531,    76532,   765321,
       7654,    76541,    76542,   765421,    76543,   765431,   765432,  7654321,
          8,       81,       82,      821,       83,      831,      832,     8321,
         84,      841,      842,     8421,      843,     8431,     8432,    84321,
         85,      851,      852,     8521,      853,     8531,     8532,    85321,
        854,     8541,     8542,     5421,     8543,    85431,    85432,   854321,
         86,      861,      862,     8621,      863,     8631,     8632,    86321,
        864,     8641,     8642,    86421,     8643,    86431,    86432,   864321,
        865,     8651,     8652,    86521,     8653,    86531,    86532,   865321,
       8654,    86541,    86542,   865421,    86543,   865431,   865432,  8654321,
         87,      871,      872,     8721,      873,     8731,     8732,    87321,
        874,     8741,     8742,    87421,     8743,    87431,    87432,   874321,
        875,     8751,     8752,    87521,     8753,    87531,    87532,   875321,
       8754,    87541,    87542,   875421,    87543,   875431,   875432,  8754321,
        876,     8761,     8762,    87621,     8763,    87631,    87632,   876321,
       8764,    87641,    87642,   876421,    87643,   876431,   876432,  8764321,
       8765,    87651,    87652,   876521,    87653,   876531,   876532,  8765321,
      87654,   876541,   876542,  8765421,   876543,  8765431,  8765432, 87654321,
          9,       91,       92,      921,       93,      931,      932,     9321,
         94,      941,      942,     9421,      943,     9431,     9432,    94321,
         95,      951,      952,     9521,      953,     9531,     9532,    95321,
        954,     9541,     9542,    95421,     9543,    95431,    95432,   954321,
         96,      961,      962,     9621,      963,     9631,     9632,    96321,
        964,     9641,     9642,    96421,     9643,    96431,    96432,   964321,
        965,     9651,     9652,    96521,     9653,    96531,    96532,   965321,
       9654,    96541,    96542,   965421,    96543,   965431,   965432,  9654321,
         97,      971,      972,     9721,      973,     9731,     9732,    97321,
        974,     9741,     9742,    97421,     9743,    97431,    97432,   974321,
        975,     9751,     9752,    97521,     9753,    97531,    97532,   975321,
       9754,    97541,    97542,   975421,    97543,   975431,   975432,  9754321,
        976,     9761,     9762,    97621,     9763,    97631,    97632,   976321,
       9764,    97641,    97642,   976421,    97643,   976431,   976432,  9764321,
       9765,    97651,    97652,   976521,    97653,   976531,   976532,  9765321,
      97654,   976541,   976542,  9765421,   976543,  9765431,  9765432, 97654321,
         98,      981,      982,     9821,      983,     9831,     9832,    98321,
        984,     9841,     9842,    98421,     9843,    98431,    98432,   984321,
        985,     9851,     9852,    98521,     9853,    98531,    98532,   985321,
       9854,    98541,    98542,    95421,    98543,   985431,   985432,  9854321,
        986,     9861,     9862,    98621,     9863,    98631,    98632,   986321,
       9864,    98641,    98642,   986421,    98643,   986431,   986432,  9864321,
       9865,    98651,    98652,   986521,    98653,   986531,   986532,  9865321,
      98654,   986541,   986542,  9865421,   986543,  9865431,  9865432, 98654321,
        987,     9871,     9872,    98721,     9873,    98731,    98732,   987321,
       9874,    98741,    98742,   987421,    98743,   987431,   987432,  9874321,
       9875,    98751,    98752,   987521,    98753,   987531,   987532,  9875321,
      98754,   987541,   987542,  9875421,   987543,  9875431,  9875432, 98754321,
       9876,    98761,    98762,   987621,    98763,   987631,   987632,  9876321,
      98764,   987641,   987642,  9876421,   987643,  9876431,  9876432, 98764321,
      98765,   987651,   987652,  9876521,   987653,  9876531,  9876532, 98765321,
     987654,  9876541,  9876542, 98765421,  9876543, 98765431, 98765432,987654321},
           w[81][20] = {     // Affected empty 20 Cell positions
  { 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20,27,36,45,54,63,72},
  { 0, 2, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20,28,37,46,55,64,73},
  { 0, 1, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20,29,38,47,56,65,74},
  { 0, 1, 2, 4, 5, 6, 7, 8,12,13,14,21,22,23,30,39,48,57,66,75},
  { 0, 1, 2, 3, 5, 6, 7, 8,12,13,14,21,22,23,31,40,49,58,67,76},
  { 0, 1, 2, 3, 4, 6, 7, 8,12,13,14,21,22,23,32,41,50,59,68,77},
  { 0, 1, 2, 3, 4, 5, 7, 8,15,16,17,24,25,26,33,42,51,60,69,78},
  { 0, 1, 2, 3, 4, 5, 6, 8,15,16,17,24,25,26,34,43,52,61,70,79},
  { 0, 1, 2, 3, 4, 5, 6, 7,15,16,17,24,25,26,35,44,53,62,71,80},
  { 0, 1, 2,10,11,12,13,14,15,16,17,18,19,20,27,36,45,54,63,72},
  { 0, 1, 2, 9,11,12,13,14,15,16,17,18,19,20,28,37,46,55,64,73},
  { 0, 1, 2, 9,10,12,13,14,15,16,17,18,19,20,29,38,47,56,65,74},
  { 3, 4, 5, 9,10,11,13,14,15,16,17,21,22,23,30,39,48,57,66,75},
  { 3, 4, 5, 9,10,11,12,14,15,16,17,21,22,23,31,40,49,58,67,76},
  { 3, 4, 5, 9,10,11,12,13,15,16,17,21,22,23,32,41,50,59,68,77},
  { 6, 7, 8, 9,10,11,12,13,14,16,17,24,25,26,33,42,51,60,69,78},
  { 6, 7, 8, 9,10,11,12,13,14,15,17,24,25,26,34,43,52,61,70,79},
  { 6, 7, 8, 9,10,11,12,13,14,15,16,24,25,26,35,44,53,62,71,80},
  { 0, 1, 2, 9,10,11,19,20,21,22,23,24,25,26,27,36,45,54,63,72},
  { 0, 1, 2, 9,10,11,18,20,21,22,23,24,25,26,28,37,46,55,64,73},
  { 0, 1, 2, 9,10,11,18,19,21,22,23,24,25,26,29,38,47,56,65,74},
  { 3, 4, 5,12,13,14,18,19,20,22,23,24,25,26,30,39,48,57,66,75},
  { 3, 4, 5,12,13,14,18,19,20,21,23,24,25,26,31,40,49,58,67,76},
  { 3, 4, 5,12,13,14,18,19,20,21,22,24,25,26,32,41,50,59,68,77},
  { 6, 7, 8,15,16,17,18,19,20,21,22,23,25,26,33,42,51,60,69,78},
  { 6, 7, 8,15,16,17,18,19,20,21,22,23,24,26,34,43,52,61,70,79},
  { 6, 7, 8,15,16,17,18,19,20,21,22,23,24,25,35,44,53,62,71,80},
  { 0, 9,18,28,29,30,31,32,33,34,35,36,37,38,45,46,47,54,63,72},
  { 1,10,19,27,29,30,31,32,33,34,35,36,37,38,45,46,47,55,64,73},
  { 2,11,20,27,28,30,31,32,33,34,35,36,37,38,45,46,47,56,65,74},
  { 3,12,21,27,28,29,31,32,33,34,35,39,40,41,48,49,50,57,66,75},
  { 4,13,22,27,28,29,30,32,33,34,35,39,40,41,48,49,50,58,67,76},
  { 5,14,23,27,28,29,30,31,33,34,35,39,40,41,48,49,50,59,68,77},
  { 6,15,24,27,28,29,30,31,32,34,35,42,43,44,51,52,53,60,69,78},
  { 7,16,25,27,28,29,30,31,32,33,35,42,43,44,51,52,53,61,70,79},
  { 8,17,26,27,28,29,30,31,32,33,34,42,43,44,51,52,53,62,71,80},
  { 0, 9,18,27,28,29,37,38,39,40,41,42,43,44,45,46,47,54,63,72},
  { 1,10,19,27,28,29,36,38,39,40,41,42,43,44,45,46,47,55,64,73},
  { 2,11,20,27,28,29,36,37,39,40,41,42,43,44,45,46,47,56,65,74},
  { 3,12,21,30,31,32,36,37,38,40,41,42,43,44,48,49,50,57,66,75},
  { 4,13,22,30,31,32,36,37,38,39,41,42,43,44,48,49,50,58,67,76},
  { 5,14,23,30,31,32,36,37,38,39,40,42,43,44,48,49,50,59,68,77},
  { 6,15,24,33,34,35,36,37,38,39,40,41,43,44,51,52,53,60,69,78},
  { 7,16,25,33,34,35,36,37,38,39,40,41,42,44,51,52,53,61,70,79},
  { 8,17,26,33,34,35,36,37,38,39,40,41,42,43,51,52,53,62,71,80},
  { 0, 9,18,27,28,29,36,37,38,46,47,48,49,50,51,52,53,54,63,72},
  { 1,10,19,27,28,29,36,37,38,45,47,48,49,50,51,52,53,55,64,73},
  { 2,11,20,27,28,29,36,37,38,45,46,48,49,50,51,52,53,56,65,74},
  { 3,12,21,30,31,32,39,40,41,45,46,47,49,50,51,52,53,57,66,75},
  { 4,13,22,30,31,32,39,40,41,45,46,47,48,50,51,52,53,58,67,76},
  { 5,14,23,30,31,32,39,40,41,45,46,47,48,49,51,52,53,59,68,77},
  { 6,15,24,33,34,35,42,43,44,45,46,47,48,49,50,52,53,60,69,78},
  { 7,16,25,33,34,35,42,43,44,45,46,47,48,49,50,51,53,61,70,79},
  { 8,17,26,33,34,35,42,43,44,45,46,47,48,49,50,51,52,62,71,80},
  { 0, 9,18,27,36,45,55,56,57,58,59,60,61,62,63,64,65,72,73,74},
  { 1,10,19,28,37,46,54,56,57,58,59,60,61,62,63,64,65,72,73,74},
  { 2,11,20,29,38,47,54,55,57,58,59,60,61,62,63,64,65,72,73,74},
  { 3,12,21,30,39,48,54,55,56,58,59,60,61,62,66,67,68,75,76,77},
  { 4,13,22,31,40,49,54,55,56,57,59,60,61,62,66,67,68,75,76,77},
  { 5,14,23,32,41,50,54,55,56,57,58,60,61,62,66,67,68,75,76,77},
  { 6,15,24,33,42,51,54,55,56,57,58,59,61,62,69,70,71,78,79,80},
  { 7,16,25,34,43,52,54,55,56,57,58,59,60,62,69,70,71,78,79,80},
  { 8,17,26,35,44,53,54,55,56,57,58,59,60,61,69,70,71,78,79,80},
  { 0, 9,18,27,36,45,54,55,56,64,65,66,67,68,69,70,71,72,73,74},
  { 1,10,19,28,37,46,54,55,56,63,65,66,67,68,69,70,71,72,73,74},
  { 2,11,20,29,38,47,54,55,56,63,64,66,67,68,69,70,71,72,73,74},
  { 3,12,21,30,39,48,57,58,59,63,64,65,67,68,69,70,71,75,76,77},
  { 4,13,22,31,40,49,57,58,59,63,64,65,66,68,69,70,71,75,76,77},
  { 5,14,23,32,41,50,57,58,59,63,64,65,66,67,69,70,71,75,76,77},
  { 6,15,24,33,42,51,60,61,62,63,64,65,66,67,68,70,71,78,79,80},
  { 7,16,25,34,43,52,60,61,62,63,64,65,66,67,68,69,71,78,79,80},
  { 8,17,26,35,44,53,60,61,62,63,64,65,66,67,68,69,70,78,79,80},
  { 0, 9,18,27,36,45,54,55,56,63,64,65,73,74,75,76,77,78,79,80},
  { 1,10,19,28,37,46,54,55,56,63,64,65,72,74,75,76,77,78,79,80},
  { 2,11,20,29,38,47,54,55,56,63,64,65,72,73,75,76,77,78,79,80},
  { 3,12,21,30,39,48,57,58,59,66,67,68,72,73,74,76,77,78,79,80},
  { 4,13,22,31,40,49,57,58,59,66,67,68,72,73,74,75,77,78,79,80},
  { 5,14,23,32,41,50,57,58,59,66,67,68,72,73,74,75,76,78,79,80},
  { 6,15,24,33,42,51,60,61,62,69,70,71,72,73,74,75,76,77,79,80},
  { 7,16,25,34,43,52,60,61,62,69,70,71,72,73,74,75,76,77,78,80},
  { 8,17,26,35,44,53,60,61,62,69,70,71,72,73,74,75,76,77,78,79}},
           l[27][9] = {      // Empty 9 Cell positions for Hidden Singles Row, Column and Box wise
  { 0, 1, 2, 3, 4, 5, 6, 7, 8}, { 9,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},
  { 0, 9,18,27,36,45,54,63,72}, { 1,10,19,28,37,46,55,64,73}, { 2,11,20,29,38,47,56,65,74},
  { 3,12,21,30,39,48,57,66,75}, { 4,13,22,31,40,49,58,67,76}, { 5,14,23,32,41,50,59,68,77},
  { 6,15,24,33,42,51,60,69,78}, { 7,16,25,34,43,52,61,70,79}, { 8,17,26,35,44,53,62,71,80},
  { 0, 1, 2, 9,10,11,18,19,20}, { 3, 4, 5,12,13,14,21,22,23}, { 6, 7, 8,15,16,17,24,25,26},
  {27,28,29,36,37,38,45,46,47}, {30,31,32,39,40,41,48,49,50}, {33,34,35,42,43,44,51,52,53},
  {54,55,56,63,64,65,72,73,74}, {57,58,59,66,67,68,75,76,77}, {60,61,62,69,70,71,78,79,80}},
           j[54][15] = {     // Empty 3 Cell positions Box-Row/Column wise and affected empty 6 Box + 6 Row/Column Cell positions for Intersection Removal
  { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20},
  { 3, 4, 5, 0, 1, 2, 6, 7, 8,12,13,14,21,22,23},
  { 6, 7, 8, 0, 1, 2, 3, 4, 5,15,16,17,24,25,26},
  { 9,10,11,12,13,14,15,16,17, 0, 1, 2,18,19,20},
  {12,13,14, 9,10,11,15,16,17, 3, 4, 5,21,22,23},
  {15,16,17, 9,10,11,12,13,14, 6, 7, 8,24,25,26},
  {18,19,20,21,22,23,24,25,26, 0, 1, 2, 9,10,11},
  {21,22,23,18,19,20,24,25,26, 3, 4, 5,12,13,14},
  {24,25,26,18,19,20,21,22,23, 6, 7, 8,15,16,17},
  {27,28,29,30,31,32,33,34,35,36,37,38,45,46,47},
  {30,31,32,27,28,29,33,34,35,39,40,41,48,49,50},
  {33,34,35,27,28,29,30,31,32,42,43,44,51,52,53},
  {36,37,38,39,40,41,42,43,44,27,28,29,45,46,47},
  {39,40,41,36,37,38,42,43,44,30,31,32,48,49,50},
  {42,43,44,36,37,38,39,40,41,33,34,35,51,52,53},
  {45,46,47,48,49,50,51,52,53,27,28,29,36,37,38},
  {48,49,50,45,46,47,51,52,53,30,31,32,39,40,41},
  {51,52,53,45,46,47,48,49,50,33,34,35,42,43,44},
  {54,55,56,57,58,59,60,61,62,63,64,65,72,73,74},
  {57,58,59,54,55,56,60,61,62,66,67,68,75,76,77},
  {60,61,62,54,55,56,57,58,59,69,70,71,78,79,80},
  {63,64,65,66,67,68,69,70,71,54,55,56,72,73,74},
  {66,67,68,63,64,65,69,70,71,57,58,59,75,76,77},
  {69,70,71,63,64,65,66,67,68,60,61,62,78,79,80},
  {72,73,74,75,76,77,78,79,80,54,55,56,63,64,65},
  {75,76,77,72,73,74,78,79,80,57,58,59,66,67,68},
  {78,79,80,72,73,74,75,76,77,60,61,62,69,70,71},
  { 0, 9,18,27,36,45,54,63,72, 1, 2,10,11,19,20},
  {27,36,45, 0, 9,18,54,63,72,28,29,37,38,46,47},
  {54,63,72, 0, 9,18,27,36,45,55,56,64,65,73,74},
  { 1,10,19,28,37,46,55,64,73, 0, 2, 9,11,18,20},
  {28,37,46, 1,10,19,55,64,73,27,29,36,38,45,47},
  {55,64,73, 1,10,19,28,37,46,54,56,63,65,72,74},
  { 2,11,20,29,38,47,56,65,74, 0, 1, 9,10,18,19},
  {29,38,47, 2,11,20,56,65,74,27,28,36,37,45,46},
  {56,65,74, 2,11,20,29,38,47,54,55,63,64,72,73},
  { 3,12,21,30,39,48,57,66,75, 4, 5,13,14,22,23},
  {30,39,48, 3,12,21,57,66,75,31,32,40,41,49,50},
  {57,66,75, 3,12,21,30,39,48,58,59,67,68,76,77},
  { 4,13,22,31,40,49,58,67,76, 3, 5,12,14,21,23},
  {31,40,49, 4,13,22,58,67,76,30,32,39,41,48,50},
  {58,67,76, 4,13,22,31,40,49,57,59,66,68,75,77},
  { 5,14,23,32,41,50,59,68,77, 3, 4,12,13,21,22},
  {32,41,50, 5,14,23,59,68,77,30,31,39,40,48,49},
  {59,68,77, 5,14,23,32,41,50,57,58,66,67,75,76},
  { 6,15,24,33,42,51,60,69,78, 7, 8,16,17,25,26},
  {33,42,51, 6,15,24,60,69,78,34,35,43,44,52,53},
  {60,69,78, 6,15,24,33,42,51,61,62,70,71,79,80},
  { 7,16,25,34,43,52,61,70,79, 6, 8,15,17,24,26},
  {34,43,52, 7,16,25,61,70,79,33,35,42,44,51,53},
  {61,70,79, 7,16,25,34,43,52,60,62,69,71,78,80},
  { 8,17,26,35,44,53,62,71,80, 6, 7,15,16,24,25},
  {35,44,53, 8,17,26,62,71,80,33,34,42,43,51,52},
  {62,71,80, 8,17,26,35,44,53,60,61,69,70,78,79}};

int b2d(int p)               // Convert Candidates from boolean to digits
{
  int z = g[p][0] + g[p][1] * 2 + g[p][2] * 4 + g[p][3] * 8 + g[p][4] * 16 +
    g[p][5] * 32 + g[p][6] * 64 + g[p][7] * 128 + g[p][8] * 256;

  return bd[z];
}

int solve(int p)
{
  int a,
      x,
      y,
      z = 987654322;

  for(a = p; a < q; a++)
    if(z > b2d(r[a]))        // Check least Candidates empty Cell position wise
      if((z = b2d(r[x = a])) < 10)
        goto NHSCF;          // Found Naked Single Candidate
  for(y = 0; y < 27; y++)
    for(a = 0; a < 9; a++)
      if(g[l[y][0]][a] + g[l[y][1]][a] + g[l[y][2]][a] + g[l[y][3]][a] + g[l[y][4]][a] +
        g[l[y][5]][a] + g[l[y][6]][a] + g[l[y][7]][a] + g[l[y][8]][a] == 1)
      {                      // Check Hidden Single Candidate
        x = g[l[y][0]][a] + g[l[y][1]][a] * 2 + g[l[y][2]][a] * 4 + g[l[y][3]][a] * 8 + g[l[y][4]][a] * 16 +
          g[l[y][5]][a] * 32 + g[l[y][6]][a] * 64 + g[l[y][7]][a] * 128 + g[l[y][8]][a] * 256;
        for(h++, z = a + 1, a = l[y][bd[x] - 1], x = p; x < q; x++)
          if(r[x] == a)
            goto NHSCF;
      }
  for(int b = 0; b < 54; b++)
    for(a = 0; a < 9; a++)
      if(g[j[b][0]][a] || g[j[b][1]][a] || g[j[b][2]][a])
      {                      // Check Candidate within empty 3 Cell positions either Box-Row or Box-Column wise
        if(g[j[b][3]][a] || g[j[b][4]][a] || g[j[b][5]][a] || g[j[b][6]][a] || g[j[b][7]][a] || g[j[b][8]][a])
        {                    // Check Candidate within affected empty 6 Cell positions either Row or Column wise
          if(!(g[j[b][9]][a] || g[j[b][10]][a] || g[j[b][11]][a] || g[j[b][12]][a] || g[j[b][13]][a] || g[j[b][14]][a]))
          {                  // Check Candidate within affected empty 6 Cells positions Box wise
            int k[6] = {g[j[b][3]][a], g[j[b][4]][a], g[j[b][5]][a], g[j[b][6]][a], g[j[b][7]][a], g[j[b][8]][a]};
                             // Backup Candidate within affected empty 6 Cell positions either Row or Column wise
            g[j[b][3]][a] = g[j[b][4]][a] = g[j[b][5]][a] = 0;
            g[j[b][6]][a] = g[j[b][7]][a] = g[j[b][8]][a] = 0;
            if(solve(p))
              return 1;
            g[j[b][3]][a] = k[0];
            g[j[b][4]][a] = k[1];
            g[j[b][5]][a] = k[2];
            g[j[b][6]][a] = k[3];
            g[j[b][7]][a] = k[4];
            g[j[b][8]][a] = k[5];
          }                  // Restore Candidate within affected empty 6 Cell positions either Row or Column wise
        }
        else
          if(g[j[b][9]][a] || g[j[b][10]][a] || g[j[b][11]][a] || g[j[b][12]][a] || g[j[b][13]][a] || g[j[b][14]][a])
          {                  // Check Candidate within affected empty 6 Cell positions Box wise
            int k[6] = {g[j[b][9]][a], g[j[b][10]][a], g[j[b][11]][a], g[j[b][12]][a], g[j[b][13]][a], g[j[b][14]][a]};
                             // Backup Candidate within affected empty 6 Cell positions Box wise
            g[j[b][9]][a] = g[j[b][10]][a] = g[j[b][11]][a] = 0;
            g[j[b][12]][a] = g[j[b][13]][a] = g[j[b][14]][a] = 0;
            if(solve(p))
              return 1;
            g[j[b][9]][a] = k[0];
            g[j[b][10]][a] = k[1];
            g[j[b][11]][a] = k[2];
            g[j[b][12]][a] = k[3];
            g[j[b][13]][a] = k[4];
            g[j[b][14]][a] = k[5];
          }                  // Restore Candidate within affected empty 6 Cell positions Box wise
      }
NHSCF:
  if(x > p)                  // Check define Cell position for sorting and eliminating
  {
    a = r[p];
    r[p] = r[x];
    r[x] = a;
  }
  for(; (s[r[p]] = z % 10) > 0; n++, z /= 10)
  {
    int k[29] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      g[r[p]][0], g[r[p]][1], g[r[p]][2], g[r[p]][3], g[r[p]][4], g[r[p]][5], g[r[p]][6], g[r[p]][7], g[r[p]][8]};
                             // Backup define Cell position Candidates wise
    g[r[p]][0] = g[r[p]][1] = g[r[p]][2] = 0;
    g[r[p]][3] = g[r[p]][4] = g[r[p]][5] = 0;
    g[r[p]][6] = g[r[p]][7] = g[r[p]][8] = 0;
    for(a = 0; a < 20; a++)  // Backup Candidate within affected empty 20 Cell positions wise
      if(g[w[r[p]][a]][s[r[p]] - 1])
      {
        if(b2d(w[r[p]][a]) < 10)
          break;
        k[a] = 1;
        g[w[r[p]][a]][s[r[p]] - 1] = 0;
      }
    if(a > 19 && (p + 1 >= q || solve(p + 1)))
      return 1;              // If either all empty Cell positions defined or recursive solve for next empty Cell position
    g[r[p]][0] = k[20];      // Restore Candidates define Cell position wise
    g[r[p]][1] = k[21];
    g[r[p]][2] = k[22];
    g[r[p]][3] = k[23];
    g[r[p]][4] = k[24];
    g[r[p]][5] = k[25];
    g[r[p]][6] = k[26];
    g[r[p]][7] = k[27];
    g[r[p]][8] = k[28];
    while(a > 0)             // Restore Candidate within affected empty 20 Cell positions wise
      g[w[r[p]][--a]][s[r[p]] - 1] = k[a];
  }
  return 0;
}

int check(int p, int q)
{
  for(int a = 0; a < 20; a++)
    if(s[w[p][a]] == q)      // Check duplicate Candidate within affected empty 20 Cell positions wise
      return 0;
  return 1;
}

int invalid(void)
{
  for(int p = 0; p < 81; p++)
    if(!s[p])                // Found empty Cell position
    {
      for(int a = 0; a < 9; a++)
        g[p][a] = check(p, a + 1);
                             // Check and assign Candidate for empty Cell positions
      if(!b2d(p))            // Check no Candidate assigned
        return 1;
      r[q++] = p;            // Assign empty Cell position for sorting and eliminating
    }
    else if(!check(p, s[p])) // Check all pre define Cell positions constraint
      return 1;
  return 0;
}

int main(void)
{
  int a = 0,
      m,
      i = 0,
      t = 0,
      u = 0,
      v = 0;

  float c,
        d = 0,
        e = 0,
        f = 0;

  FILE *o = fopen("sudoku.txt", "r");

  if(o == NULL)
    printf("Unable to open sudoku.txt file for read !!");
  else
    do
      if((m = fgetc(o)) != 10 && m != EOF && a < 81)
        s[a++] = m >= '1' && m <= '9' ? m - '0' : 0;
                             // Assign digit to pre define Cell position
      else
        if(m == 10 || m == EOF)
        {
          while(a < 81)
            s[a++] = 0;      // Clear remaining empty Cell positions
          n = h = q = 0;
          c = clock();
          if(invalid())
          {
            c = (clock() - c) / CLOCKS_PER_SEC * 1000;
            d += c;
            printf("%ld) Error: Invalid Sudoku! # I%ld", ++t, ++i);
          }
          else
            if(solve(0))
            {
              c = (clock() - c) / CLOCKS_PER_SEC * 1000;
              e += c;
              printf("%ld) ", ++t);
              for(a = 0; a < 81; a++)
                printf("%c", s[a] ? s[a] + '0' : '.');
              printf(" # S%ld", ++v);
            }
            else
            {
              c = (clock() - c) / CLOCKS_PER_SEC * 1000;
              f += c;
              printf("%ld) Error: Unsolvable Sudoku! # U%ld", ++t, ++u);
            }
          printf(" # N%ld # H%ld # %f\n", n, h, c);
          a = 0;
        }
    while(m != EOF);
  printf("=======================================\n");
  printf("Total Sudoku puzzle read   : %ld\n", t);
  printf("Total time for all puzzles : %f\n", d + e + f);
  printf("Average time per puzzle    : %f\n", t ? (d + e + f) / t : 0);
  printf("Number of invalid puzzles  : %ld\n", i);
  printf("Time for invalid puzzles   : %f\n", d);
  printf("Average time per invalid   : %f\n", i ? d / i : 0);
  printf("Number of solved puzzles   : %ld\n", v);
  printf("Time for solved puzzles    : %f\n", e);
  printf("Average time per solved    : %f\n", v ? e / v : 0);
  printf("Number of unsolved puzzle  : %ld\n", u);
  printf("Time for unsolved puzzles  : %f\n", f);
  printf("Average time per unsolved  : %f\n", u ? f / u : 0);
  if(fclose(o) == EOF)
    printf("Unable to close sudoku.txt file !!");
}

1st Modification (20150820):
Replace:

Code: Select all

    for(a = 0; a < 20; a++)  // Restore Candidate within affected empty 20 Cell positions wise
      if(k[a])
        g[w[r[p]][a]][s[r[p]] - 1] = 1;

With:

Code: Select all

    while(a > 0)             // Restore Candidate within affected empty 20 Cell positions wise
      g[w[r[p]][--a]][s[r[p]] - 1] = k[a];

R. Jamil

[rjamil]

Hi all,

I am trying to learn bit bashing (bit manipulation) recently by trial and error method.

Trying to implement the same by converting my Boolean Sudoku Solver in to Binary Sudoku Solver.

Code: Select all

#include <stdio.h>
#include <time.h>

int q,                       // Number of empty Cell positions
    r[81][2],                // Used for sorting and eliminating empty Cell positions
    s[81],                   // Sudoku empty 81 Cell positions Board wise
    g[81],                   // Candidates empty Cell position wise
    n,                       // Number of guesses Board wise
    h;                       // Number of Hidden Singles Board wise

static int b[512] = {        // Binary to Digit
  987654322,        1,        2,       21,        3,       31,       32,      321,
          4,       41,       42,      421,       43,      431,      432,     4321,
          5,       51,       52,      521,       53,      531,      532,     5321,
         54,      541,      542,     5421,      543,     5431,     5432,    54321,
          6,       61,       62,      621,       63,      631,      632,     6321,
         64,      641,      642,     6421,      643,     6431,     6432,    64321,
         65,      651,      652,     6521,      653,     6531,     6532,    65321,
        654,     6541,     6542,    65421,     6543,    65431,    65432,   654321,
          7,       71,       72,      721,       73,      731,      732,     7321,
         74,      741,      742,     7421,      743,     7431,     7432,    74321,
         75,      751,      752,     7521,      753,     7531,     7532,    75321,
        754,     7541,     7542,    75421,     7543,    75431,    75432,   754321,
         76,      761,      762,     7621,      763,     7631,     7632,    76321,
        764,     7641,     7642,    76421,     7643,    76431,    76432,   764321,
        765,     7651,     7652,    76521,     7653,    76531,    76532,   765321,
       7654,    76541,    76542,   765421,    76543,   765431,   765432,  7654321,
          8,       81,       82,      821,       83,      831,      832,     8321,
         84,      841,      842,     8421,      843,     8431,     8432,    84321,
         85,      851,      852,     8521,      853,     8531,     8532,    85321,
        854,     8541,     8542,     5421,     8543,    85431,    85432,   854321,
         86,      861,      862,     8621,      863,     8631,     8632,    86321,
        864,     8641,     8642,    86421,     8643,    86431,    86432,   864321,
        865,     8651,     8652,    86521,     8653,    86531,    86532,   865321,
       8654,    86541,    86542,   865421,    86543,   865431,   865432,  8654321,
         87,      871,      872,     8721,      873,     8731,     8732,    87321,
        874,     8741,     8742,    87421,     8743,    87431,    87432,   874321,
        875,     8751,     8752,    87521,     8753,    87531,    87532,   875321,
       8754,    87541,    87542,   875421,    87543,   875431,   875432,  8754321,
        876,     8761,     8762,    87621,     8763,    87631,    87632,   876321,
       8764,    87641,    87642,   876421,    87643,   876431,   876432,  8764321,
       8765,    87651,    87652,   876521,    87653,   876531,   876532,  8765321,
      87654,   876541,   876542,  8765421,   876543,  8765431,  8765432, 87654321,
          9,       91,       92,      921,       93,      931,      932,     9321,
         94,      941,      942,     9421,      943,     9431,     9432,    94321,
         95,      951,      952,     9521,      953,     9531,     9532,    95321,
        954,     9541,     9542,    95421,     9543,    95431,    95432,   954321,
         96,      961,      962,     9621,      963,     9631,     9632,    96321,
        964,     9641,     9642,    96421,     9643,    96431,    96432,   964321,
        965,     9651,     9652,    96521,     9653,    96531,    96532,   965321,
       9654,    96541,    96542,   965421,    96543,   965431,   965432,  9654321,
         97,      971,      972,     9721,      973,     9731,     9732,    97321,
        974,     9741,     9742,    97421,     9743,    97431,    97432,   974321,
        975,     9751,     9752,    97521,     9753,    97531,    97532,   975321,
       9754,    97541,    97542,   975421,    97543,   975431,   975432,  9754321,
        976,     9761,     9762,    97621,     9763,    97631,    97632,   976321,
       9764,    97641,    97642,   976421,    97643,   976431,   976432,  9764321,
       9765,    97651,    97652,   976521,    97653,   976531,   976532,  9765321,
      97654,   976541,   976542,  9765421,   976543,  9765431,  9765432, 97654321,
         98,      981,      982,     9821,      983,     9831,     9832,    98321,
        984,     9841,     9842,    98421,     9843,    98431,    98432,   984321,
        985,     9851,     9852,    98521,     9853,    98531,    98532,   985321,
       9854,    98541,    98542,    95421,    98543,   985431,   985432,  9854321,
        986,     9861,     9862,    98621,     9863,    98631,    98632,   986321,
       9864,    98641,    98642,   986421,    98643,   986431,   986432,  9864321,
       9865,    98651,    98652,   986521,    98653,   986531,   986532,  9865321,
      98654,   986541,   986542,  9865421,   986543,  9865431,  9865432, 98654321,
        987,     9871,     9872,    98721,     9873,    98731,    98732,   987321,
       9874,    98741,    98742,   987421,    98743,   987431,   987432,  9874321,
       9875,    98751,    98752,   987521,    98753,   987531,   987532,  9875321,
      98754,   987541,   987542,  9875421,   987543,  9875431,  9875432, 98754321,
       9876,    98761,    98762,   987621,    98763,   987631,   987632,  9876321,
      98764,   987641,   987642,  9876421,   987643,  9876431,  9876432, 98764321,
      98765,   987651,   987652,  9876521,   987653,  9876531,  9876532, 98765321,
     987654,  9876541,  9876542, 98765421,  9876543, 98765431, 98765432,987654321},
           w[81][20] = {     // Affected empty 20 Cell positions
  { 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20,27,36,45,54,63,72},
  { 0, 2, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20,28,37,46,55,64,73},
  { 0, 1, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20,29,38,47,56,65,74},
  { 0, 1, 2, 4, 5, 6, 7, 8,12,13,14,21,22,23,30,39,48,57,66,75},
  { 0, 1, 2, 3, 5, 6, 7, 8,12,13,14,21,22,23,31,40,49,58,67,76},
  { 0, 1, 2, 3, 4, 6, 7, 8,12,13,14,21,22,23,32,41,50,59,68,77},
  { 0, 1, 2, 3, 4, 5, 7, 8,15,16,17,24,25,26,33,42,51,60,69,78},
  { 0, 1, 2, 3, 4, 5, 6, 8,15,16,17,24,25,26,34,43,52,61,70,79},
  { 0, 1, 2, 3, 4, 5, 6, 7,15,16,17,24,25,26,35,44,53,62,71,80},
  { 0, 1, 2,10,11,12,13,14,15,16,17,18,19,20,27,36,45,54,63,72},
  { 0, 1, 2, 9,11,12,13,14,15,16,17,18,19,20,28,37,46,55,64,73},
  { 0, 1, 2, 9,10,12,13,14,15,16,17,18,19,20,29,38,47,56,65,74},
  { 3, 4, 5, 9,10,11,13,14,15,16,17,21,22,23,30,39,48,57,66,75},
  { 3, 4, 5, 9,10,11,12,14,15,16,17,21,22,23,31,40,49,58,67,76},
  { 3, 4, 5, 9,10,11,12,13,15,16,17,21,22,23,32,41,50,59,68,77},
  { 6, 7, 8, 9,10,11,12,13,14,16,17,24,25,26,33,42,51,60,69,78},
  { 6, 7, 8, 9,10,11,12,13,14,15,17,24,25,26,34,43,52,61,70,79},
  { 6, 7, 8, 9,10,11,12,13,14,15,16,24,25,26,35,44,53,62,71,80},
  { 0, 1, 2, 9,10,11,19,20,21,22,23,24,25,26,27,36,45,54,63,72},
  { 0, 1, 2, 9,10,11,18,20,21,22,23,24,25,26,28,37,46,55,64,73},
  { 0, 1, 2, 9,10,11,18,19,21,22,23,24,25,26,29,38,47,56,65,74},
  { 3, 4, 5,12,13,14,18,19,20,22,23,24,25,26,30,39,48,57,66,75},
  { 3, 4, 5,12,13,14,18,19,20,21,23,24,25,26,31,40,49,58,67,76},
  { 3, 4, 5,12,13,14,18,19,20,21,22,24,25,26,32,41,50,59,68,77},
  { 6, 7, 8,15,16,17,18,19,20,21,22,23,25,26,33,42,51,60,69,78},
  { 6, 7, 8,15,16,17,18,19,20,21,22,23,24,26,34,43,52,61,70,79},
  { 6, 7, 8,15,16,17,18,19,20,21,22,23,24,25,35,44,53,62,71,80},
  { 0, 9,18,28,29,30,31,32,33,34,35,36,37,38,45,46,47,54,63,72},
  { 1,10,19,27,29,30,31,32,33,34,35,36,37,38,45,46,47,55,64,73},
  { 2,11,20,27,28,30,31,32,33,34,35,36,37,38,45,46,47,56,65,74},
  { 3,12,21,27,28,29,31,32,33,34,35,39,40,41,48,49,50,57,66,75},
  { 4,13,22,27,28,29,30,32,33,34,35,39,40,41,48,49,50,58,67,76},
  { 5,14,23,27,28,29,30,31,33,34,35,39,40,41,48,49,50,59,68,77},
  { 6,15,24,27,28,29,30,31,32,34,35,42,43,44,51,52,53,60,69,78},
  { 7,16,25,27,28,29,30,31,32,33,35,42,43,44,51,52,53,61,70,79},
  { 8,17,26,27,28,29,30,31,32,33,34,42,43,44,51,52,53,62,71,80},
  { 0, 9,18,27,28,29,37,38,39,40,41,42,43,44,45,46,47,54,63,72},
  { 1,10,19,27,28,29,36,38,39,40,41,42,43,44,45,46,47,55,64,73},
  { 2,11,20,27,28,29,36,37,39,40,41,42,43,44,45,46,47,56,65,74},
  { 3,12,21,30,31,32,36,37,38,40,41,42,43,44,48,49,50,57,66,75},
  { 4,13,22,30,31,32,36,37,38,39,41,42,43,44,48,49,50,58,67,76},
  { 5,14,23,30,31,32,36,37,38,39,40,42,43,44,48,49,50,59,68,77},
  { 6,15,24,33,34,35,36,37,38,39,40,41,43,44,51,52,53,60,69,78},
  { 7,16,25,33,34,35,36,37,38,39,40,41,42,44,51,52,53,61,70,79},
  { 8,17,26,33,34,35,36,37,38,39,40,41,42,43,51,52,53,62,71,80},
  { 0, 9,18,27,28,29,36,37,38,46,47,48,49,50,51,52,53,54,63,72},
  { 1,10,19,27,28,29,36,37,38,45,47,48,49,50,51,52,53,55,64,73},
  { 2,11,20,27,28,29,36,37,38,45,46,48,49,50,51,52,53,56,65,74},
  { 3,12,21,30,31,32,39,40,41,45,46,47,49,50,51,52,53,57,66,75},
  { 4,13,22,30,31,32,39,40,41,45,46,47,48,50,51,52,53,58,67,76},
  { 5,14,23,30,31,32,39,40,41,45,46,47,48,49,51,52,53,59,68,77},
  { 6,15,24,33,34,35,42,43,44,45,46,47,48,49,50,52,53,60,69,78},
  { 7,16,25,33,34,35,42,43,44,45,46,47,48,49,50,51,53,61,70,79},
  { 8,17,26,33,34,35,42,43,44,45,46,47,48,49,50,51,52,62,71,80},
  { 0, 9,18,27,36,45,55,56,57,58,59,60,61,62,63,64,65,72,73,74},
  { 1,10,19,28,37,46,54,56,57,58,59,60,61,62,63,64,65,72,73,74},
  { 2,11,20,29,38,47,54,55,57,58,59,60,61,62,63,64,65,72,73,74},
  { 3,12,21,30,39,48,54,55,56,58,59,60,61,62,66,67,68,75,76,77},
  { 4,13,22,31,40,49,54,55,56,57,59,60,61,62,66,67,68,75,76,77},
  { 5,14,23,32,41,50,54,55,56,57,58,60,61,62,66,67,68,75,76,77},
  { 6,15,24,33,42,51,54,55,56,57,58,59,61,62,69,70,71,78,79,80},
  { 7,16,25,34,43,52,54,55,56,57,58,59,60,62,69,70,71,78,79,80},
  { 8,17,26,35,44,53,54,55,56,57,58,59,60,61,69,70,71,78,79,80},
  { 0, 9,18,27,36,45,54,55,56,64,65,66,67,68,69,70,71,72,73,74},
  { 1,10,19,28,37,46,54,55,56,63,65,66,67,68,69,70,71,72,73,74},
  { 2,11,20,29,38,47,54,55,56,63,64,66,67,68,69,70,71,72,73,74},
  { 3,12,21,30,39,48,57,58,59,63,64,65,67,68,69,70,71,75,76,77},
  { 4,13,22,31,40,49,57,58,59,63,64,65,66,68,69,70,71,75,76,77},
  { 5,14,23,32,41,50,57,58,59,63,64,65,66,67,69,70,71,75,76,77},
  { 6,15,24,33,42,51,60,61,62,63,64,65,66,67,68,70,71,78,79,80},
  { 7,16,25,34,43,52,60,61,62,63,64,65,66,67,68,69,71,78,79,80},
  { 8,17,26,35,44,53,60,61,62,63,64,65,66,67,68,69,70,78,79,80},
  { 0, 9,18,27,36,45,54,55,56,63,64,65,73,74,75,76,77,78,79,80},
  { 1,10,19,28,37,46,54,55,56,63,64,65,72,74,75,76,77,78,79,80},
  { 2,11,20,29,38,47,54,55,56,63,64,65,72,73,75,76,77,78,79,80},
  { 3,12,21,30,39,48,57,58,59,66,67,68,72,73,74,76,77,78,79,80},
  { 4,13,22,31,40,49,57,58,59,66,67,68,72,73,74,75,77,78,79,80},
  { 5,14,23,32,41,50,57,58,59,66,67,68,72,73,74,75,76,78,79,80},
  { 6,15,24,33,42,51,60,61,62,69,70,71,72,73,74,75,76,77,79,80},
  { 7,16,25,34,43,52,60,61,62,69,70,71,72,73,74,75,76,77,78,80},
  { 8,17,26,35,44,53,60,61,62,69,70,71,72,73,74,75,76,77,78,79}},
           l[27][9] = {      // Empty 9 Cell positions for Hidden Singles Row, Column and Box wise
  { 0, 1, 2, 3, 4, 5, 6, 7, 8}, { 9,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},
  { 0, 9,18,27,36,45,54,63,72}, { 1,10,19,28,37,46,55,64,73}, { 2,11,20,29,38,47,56,65,74},
  { 3,12,21,30,39,48,57,66,75}, { 4,13,22,31,40,49,58,67,76}, { 5,14,23,32,41,50,59,68,77},
  { 6,15,24,33,42,51,60,69,78}, { 7,16,25,34,43,52,61,70,79}, { 8,17,26,35,44,53,62,71,80},
  { 0, 1, 2, 9,10,11,18,19,20}, { 3, 4, 5,12,13,14,21,22,23}, { 6, 7, 8,15,16,17,24,25,26},
  {27,28,29,36,37,38,45,46,47}, {30,31,32,39,40,41,48,49,50}, {33,34,35,42,43,44,51,52,53},
  {54,55,56,63,64,65,72,73,74}, {57,58,59,66,67,68,75,76,77}, {60,61,62,69,70,71,78,79,80}},
           j[54][15] = {     // Empty 3 Cell positions Box-Row/Column wise and affected empty 6 Box + 6 Row/Column Cell positions for Intersection Removal
  { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20},
  { 3, 4, 5, 0, 1, 2, 6, 7, 8,12,13,14,21,22,23},
  { 6, 7, 8, 0, 1, 2, 3, 4, 5,15,16,17,24,25,26},
  { 9,10,11,12,13,14,15,16,17, 0, 1, 2,18,19,20},
  {12,13,14, 9,10,11,15,16,17, 3, 4, 5,21,22,23},
  {15,16,17, 9,10,11,12,13,14, 6, 7, 8,24,25,26},
  {18,19,20,21,22,23,24,25,26, 0, 1, 2, 9,10,11},
  {21,22,23,18,19,20,24,25,26, 3, 4, 5,12,13,14},
  {24,25,26,18,19,20,21,22,23, 6, 7, 8,15,16,17},
  {27,28,29,30,31,32,33,34,35,36,37,38,45,46,47},
  {30,31,32,27,28,29,33,34,35,39,40,41,48,49,50},
  {33,34,35,27,28,29,30,31,32,42,43,44,51,52,53},
  {36,37,38,39,40,41,42,43,44,27,28,29,45,46,47},
  {39,40,41,36,37,38,42,43,44,30,31,32,48,49,50},
  {42,43,44,36,37,38,39,40,41,33,34,35,51,52,53},
  {45,46,47,48,49,50,51,52,53,27,28,29,36,37,38},
  {48,49,50,45,46,47,51,52,53,30,31,32,39,40,41},
  {51,52,53,45,46,47,48,49,50,33,34,35,42,43,44},
  {54,55,56,57,58,59,60,61,62,63,64,65,72,73,74},
  {57,58,59,54,55,56,60,61,62,66,67,68,75,76,77},
  {60,61,62,54,55,56,57,58,59,69,70,71,78,79,80},
  {63,64,65,66,67,68,69,70,71,54,55,56,72,73,74},
  {66,67,68,63,64,65,69,70,71,57,58,59,75,76,77},
  {69,70,71,63,64,65,66,67,68,60,61,62,78,79,80},
  {72,73,74,75,76,77,78,79,80,54,55,56,63,64,65},
  {75,76,77,72,73,74,78,79,80,57,58,59,66,67,68},
  {78,79,80,72,73,74,75,76,77,60,61,62,69,70,71},
  { 0, 9,18,27,36,45,54,63,72, 1, 2,10,11,19,20},
  {27,36,45, 0, 9,18,54,63,72,28,29,37,38,46,47},
  {54,63,72, 0, 9,18,27,36,45,55,56,64,65,73,74},
  { 1,10,19,28,37,46,55,64,73, 0, 2, 9,11,18,20},
  {28,37,46, 1,10,19,55,64,73,27,29,36,38,45,47},
  {55,64,73, 1,10,19,28,37,46,54,56,63,65,72,74},
  { 2,11,20,29,38,47,56,65,74, 0, 1, 9,10,18,19},
  {29,38,47, 2,11,20,56,65,74,27,28,36,37,45,46},
  {56,65,74, 2,11,20,29,38,47,54,55,63,64,72,73},
  { 3,12,21,30,39,48,57,66,75, 4, 5,13,14,22,23},
  {30,39,48, 3,12,21,57,66,75,31,32,40,41,49,50},
  {57,66,75, 3,12,21,30,39,48,58,59,67,68,76,77},
  { 4,13,22,31,40,49,58,67,76, 3, 5,12,14,21,23},
  {31,40,49, 4,13,22,58,67,76,30,32,39,41,48,50},
  {58,67,76, 4,13,22,31,40,49,57,59,66,68,75,77},
  { 5,14,23,32,41,50,59,68,77, 3, 4,12,13,21,22},
  {32,41,50, 5,14,23,59,68,77,30,31,39,40,48,49},
  {59,68,77, 5,14,23,32,41,50,57,58,66,67,75,76},
  { 6,15,24,33,42,51,60,69,78, 7, 8,16,17,25,26},
  {33,42,51, 6,15,24,60,69,78,34,35,43,44,52,53},
  {60,69,78, 6,15,24,33,42,51,61,62,70,71,79,80},
  { 7,16,25,34,43,52,61,70,79, 6, 8,15,17,24,26},
  {34,43,52, 7,16,25,61,70,79,33,35,42,44,51,53},
  {61,70,79, 7,16,25,34,43,52,60,62,69,71,78,80},
  { 8,17,26,35,44,53,62,71,80, 6, 7,15,16,24,25},
  {35,44,53, 8,17,26,62,71,80,33,34,42,43,51,52},
  {62,71,80, 8,17,26,35,44,53,60,61,69,70,78,79}};

int solve(int p)
{
  int a,
      x,
      y,
      z = b[0];

  for(a = p; a < q; ++a)
    if(z > b[g[r[a][0]]])    // Check least Candidates empty Cell position wise
      if((z = b[g[r[x = a][0]]]) < 10)
        goto NHSCF;          // Found Naked Single Candidate
  for(y = 0; y < 27; ++y)
    for(a = 0; a < 9; ++a)
      if(((g[l[y][0]] >> a) & 1) + ((g[l[y][1]] >> a) & 1) +
        ((g[l[y][2]] >> a) & 1) + ((g[l[y][3]] >> a) & 1) +
        ((g[l[y][4]] >> a) & 1) + ((g[l[y][5]] >> a) & 1) +
        ((g[l[y][6]] >> a) & 1) + ((g[l[y][7]] >> a) & 1) +
        ((g[l[y][8]] >> a) & 1) == 1)
      {                      // Check Hidden Single Candidate
        x = (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;
        ++h;
        z = a + 1;
        a = l[y][b[x] - 1];
        x = r[a][1];
        goto NHSCF;
      }
  for(y = 0; y < 54; ++y)
    for(a = 0; a < 9; ++a)
      if((g[j[y][0]] >> a) & 1 || (g[j[y][1]] >> a) & 1 || (g[j[y][2]] >> a) & 1)
      {                      // Check Candidate within empty 3 Cell positions either Box-Row or Box-Column wise
        if((g[j[y][3]] >> a) & 1 || (g[j[y][4]] >> a) & 1 ||
          (g[j[y][5]] >> a) & 1 || (g[j[y][6]] >> a) & 1 ||
          (g[j[y][7]] >> a) & 1 || (g[j[y][8]] >> a) & 1)
        {                    // Check Candidate within affected empty 6 Cell positions either Row or Column wise
          if(!((g[j[y][9]] >> a) & 1 || (g[j[y][10]] >> a) & 1 ||
            (g[j[y][11]] >> a) & 1 || (g[j[y][12]] >> a) & 1 ||
            (g[j[y][13]] >> a) & 1 || (g[j[y][14]] >> a) & 1))
          {                  // Check Candidate within affected empty 6 Cells positions Box wise
            int k = (g[j[y][3]] >> a) & 1 | ((g[j[y][4]] >> a) & 1) << 1 |
              ((g[j[y][5]] >> a) & 1) << 2 | ((g[j[y][6]] >> a) & 1) << 3 |
              ((g[j[y][7]] >> a) & 1) << 4 | ((g[j[y][8]] >> a) & 1) << 5;
                             // Backup Candidate within affected empty 6 Cell positions either Row or Column wise
            g[j[y][3]] &= ~(1 << a);
            g[j[y][4]] &= ~(1 << a);
            g[j[y][5]] &= ~(1 << a);
            g[j[y][6]] &= ~(1 << a);
            g[j[y][7]] &= ~(1 << a);
            g[j[y][8]] &= ~(1 << a);
            if(solve(p))
              return 1;
            g[j[y][3]] ^= (-(k & 1) ^ g[j[y][3]]) & (1 << a);
            g[j[y][4]] ^= (-((k >> 1) & 1) ^ g[j[y][4]]) & (1 << a);
            g[j[y][5]] ^= (-((k >> 2) & 1) ^ g[j[y][5]]) & (1 << a);
            g[j[y][6]] ^= (-((k >> 3) & 1) ^ g[j[y][6]]) & (1 << a);
            g[j[y][7]] ^= (-((k >> 4) & 1) ^ g[j[y][7]]) & (1 << a);
            g[j[y][8]] ^= (-((k >> 5) & 1) ^ g[j[y][8]]) & (1 << a);
          }                  // Restore Candidate within affected empty 6 Cell positions either Row or Column wise
        }
        else
          if((g[j[y][9]] >> a) & 1 || (g[j[y][10]] >> a) & 1 ||
            (g[j[y][11]] >> a) & 1 || (g[j[y][12]] >> a) & 1 ||
            (g[j[y][13]] >> a) & 1 || (g[j[y][14]] >> a) & 1)
          {                  // Check Candidate within affected empty 6 Cell positions Box wise
            int k = (g[j[y][9]] >> a) & 1 | ((g[j[y][10]] >> a) & 1) << 1 |
              ((g[j[y][11]] >> a) & 1) << 2 | ((g[j[y][12]] >> a) & 1) << 3 |
              ((g[j[y][13]] >> a) & 1) << 4 | ((g[j[y][14]] >> a) & 1) << 5;
                             // Backup Candidate within affected empty 6 Cell positions Box wise
            g[j[y][9]] &= ~(1 << a);
            g[j[y][10]] &= ~(1 << a);
            g[j[y][11]] &= ~(1 << a);
            g[j[y][12]] &= ~(1 << a);
            g[j[y][13]] &= ~(1 << a);
            g[j[y][14]] &= ~(1 << a);
            if(solve(p))
              return 1;
            g[j[y][9]] ^= (-(k & 1) ^ g[j[y][9]]) & (1 << a);
            g[j[y][10]] ^= (-((k >> 1) & 1) ^ g[j[y][10]]) & (1 << a);
            g[j[y][11]] ^= (-((k >> 2) & 1) ^ g[j[y][11]]) & (1 << a);
            g[j[y][12]] ^= (-((k >> 3) & 1) ^ g[j[y][12]]) & (1 << a);
            g[j[y][13]] ^= (-((k >> 4) & 1) ^ g[j[y][13]]) & (1 << a);
            g[j[y][14]] ^= (-((k >> 5) & 1) ^ g[j[y][14]]) & (1 << a);
          }                  // Restore Candidate within affected empty 6 Cell positions Box wise
      }
NHSCF:
  if(x > p)                  // Check define Cell position for sorting and eliminating
  {
    a = r[p][0];
    r[p][0] = r[x][0];
    r[x][0] = a;
    r[r[p][0]][1] = p;
    r[a][1] = x;
  }
  for(; s[r[p][0]] = z % 10; ++n, z /= 10)
  {
    int k = g[r[p][0]] << 20;// Backup define Cell position Candidates wise
    for(g[r[p][0]] = 0, a = 0; a < 20; ++a)
      if(g[w[r[p][0]][a]] & (1 << (s[r[p][0]] - 1)))
      {                      // Backup Candidate within affected empty 20 Cell positions wise
        if(b[g[w[r[p][0]][a]]] < 10)
          break;             // Check one candidate assigned
        k |= 1 << a;
        g[w[r[p][0]][a]] &= ~(1 << (s[r[p][0]] - 1));
      }
    if(a > 19 && (p + 1 >= q || solve(p + 1)))
      return 1;              // If either all empty Cell positions defined or recursive solve for next empty Cell position
    g[r[p][0]] = k >> 20;    // Restore Candidates define Cell position wise
    while(a > 0)             // Restore Candidate within affected empty 20 Cell positions wise
      g[w[r[p][0]][--a]] ^= (-((k >> a) & 1) ^ g[w[r[p][0]][a]]) & (1 << (s[r[p][0]] - 1));
  }
  return 0;
}

int check(int p, int q)
{
  for(int a = 0; a < 20; ++a)
    if(s[w[p][a]] == q)      // Check duplicate Candidate within affected empty 20 Cell positions wise
      return 0;
  return 1;
}

int invalid(void)
{
  for(int p = 0; p < 81; ++p)
    if(!s[p])                // Found empty Cell position
    {
       for(int a = 0; a < 9; ++a)
        g[p] ^= (-check(p, a + 1) ^ g[p]) & (1 << a);
                             // Check constraint and assign Candidate for empty Cell positions
      if(!g[p])              // Check no Candidate assigned
        return 1;
      r[q][0] = p;           // Assign empty Cell position for sorting and eliminating
      r[p][1] = q++;
    }
    else
      if(!check(p, s[p]))    // Check pre define Cell positions constraint
        return 1;
  return 0;
}

int main(void)
{
  int a = 0,
      m,
      i = 0,
      t = 0,
      u = 0,
      v = 0;

  float c,
        d = 0,
        e = 0,
        f = 0;

  FILE *o = fopen("sudoku.txt", "r");

  if(o == NULL)
    printf("Unable to open sudoku.txt file for read !!\n");
  else
    do
      if((m = fgetc(o)) != 10 && m != EOF && a < 81)
        s[a++] = m >= '1' && m <= '9' ? m - '0' : 0;
                             // Assign digit to pre define Cell position
      else
        if(m == 10 || m == EOF)
        {
          while(a < 81)
            s[a++] = 0;      // Clear remaining empty Cell positions
          n = h = q = 0;
          c = clock();
          if(invalid())
          {
            c = (clock() - c) / CLOCKS_PER_SEC * 1000;
            d += c;
            printf("%ld) Error: Invalid Sudoku! # I%ld", ++t, ++i);
          }
          else
            if(solve(0))
            {
              c = (clock() - c) / CLOCKS_PER_SEC * 1000;
              e += c;
              printf("%ld) ", ++t);
              for(a = 0; a < 81; ++a)
                printf("%c", s[a]);
              printf(" # S%ld", ++v);
            }
            else
            {
              c = (clock() - c) / CLOCKS_PER_SEC * 1000;
              f += c;
              printf("%ld) Error: Unsolvable Sudoku! # U%ld", ++t, ++u);
            }
          printf(" # N%ld # H%ld # %f\n", n, h, c);
          a = 0;
        }
    while(m != EOF);
  printf("=======================================\n");
  printf("Total Sudoku puzzle read   : %ld\n", t);
  printf("Total time for all puzzles : %f\n", d + e + f);
  printf("Average time per puzzle    : %f\n", t ? (d + e + f) / t : 0);
  printf("Number of invalid puzzles  : %ld\n", i);
  printf("Time for invalid puzzles   : %f\n", d);
  printf("Average time per invalid   : %f\n", i ? d / i : 0);
  printf("Number of solved puzzles   : %ld\n", v);
  printf("Time for solved puzzles    : %f\n", e);
  printf("Average time per solved    : %f\n", v ? e / v : 0);
  printf("Number of unsolved puzzle  : %ld\n", u);
  printf("Time for unsolved puzzles  : %f\n", f);
  printf("Average time per unsolved  : %f\n", u ? f / u : 0);
  if(fclose(o) == EOF)
    printf("Unable to close sudoku.txt file !!");
}

Also, successfully removed time consuming sort searching loop by introducing sorted list and indexed list maintaning simultaneously.

Regards,
R. Jamil

[rjamil]

Hi all again,

While I am trying to convert modulus (%) and divide (/) operators in to Boolean in my Boolean Sudoku Solver, I stuck due inappropriate results. I need some help as whether I am doing wrong or missing something.

In solve function, I use a temporary variable 'z' for holding candidates of an empty cell for which recursively next move is checking. I changed all five statements containing variable 'z' as follows:

229) z = 0; // z = b[0]; holding larger initial value as naked candidates
232) if(b[z] > b[g[r[a][0]]]) // if(z > b[g[r[a][0]]]) searching smaller value than initial value as naked candidates
233) if(b[z = g[r[x = a][0]]] < 10) // if((z = b[g[r[x = a][0]]]) < 10) assigning smaller value in to initial value and check if it contain naked single candidate value
249) z = 1 << a; // z = a + 1; assigning hidden single candidate value
320) for(; s[r[p][0]] = b[z & -z]; ++n, z &= (z - 1)) // for(; s[r[p][0]] = z % 10; ++n, z /= 10) iterate each candidate by assigning in to empty cell one by one

I am unable to understand as to where I made any mistake.

Please help me in this regards.

Update 20150923:
Got it.
320) for(; (s[r[p][0]] = b[z & -z]) < b[0]; ++n, z &= (z - 1))
Problem solved.

R. Jamil
_____________________________________________________________________________________
It's always stressful to tell someone that they made a mistake.
The only way you can learn something from your mistakes is when somebody corrects them.
"Experience is the name everyone gives to their mistakes." ~ OSCAR WILDE, Lady Windermere's Fan
"A person who never made a mistake never tried anything new." ~ Albert Einstein

[rjamil]

Hi,

Find Bitwise Sudoku Solver made by me. Now Naked & Hidden singles, Tuples eliminations, Intersection Removals, Basic Fishes and Trial & Error with Backtracking methods and debugging information are included in it:

RJSolBit.cpp

Code: Select all

#include <stdio.h>
#include <time.h>

#ifndef RJ
//#define RJ                   // Uncheck for debugging
#endif

int q,                       // Number of unsolved Cell positions
    r[81],                   // Used for sorting and eliminating unsolved Cell positions
    s[81],                   // Sudoku solved 81 Cell positions Board wise
    g[81],                   // Bitwise Candidates unsolved 81 Cell positions Board wise
    n,                       // Number of guesses Board wise
    h;                       // Number of Hidden Singles Board wise

static int b[512] = {        // Bitwise Candidates
          0,        1,        2,       12,        3,       13,       23,      123,
          4,       14,       24,      124,       34,      134,      234,     1234,
          5,       15,       25,      125,       35,      135,      235,     1235,
         45,      145,      245,     1245,      345,     1345,     2345,    12345,
          6,       16,       26,      126,       36,      136,      236,     1236,
         46,      146,      246,     1246,      346,     1346,     2346,    12346,
         56,      156,      256,     1256,      356,     1356,     2356,    12356,
        456,     1456,     2456,    12456,     3456,    13456,    23456,   123456,
          7,       17,       27,      127,       37,      137,      237,     1237,
         47,      147,      247,     1247,      347,     1347,     2347,    12347,
         57,      157,      257,     1257,      357,     1357,     2357,    12357,
        457,     1457,     2457,    12457,     3457,    13457,    23457,   123457,
         67,      167,      267,     1267,      367,     1367,     2367,    12367,
        467,     1467,     2467,    12467,     3467,    13467,    23467,   123467,
        567,     1567,     2567,    12567,     3567,    13567,    23567,   123567,
       4567,    14567,    24567,   124567,    34567,   134567,   234567,  1234567,
          8,       18,       28,      128,       38,      138,      238,     1238,
         48,      148,      248,     1248,      348,     1348,     2348,    12348,
         58,      158,      258,     1258,      358,     1358,     2358,    12358,
        458,     1458,     2458,    12458,     3458,    13458,    23458,   123458,
         68,      168,      268,     1268,      368,     1368,     2368,    12368,
        468,     1468,     2468,    12468,     3468,    13468,    23468,   123468,
        568,     1568,     2568,    12568,     3568,    13568,    23568,   123568,
       4568,    14568,    24568,   124568,    34568,   134568,   234568,  1234568,
         78,      178,      278,     1278,      378,     1378,     2378,    12378,
        478,     1478,     2478,    12478,     3478,    13478,    23478,   123478,
        578,     1578,     2578,    12578,     3578,    13578,    23578,   123578,
       4578,    14578,    24578,   124578,    34578,   134578,   234578,  1234578,
        378,     1678,     2678,    12678,     3678,    13678,    23678,   123678,
       4678,    14678,    24678,   124678,    34678,   134678,   234678,  1234678,
       5678,    15678,    25678,   125678,    35678,   135678,   235678,  1235678,
      45678,   145678,   245678,  1245678,   345678,  1345678,  2345678, 12345678,
          9,       19,       29,      129,       39,      139,      239,     1239,
         49,      149,      249,     1249,      349,     1349,     2349,    12349,
         59,      159,      259,     1259,      359,     1359,     2359,    12359,
        459,     1459,     2459,    12459,     3459,    13459,    23459,   123459,
         69,      169,      269,     1269,      369,     1369,     2369,    12369,
        469,     1469,     2469,    12469,     3469,    13469,    23469,   123469,
        569,     1569,     2569,    12569,     3569,    13569,    23569,   123569,
       4569,    14569,    24569,   124569,    34569,   134569,   234569,  1234569,
         79,      179,      279,     1279,      379,     1379,     2379,    12379,
        479,     1479,     2479,    12479,     3479,    13479,    23479,   123479,
        579,     1579,     2579,    12579,     3579,    13579,    23579,   123579,
       4579,    14579,    24579,   124579,    34579,   134579,   234579,  1234579,
        679,     1679,     2679,    12679,     3679,    13679,    23679,   123679,
       4679,    14679,    24679,   124679,    34679,   134679,   234679,  1234679,
       5679,    15679,    25679,   125679,    35679,   135679,   235679,  1235679,
      45679,   145679,   245679,  1245679,   345679,  1345679,  2345679, 12345679,
         89,      189,      289,     1289,      389,     1389,     2389,    12389,
        489,     1489,     2489,    12489,     3489,    13489,    23489,   123489,
        589,     1589,     2589,    12589,     3589,    13589,    23589,   123589,
       4589,    14589,    24589,   124589,    34589,   134589,   234589,  1234589,
        689,     1689,     2689,    12689,     3689,    13689,    23689,   123689,
       4689,    14689,    24689,   124689,    34689,   134689,   234689,  1234689,
       5689,    15689,    25689,   125689,    35689,   135689,   235689,  1235689,
      45689,   145689,   245689,  1245689,   345689,  1345689,  2345689, 12345689,
        789,     1789,     2789,    12789,     3789,    13789,    23789,   123789,
       4789,    14789,    24789,   124789,    34789,   134789,   234789,  1234789,
       5789,    15789,    25789,   125789,    35789,   135789,   235789,  1235789,
      45789,   145789,   245789,  1245789,   345789,  1345789,  2345789, 12345789,
       6789,    16789,    26789,   126789,    36789,   136789,   236789,  1236789,
      46789,   146789,   246789,  1246789,   346789,  1346789,  2346789, 12346789,
      56789,   156789,   256789,  1256789,   356789,  1356789,  2356789, 12356789,
     456789,  1456789,  2456789, 12456789,  3456789, 13456789, 23456789,123456789},
           B[513] = {        // Bit Count
   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
   4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
   5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9,10},
           w[81][20] = {     // Affected unsolved 20 Cell positions
  { 3, 4, 5, 6, 7, 8, 1, 2,10,11,19,20, 9,18,27,36,45,54,63,72},
  { 3, 4, 5, 6, 7, 8, 0, 2, 9,11,18,20,10,19,28,37,46,55,64,73},
  { 3, 4, 5, 6, 7, 8, 0, 1, 9,10,18,19,11,20,29,38,47,56,65,74},
  { 0, 1, 2, 6, 7, 8, 4, 5,13,14,22,23,12,21,30,39,48,57,66,75},
  { 0, 1, 2, 6, 7, 8, 3, 5,12,14,21,23,13,22,31,40,49,58,67,76},
  { 0, 1, 2, 6, 7, 8, 3, 4,12,13,21,22,14,23,32,41,50,59,68,77},
  { 0, 1, 2, 3, 4, 5, 7, 8,16,17,25,26,15,24,33,42,51,60,69,78},
  { 0, 1, 2, 3, 4, 5, 6, 8,15,17,24,26,16,25,34,43,52,61,70,79},
  { 0, 1, 2, 3, 4, 5, 6, 7,15,16,24,25,17,26,35,44,53,62,71,80},
  {12,13,14,15,16,17,10,11, 1, 2,19,20, 0,18,27,36,45,54,63,72},
  {12,13,14,15,16,17, 9,11, 0, 2,18,20, 1,19,28,37,46,55,64,73},
  {12,13,14,15,16,17, 9,10, 0, 1,18,19, 2,20,29,38,47,56,65,74},
  { 9,10,11,15,16,17,13,14, 4, 5,22,23, 3,21,30,39,48,57,66,75},
  { 9,10,11,15,16,17,12,14, 3, 5,21,23, 4,22,31,40,49,58,67,76},
  { 9,10,11,15,16,17,12,13, 3, 4,21,22, 5,23,32,41,50,59,68,77},
  { 9,10,11,12,13,14,16,17, 7, 8,25,26, 6,24,33,42,51,60,69,78},
  { 9,10,11,12,13,14,15,17, 6, 8,24,26, 7,25,34,43,52,61,70,79},
  { 9,10,11,12,13,14,15,16, 6, 7,24,25, 8,26,35,44,53,62,71,80},
  {21,22,23,24,25,26,19,20, 1, 2,10,11, 0, 9,27,36,45,54,63,72},
  {21,22,23,24,25,26,18,20, 0, 2, 9,11, 1,10,28,37,46,55,64,73},
  {21,22,23,24,25,26,18,19, 0, 1, 9,10, 2,11,29,38,47,56,65,74},
  {18,19,20,24,25,26,22,23, 4, 5,13,14, 3,12,30,39,48,57,66,75},
  {18,19,20,24,25,26,21,23, 3, 5,12,14, 4,13,31,40,49,58,67,76},
  {18,19,20,24,25,26,21,22, 3, 4,12,13, 5,14,32,41,50,59,68,77},
  {18,19,20,21,22,23,25,26, 7, 8,16,17, 6,15,33,42,51,60,69,78},
  {18,19,20,21,22,23,24,26, 6, 8,15,17, 7,16,34,43,52,61,70,79},
  {18,19,20,21,22,23,24,25, 6, 7,15,16, 8,17,35,44,53,62,71,80},
  {30,31,32,33,34,35,28,29,37,38,46,47,36,45, 0, 9,18,54,63,72},
  {30,31,32,33,34,35,27,29,36,38,45,47,37,46, 1,10,19,55,64,73},
  {30,31,32,33,34,35,27,28,36,37,45,46,38,47, 2,11,20,56,65,74},
  {27,28,29,33,34,35,31,32,40,41,49,50,39,48, 3,12,21,57,66,75},
  {27,28,29,33,34,35,30,32,39,41,48,50,40,49, 4,13,22,58,67,76},
  {27,28,29,33,34,35,30,31,39,40,48,49,41,50, 5,14,23,59,68,77},
  {27,28,29,30,31,32,34,35,43,44,52,53,42,51, 6,15,24,60,69,78},
  {27,28,29,30,31,32,33,35,42,44,51,53,43,52, 7,16,25,61,70,79},
  {27,28,29,30,31,32,33,34,42,43,51,52,44,53, 8,17,26,62,71,80},
  {39,40,41,42,43,44,37,38,28,29,46,47,27,45, 0, 9,18,54,63,72},
  {39,40,41,42,43,44,36,38,27,29,45,47,28,46, 1,10,19,55,64,73},
  {39,40,41,42,43,44,36,37,27,28,45,46,29,47, 2,11,20,56,65,74},
  {36,37,38,42,43,44,40,41,31,32,49,50,30,48, 3,12,21,57,66,75},
  {36,37,38,42,43,44,39,41,30,32,48,50,31,49, 4,13,22,58,67,76},
  {36,37,38,42,43,44,39,40,30,31,48,49,32,50, 5,14,23,59,68,77},
  {36,37,38,39,40,41,43,44,34,35,52,53,33,51, 6,15,24,60,69,78},
  {36,37,38,39,40,41,42,44,33,35,51,53,34,52, 7,16,25,61,70,79},
  {36,37,38,39,40,41,42,43,33,34,51,52,35,53, 8,17,26,62,71,80},
  {48,49,50,51,52,53,46,47,28,29,37,38,27,36, 0, 9,18,54,63,72},
  {48,49,50,51,52,53,45,47,27,29,36,38,28,37, 1,10,19,55,64,73},
  {48,49,50,51,52,53,45,46,27,28,36,37,29,38, 2,11,20,56,65,74},
  {45,46,47,51,52,53,49,50,31,32,40,41,30,39, 3,12,21,57,66,75},
  {45,46,47,51,52,53,48,50,30,32,39,41,31,40, 4,13,22,58,67,76},
  {45,46,47,51,52,53,48,49,30,31,39,40,32,41, 5,14,23,59,68,77},
  {45,46,47,48,49,50,52,53,34,35,43,44,33,42, 6,15,24,60,69,78},
  {45,46,47,48,49,50,51,53,33,35,42,44,34,43, 7,16,25,61,70,79},
  {45,46,47,48,49,50,51,52,33,34,42,43,35,44, 8,17,26,62,71,80},
  {57,58,59,60,61,62,55,56,64,65,73,74,63,72, 0, 9,18,27,36,45},
  {57,58,59,60,61,62,54,56,63,65,72,74,64,73, 1,10,19,28,37,46},
  {57,58,59,60,61,62,54,55,63,64,72,73,65,74, 2,11,20,29,38,47},
  {54,55,56,60,61,62,58,59,67,68,76,77,66,75, 3,12,21,30,39,48},
  {54,55,56,60,61,62,57,59,66,68,75,77,67,76, 4,13,22,31,40,49},
  {54,55,56,60,61,62,57,58,66,67,75,76,68,77, 5,14,23,32,41,50},
  {54,55,56,57,58,59,61,62,70,71,79,80,69,78, 6,15,24,33,42,51},
  {54,55,56,57,58,59,60,62,69,71,78,80,70,79, 7,16,25,34,43,52},
  {54,55,56,57,58,59,60,61,69,70,78,79,71,80, 8,17,26,35,44,53},
  {66,67,68,69,70,71,64,65,55,56,73,74,54,72, 0, 9,18,27,36,45},
  {66,67,68,69,70,71,63,65,54,56,72,74,55,73, 1,10,19,28,37,46},
  {66,67,68,69,70,71,63,64,54,55,72,73,56,74, 2,11,20,29,38,47},
  {63,64,65,69,70,71,67,68,58,59,76,77,57,75, 3,12,21,30,39,48},
  {63,64,65,69,70,71,66,68,57,59,75,77,58,76, 4,13,22,31,40,49},
  {63,64,65,69,70,71,66,67,57,58,75,76,59,77, 5,14,23,32,41,50},
  {63,64,65,66,67,68,70,71,61,62,79,80,60,78, 6,15,24,33,42,51},
  {63,64,65,66,67,68,69,71,60,62,78,80,61,79, 7,16,25,34,43,52},
  {63,64,65,66,67,68,69,70,60,61,78,79,62,80, 8,17,26,35,44,53},
  {75,76,77,78,79,80,73,74,55,56,64,65,54,63, 0, 9,18,27,36,45},
  {75,76,77,78,79,80,72,74,54,56,63,65,55,64, 1,10,19,28,37,46},
  {75,76,77,78,79,80,72,73,54,55,63,64,56,65, 2,11,20,29,38,47},
  {72,73,74,78,79,80,76,77,58,59,67,68,57,66, 3,12,21,30,39,48},
  {72,73,74,78,79,80,75,77,57,59,66,68,58,67, 4,13,22,31,40,49},
  {72,73,74,78,79,80,75,76,57,58,66,67,59,68, 5,14,23,32,41,50},
  {72,73,74,75,76,77,79,80,61,62,70,71,60,69, 6,15,24,33,42,51},
  {72,73,74,75,76,77,78,80,60,62,69,71,61,70, 7,16,25,34,43,52},
  {72,73,74,75,76,77,78,79,60,61,69,70,62,71, 8,17,26,35,44,53}},
           l[27][9] = {      // Unit Cell positions for Naked/Hidden tuples
  { 0, 1, 2, 3, 4, 5, 6, 7, 8}, { 9,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},
  { 0, 9,18,27,36,45,54,63,72}, { 1,10,19,28,37,46,55,64,73}, { 2,11,20,29,38,47,56,65,74},
  { 3,12,21,30,39,48,57,66,75}, { 4,13,22,31,40,49,58,67,76}, { 5,14,23,32,41,50,59,68,77},
  { 6,15,24,33,42,51,60,69,78}, { 7,16,25,34,43,52,61,70,79}, { 8,17,26,35,44,53,62,71,80},
  { 0, 1, 2, 9,10,11,18,19,20}, { 3, 4, 5,12,13,14,21,22,23}, { 6, 7, 8,15,16,17,24,25,26},
  {27,28,29,36,37,38,45,46,47}, {30,31,32,39,40,41,48,49,50}, {33,34,35,42,43,44,51,52,53},
  {54,55,56,63,64,65,72,73,74}, {57,58,59,66,67,68,75,76,77}, {60,61,62,69,70,71,78,79,80}},
           T[246][9] = {     // 36 pairs/84 triplets/126 quads Cell positions first then Unit other Cell positions
  { 0, 1, 2, 3, 4, 5, 6, 7, 8}, { 0, 2, 1, 3, 4, 5, 6, 7, 8}, { 0, 3, 1, 2, 4, 5, 6, 7, 8},
  { 0, 4, 1, 2, 3, 5, 6, 7, 8}, { 0, 5, 1, 2, 3, 4, 6, 7, 8}, { 0, 6, 1, 2, 3, 4, 5, 7, 8},
  { 0, 7, 1, 2, 3, 4, 5, 6, 8}, { 0, 8, 1, 2, 3, 4, 5, 6, 7}, { 1, 2, 0, 3, 4, 5, 6, 7, 8},
  { 1, 3, 0, 2, 4, 5, 6, 7, 8}, { 1, 4, 0, 2, 3, 5, 6, 7, 8}, { 1, 5, 0, 2, 3, 4, 6, 7, 8},
  { 1, 6, 0, 2, 3, 4, 5, 7, 8}, { 1, 7, 0, 2, 3, 4, 5, 6, 8}, { 1, 8, 0, 2, 3, 4, 5, 6, 7},
  { 2, 3, 0, 1, 4, 5, 6, 7, 8}, { 2, 4, 0, 1, 3, 5, 6, 7, 8}, { 2, 5, 0, 1, 3, 4, 6, 7, 8},
  { 2, 6, 0, 1, 3, 4, 5, 7, 8}, { 2, 7, 0, 1, 3, 4, 5, 6, 8}, { 2, 8, 0, 1, 3, 4, 5, 6, 7},
  { 3, 4, 0, 1, 2, 5, 6, 7, 8}, { 3, 5, 0, 1, 2, 4, 6, 7, 8}, { 3, 6, 0, 1, 2, 4, 5, 7, 8},
  { 3, 7, 0, 1, 2, 4, 5, 6, 8}, { 3, 8, 0, 1, 2, 4, 5, 6, 7}, { 4, 5, 0, 1, 2, 3, 6, 7, 8},
  { 4, 6, 0, 1, 2, 3, 5, 7, 8}, { 4, 7, 0, 1, 2, 3, 5, 6, 8}, { 4, 8, 0, 1, 2, 3, 5, 6, 7},
  { 5, 6, 0, 1, 2, 3, 4, 7, 8}, { 5, 7, 0, 1, 2, 3, 4, 6, 8}, { 5, 8, 0, 1, 2, 3, 4, 6, 7},
  { 6, 7, 0, 1, 2, 3, 4, 5, 8}, { 6, 8, 0, 1, 2, 3, 4, 5, 7}, { 7, 8, 0, 1, 2, 3, 4, 5, 6},
  { 0, 1, 2, 3, 4, 5, 6, 7, 8}, { 0, 1, 3, 2, 4, 5, 6, 7, 8}, { 0, 1, 4, 2, 3, 5, 6, 7, 8},
  { 0, 1, 5, 2, 3, 4, 6, 7, 8}, { 0, 1, 6, 2, 3, 4, 5, 7, 8}, { 0, 1, 7, 2, 3, 4, 5, 6, 8},
  { 0, 1, 8, 2, 3, 4, 5, 6, 7}, { 0, 2, 3, 1, 4, 5, 6, 7, 8}, { 0, 2, 4, 1, 3, 5, 6, 7, 8},
  { 0, 2, 5, 1, 3, 4, 6, 7, 8}, { 0, 2, 6, 1, 3, 4, 5, 7, 8}, { 0, 2, 7, 1, 3, 4, 5, 6, 8},
  { 0, 2, 8, 1, 3, 4, 5, 6, 7}, { 0, 3, 4, 1, 2, 5, 6, 7, 8}, { 0, 3, 5, 1, 2, 4, 6, 7, 8},
  { 0, 3, 6, 1, 2, 4, 5, 7, 8}, { 0, 3, 7, 1, 2, 4, 5, 6, 8}, { 0, 3, 8, 1, 2, 4, 5, 6, 7},
  { 0, 4, 5, 1, 2, 3, 6, 7, 8}, { 0, 4, 6, 1, 2, 3, 5, 7, 8}, { 0, 4, 7, 1, 2, 3, 5, 6, 8},
  { 0, 4, 8, 1, 2, 3, 5, 6, 7}, { 0, 5, 6, 1, 2, 3, 4, 7, 8}, { 0, 5, 7, 1, 2, 3, 4, 6, 8},
  { 0, 5, 8, 1, 2, 3, 4, 6, 7}, { 0, 6, 7, 1, 2, 3, 4, 5, 8}, { 0, 6, 8, 1, 2, 3, 4, 5, 7},
  { 0, 7, 8, 1, 2, 3, 4, 5, 6}, { 1, 2, 3, 0, 4, 5, 6, 7, 8}, { 1, 2, 4, 0, 3, 5, 6, 7, 8},
  { 1, 2, 5, 0, 3, 4, 6, 7, 8}, { 1, 2, 6, 0, 3, 4, 5, 7, 8}, { 1, 2, 7, 0, 3, 4, 5, 6, 8},
  { 1, 2, 8, 0, 3, 4, 5, 6, 7}, { 1, 3, 4, 0, 2, 5, 6, 7, 8}, { 1, 3, 5, 0, 2, 4, 6, 7, 8},
  { 1, 3, 6, 0, 2, 4, 5, 7, 8}, { 1, 3, 7, 0, 2, 4, 5, 6, 8}, { 1, 3, 8, 0, 2, 4, 5, 6, 7},
  { 1, 4, 5, 0, 2, 3, 6, 7, 8}, { 1, 4, 6, 0, 2, 3, 5, 7, 8}, { 1, 4, 7, 0, 2, 3, 5, 6, 8},
  { 1, 4, 8, 0, 2, 3, 5, 6, 7}, { 1, 5, 6, 0, 2, 3, 4, 7, 8}, { 1, 5, 7, 0, 2, 3, 4, 6, 8},
  { 1, 5, 8, 0, 2, 3, 4, 6, 7}, { 1, 6, 7, 0, 2, 3, 4, 5, 8}, { 1, 6, 8, 0, 2, 3, 4, 5, 7},
  { 1, 7, 8, 0, 2, 3, 4, 5, 6}, { 2, 3, 4, 0, 1, 5, 6, 7, 8}, { 2, 3, 5, 0, 1, 4, 6, 7, 8},
  { 2, 3, 6, 0, 1, 4, 5, 7, 8}, { 2, 3, 7, 0, 1, 4, 5, 6, 8}, { 2, 3, 8, 0, 1, 4, 5, 6, 7},
  { 2, 4, 5, 0, 1, 3, 6, 7, 8}, { 2, 4, 6, 0, 1, 3, 5, 7, 8}, { 2, 4, 7, 0, 1, 3, 5, 6, 8},
  { 2, 4, 8, 0, 1, 3, 5, 6, 7}, { 2, 5, 6, 0, 1, 3, 4, 7, 8}, { 2, 5, 7, 0, 1, 3, 4, 6, 8},
  { 2, 5, 8, 0, 1, 3, 4, 6, 7}, { 2, 6, 7, 0, 1, 3, 4, 5, 8}, { 2, 6, 8, 0, 1, 3, 4, 5, 7},
  { 2, 7, 8, 0, 1, 3, 4, 5, 6}, { 3, 4, 5, 0, 1, 2, 6, 7, 8}, { 3, 4, 6, 0, 1, 2, 5, 7, 8},
  { 3, 4, 7, 0, 1, 2, 5, 6, 8}, { 3, 4, 8, 0, 1, 2, 5, 6, 7}, { 3, 5, 6, 0, 1, 2, 4, 7, 8},
  { 3, 5, 7, 0, 1, 2, 4, 6, 8}, { 3, 5, 8, 0, 1, 2, 4, 6, 7}, { 3, 6, 7, 0, 1, 2, 4, 5, 8},
  { 3, 6, 8, 0, 1, 2, 4, 5, 7}, { 3, 7, 8, 0, 1, 2, 4, 5, 6}, { 4, 5, 6, 0, 1, 2, 3, 7, 8},
  { 4, 5, 7, 0, 1, 2, 3, 6, 8}, { 4, 5, 8, 0, 1, 2, 3, 6, 7}, { 4, 6, 7, 0, 1, 2, 3, 5, 8},
  { 4, 6, 8, 0, 1, 2, 3, 5, 7}, { 4, 7, 8, 0, 1, 2, 3, 5, 6}, { 5, 6, 7, 0, 1, 2, 3, 4, 8},
  { 5, 6, 8, 0, 1, 2, 3, 4, 7}, { 5, 7, 8, 0, 1, 2, 3, 4, 6}, { 6, 7, 8, 0, 1, 2, 3, 4, 5},
  { 0, 1, 2, 3, 4, 5, 6, 7, 8}, { 0, 1, 2, 4, 3, 5, 6, 7, 8}, { 0, 1, 2, 5, 3, 4, 6, 7, 8},
  { 0, 1, 2, 6, 3, 4, 5, 7, 8}, { 0, 1, 2, 7, 3, 4, 5, 6, 8}, { 0, 1, 2, 8, 3, 4, 5, 6, 7},
  { 0, 1, 3, 4, 2, 5, 6, 7, 8}, { 0, 1, 3, 5, 2, 4, 6, 7, 8}, { 0, 1, 3, 6, 2, 4, 5, 7, 8},
  { 0, 1, 3, 7, 2, 4, 5, 6, 8}, { 0, 1, 3, 8, 2, 4, 5, 6, 7}, { 0, 1, 4, 5, 2, 3, 6, 7, 8},
  { 0, 1, 4, 6, 2, 3, 5, 7, 8}, { 0, 1, 4, 7, 2, 3, 5, 6, 8}, { 0, 1, 4, 8, 2, 3, 5, 6, 7},
  { 0, 1, 5, 6, 2, 3, 4, 7, 8}, { 0, 1, 5, 7, 2, 3, 4, 6, 8}, { 0, 1, 5, 8, 2, 3, 4, 6, 7},
  { 0, 1, 6, 7, 2, 3, 4, 5, 8}, { 0, 1, 6, 8, 2, 3, 4, 5, 7}, { 0, 1, 7, 8, 2, 3, 4, 5, 6},
  { 0, 2, 3, 4, 1, 5, 6, 7, 8}, { 0, 2, 3, 5, 1, 4, 6, 7, 8}, { 0, 2, 3, 6, 1, 4, 5, 7, 8},
  { 0, 2, 3, 7, 1, 4, 5, 6, 8}, { 0, 2, 3, 8, 1, 4, 5, 6, 7}, { 0, 2, 4, 5, 1, 3, 6, 7, 8},
  { 0, 2, 4, 6, 1, 3, 5, 7, 8}, { 0, 2, 4, 7, 1, 3, 5, 6, 8}, { 0, 2, 4, 8, 1, 3, 5, 6, 7},
  { 0, 2, 5, 6, 1, 3, 4, 7, 8}, { 0, 2, 5, 7, 1, 3, 4, 6, 8}, { 0, 2, 5, 8, 1, 3, 4, 6, 7},
  { 0, 2, 6, 7, 1, 3, 4, 5, 8}, { 0, 2, 6, 8, 1, 3, 4, 5, 7}, { 0, 2, 7, 8, 1, 3, 4, 5, 6},
  { 0, 3, 4, 5, 1, 2, 6, 7, 8}, { 0, 3, 4, 6, 1, 2, 5, 7, 8}, { 0, 3, 4, 7, 1, 2, 5, 6, 8},
  { 0, 3, 4, 8, 1, 2, 5, 6, 7}, { 0, 3, 5, 6, 1, 2, 4, 7, 8}, { 0, 3, 5, 7, 1, 2, 4, 6, 8},
  { 0, 3, 5, 8, 1, 2, 4, 6, 7}, { 0, 3, 6, 7, 1, 2, 4, 5, 8}, { 0, 3, 6, 8, 1, 2, 4, 5, 7},
  { 0, 3, 7, 8, 1, 2, 4, 5, 6}, { 0, 4, 5, 6, 1, 2, 3, 7, 8}, { 0, 4, 5, 7, 1, 2, 3, 6, 8},
  { 0, 4, 5, 8, 1, 2, 3, 6, 7}, { 0, 4, 6, 7, 1, 2, 3, 5, 8}, { 0, 4, 6, 8, 1, 2, 3, 5, 7},
  { 0, 4, 7, 8, 1, 2, 3, 5, 6}, { 0, 5, 6, 7, 1, 2, 3, 4, 8}, { 0, 5, 6, 8, 1, 2, 3, 4, 7},
  { 0, 5, 7, 8, 1, 2, 3, 4, 6}, { 0, 6, 7, 8, 1, 2, 3, 4, 5}, { 1, 2, 3, 4, 0, 5, 6, 7, 8},
  { 1, 2, 3, 5, 0, 4, 6, 7, 8}, { 1, 2, 3, 6, 0, 4, 5, 7, 8}, { 1, 2, 3, 7, 0, 4, 5, 6, 8},
  { 1, 2, 3, 8, 0, 4, 5, 6, 7}, { 1, 2, 4, 5, 0, 3, 6, 7, 8}, { 1, 2, 4, 6, 0, 3, 5, 7, 8},
  { 1, 2, 4, 7, 0, 3, 5, 6, 8}, { 1, 2, 4, 8, 0, 3, 5, 6, 7}, { 1, 2, 5, 6, 0, 3, 4, 7, 8},
  { 1, 2, 5, 7, 0, 3, 4, 6, 8}, { 1, 2, 5, 8, 0, 3, 4, 6, 7}, { 1, 2, 6, 7, 0, 3, 4, 5, 8},
  { 1, 2, 6, 8, 0, 3, 4, 5, 7}, { 1, 2, 7, 8, 0, 3, 4, 5, 6}, { 1, 3, 4, 5, 0, 2, 6, 7, 8},
  { 1, 3, 4, 6, 0, 2, 5, 7, 8}, { 1, 3, 4, 7, 0, 2, 5, 6, 8}, { 1, 3, 4, 8, 0, 2, 5, 6, 7},
  { 1, 3, 5, 6, 0, 2, 4, 7, 8}, { 1, 3, 5, 7, 0, 2, 4, 6, 8}, { 1, 3, 5, 8, 0, 2, 4, 6, 7},
  { 1, 3, 6, 7, 0, 2, 4, 5, 8}, { 1, 3, 6, 8, 0, 2, 4, 5, 7}, { 1, 3, 7, 8, 0, 2, 4, 5, 6},
  { 1, 4, 5, 6, 0, 2, 3, 7, 8}, { 1, 4, 5, 7, 0, 2, 3, 6, 8}, { 1, 4, 5, 8, 0, 2, 3, 6, 7},
  { 1, 4, 6, 7, 0, 2, 3, 5, 8}, { 1, 4, 6, 8, 0, 2, 3, 5, 7}, { 1, 4, 7, 8, 0, 2, 3, 5, 6},
  { 1, 5, 6, 7, 0, 2, 3, 4, 8}, { 1, 5, 6, 8, 0, 2, 3, 4, 7}, { 1, 5, 7, 8, 0, 2, 3, 4, 6},
  { 1, 6, 7, 8, 0, 2, 3, 4, 5}, { 2, 3, 4, 5, 0, 1, 6, 7, 8}, { 2, 3, 4, 6, 0, 1, 5, 7, 8},
  { 2, 3, 4, 7, 0, 1, 5, 6, 8}, { 2, 3, 4, 8, 0, 1, 5, 6, 7}, { 2, 3, 5, 6, 0, 1, 4, 7, 8},
  { 2, 3, 5, 7, 0, 1, 4, 6, 8}, { 2, 3, 5, 8, 0, 1, 4, 6, 7}, { 2, 3, 6, 7, 0, 1, 4, 5, 8},
  { 2, 3, 6, 8, 0, 1, 4, 5, 7}, { 2, 3, 7, 8, 0, 1, 4, 5, 6}, { 2, 4, 5, 6, 0, 1, 3, 7, 8},
  { 2, 4, 5, 7, 0, 1, 3, 6, 8}, { 2, 4, 5, 8, 0, 1, 3, 6, 7}, { 2, 4, 6, 7, 0, 1, 3, 5, 8},
  { 2, 4, 6, 8, 0, 1, 3, 5, 7}, { 2, 4, 7, 8, 0, 1, 3, 5, 6}, { 2, 5, 6, 7, 0, 1, 3, 4, 8},
  { 2, 5, 6, 8, 0, 1, 3, 4, 7}, { 2, 5, 7, 8, 0, 1, 3, 4, 6}, { 2, 6, 7, 8, 0, 1, 3, 4, 5},
  { 3, 4, 5, 6, 0, 1, 2, 7, 8}, { 3, 4, 5, 7, 0, 1, 2, 6, 8}, { 3, 4, 5, 8, 0, 1, 2, 6, 7},
  { 3, 4, 6, 7, 0, 1, 2, 5, 8}, { 3, 4, 6, 8, 0, 1, 2, 5, 7}, { 3, 4, 7, 8, 0, 1, 2, 5, 6},
  { 3, 5, 6, 7, 0, 1, 2, 4, 8}, { 3, 5, 6, 8, 0, 1, 2, 4, 7}, { 3, 5, 7, 8, 0, 1, 2, 4, 6},
  { 3, 6, 7, 8, 0, 1, 2, 4, 5}, { 4, 5, 6, 7, 0, 1, 2, 3, 8}, { 4, 5, 6, 8, 0, 1, 2, 3, 7},
  { 4, 5, 7, 8, 0, 1, 2, 3, 6}, { 4, 6, 7, 8, 0, 1, 2, 3, 5}, { 5, 6, 7, 8, 0, 1, 2, 3, 4}},
           j[54][15] = {     // 3 Cell positions Box-Line wise and affected 6 Line + 6 Box Cell positions for Intersection Removals
  { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,18,19,20},
  { 3, 4, 5, 0, 1, 2, 6, 7, 8,12,13,14,21,22,23},
  { 6, 7, 8, 0, 1, 2, 3, 4, 5,15,16,17,24,25,26},
  { 9,10,11,12,13,14,15,16,17, 0, 1, 2,18,19,20},
  {12,13,14, 9,10,11,15,16,17, 3, 4, 5,21,22,23},
  {15,16,17, 9,10,11,12,13,14, 6, 7, 8,24,25,26},
  {18,19,20,21,22,23,24,25,26, 0, 1, 2, 9,10,11},
  {21,22,23,18,19,20,24,25,26, 3, 4, 5,12,13,14},
  {24,25,26,18,19,20,21,22,23, 6, 7, 8,15,16,17},
  {27,28,29,30,31,32,33,34,35,36,37,38,45,46,47},
  {30,31,32,27,28,29,33,34,35,39,40,41,48,49,50},
  {33,34,35,27,28,29,30,31,32,42,43,44,51,52,53},
  {36,37,38,39,40,41,42,43,44,27,28,29,45,46,47},
  {39,40,41,36,37,38,42,43,44,30,31,32,48,49,50},
  {42,43,44,36,37,38,39,40,41,33,34,35,51,52,53},
  {45,46,47,48,49,50,51,52,53,27,28,29,36,37,38},
  {48,49,50,45,46,47,51,52,53,30,31,32,39,40,41},
  {51,52,53,45,46,47,48,49,50,33,34,35,42,43,44},
  {54,55,56,57,58,59,60,61,62,63,64,65,72,73,74},
  {57,58,59,54,55,56,60,61,62,66,67,68,75,76,77},
  {60,61,62,54,55,56,57,58,59,69,70,71,78,79,80},
  {63,64,65,66,67,68,69,70,71,54,55,56,72,73,74},
  {66,67,68,63,64,65,69,70,71,57,58,59,75,76,77},
  {69,70,71,63,64,65,66,67,68,60,61,62,78,79,80},
  {72,73,74,75,76,77,78,79,80,54,55,56,63,64,65},
  {75,76,77,72,73,74,78,79,80,57,58,59,66,67,68},
  {78,79,80,72,73,74,75,76,77,60,61,62,69,70,71},
  { 0, 9,18,27,36,45,54,63,72, 1, 2,10,11,19,20},
  {27,36,45, 0, 9,18,54,63,72,28,29,37,38,46,47},
  {54,63,72, 0, 9,18,27,36,45,55,56,64,65,73,74},
  { 1,10,19,28,37,46,55,64,73, 0, 2, 9,11,18,20},
  {28,37,46, 1,10,19,55,64,73,27,29,36,38,45,47},
  {55,64,73, 1,10,19,28,37,46,54,56,63,65,72,74},
  { 2,11,20,29,38,47,56,65,74, 0, 1, 9,10,18,19},
  {29,38,47, 2,11,20,56,65,74,27,28,36,37,45,46},
  {56,65,74, 2,11,20,29,38,47,54,55,63,64,72,73},
  { 3,12,21,30,39,48,57,66,75, 4, 5,13,14,22,23},
  {30,39,48, 3,12,21,57,66,75,31,32,40,41,49,50},
  {57,66,75, 3,12,21,30,39,48,58,59,67,68,76,77},
  { 4,13,22,31,40,49,58,67,76, 3, 5,12,14,21,23},
  {31,40,49, 4,13,22,58,67,76,30,32,39,41,48,50},
  {58,67,76, 4,13,22,31,40,49,57,59,66,68,75,77},
  { 5,14,23,32,41,50,59,68,77, 3, 4,12,13,21,22},
  {32,41,50, 5,14,23,59,68,77,30,31,39,40,48,49},
  {59,68,77, 5,14,23,32,41,50,57,58,66,67,75,76},
  { 6,15,24,33,42,51,60,69,78, 7, 8,16,17,25,26},
  {33,42,51, 6,15,24,60,69,78,34,35,43,44,52,53},
  {60,69,78, 6,15,24,33,42,51,61,62,70,71,79,80},
  { 7,16,25,34,43,52,61,70,79, 6, 8,15,17,24,26},
  {34,43,52, 7,16,25,61,70,79,33,35,42,44,51,53},
  {61,70,79, 7,16,25,34,43,52,60,62,69,71,78,80},
  { 8,17,26,35,44,53,62,71,80, 6, 7,15,16,24,25},
  {35,44,53, 8,17,26,62,71,80,33,34,42,43,51,52},
  {62,71,80, 8,17,26,35,44,53,60,61,69,70,78,79}};

int solve (int p)
{
  int a,
      x,
      y = 0,
      z = 512;               // Assign greatest value for first time checking

  for (a = p; a < q; ++a)    // Search Naked/Hidden Single Candidate for each unsolved Cell position
  {
    if (B[z] > B[g[r[a]]])   // Check least Candidates for each unsolved Cell position
      if (B[z = g[r[x = a]]] == 1)
        goto NHSCF;          // Found Naked Single Candidate
    int K[3] = {             // Assign Hidden Candidates for each unsolved Cell position Unit wise
      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]][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]])),
      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[0]] == 1)        // Search Hidden Single Candidate Row wise
      z = K[0];              // Assign Hidden Single Candidate
    else
      if (B[K[1]] == 1)      // Search Hidden Single Candidate Column wise
        z = K[1];            // Assign Hidden Single Candidate
      else
        if (B[K[2]] == 1)    // Search Hidden Single Candidate Box wise
          z = K[2];          // Assign Hidden Single Candidate
        else
          continue;
    ++h;
    x = a;                   // Assign Hidden Single Cell position
#ifdef RJ
    y = 1;
#endif
    goto NHSCF;
  }
  for (; y < 27; ++y)        // Search Naked/Hidden Tuples for each Unit
  {
    int k[10] = {g[l[y][0]], g[l[y][1]], g[l[y][2]], g[l[y][3]],
      g[l[y][4]], g[l[y][5]], g[l[y][6]], g[l[y][7]], g[l[y][8]],
      (g[l[y][0]] ? 1 : 0) + (g[l[y][1]] ? 1 : 0) + (g[l[y][2]] ? 1 : 0) +
      (g[l[y][3]] ? 1 : 0) + (g[l[y][4]] ? 1 : 0) + (g[l[y][5]] ? 1 : 0) +
      (g[l[y][6]] ? 1 : 0) + (g[l[y][7]] ? 1 : 0) + (g[l[y][8]] ? 1 : 0)};
                             // Backup Unit Cell positions and Count unsolved Cell positions
    if (k[9] < 4)
      continue;              // Skip Unit for less than 4 unsolved Cell positions
    for (a = 0; a < 36; ++a) // Search Unit 36 pair Cell positions for Naked/Hidden pair
    {
      if (!k[T[a][0]] || !k[T[a][1]])
      {                      // Skip solved Cell positions
        if (!k[T[a][0]])
          a += 7 - T[a][0];
        continue;
      }
      int K[2] = {k[T[a][0]] | k[T[a][1]], k[T[a][2]] | k[T[a][3]] |
        k[T[a][4]] | k[T[a][5]] | k[T[a][6]] | k[T[a][7]] | k[T[a][8]]};

      if (B[K[0]] == 2)      // Search Naked pair Candidates in Unit pair Cell positions
      {
        if (K[0] & K[1])     // Search Naked pair Candidates in Unit other Cell positions
        {                    // Remove Naked pair Candidates from Unit other Cell positions
          g[l[y][T[a][2]]] &= ~K[0];
          g[l[y][T[a][3]]] &= ~K[0];
          g[l[y][T[a][4]]] &= ~K[0];
          g[l[y][T[a][5]]] &= ~K[0];
          g[l[y][T[a][6]]] &= ~K[0];
          g[l[y][T[a][7]]] &= ~K[0];
          g[l[y][T[a][8]]] &= ~K[0];
#ifdef RJ
          printf ("%d) Found Naked pair Candidates %d at Unit %d Cells %d %d\n",
            a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]]);
#endif
          if (solve (p))
            return 1;
#ifdef RJ
          printf ("%d) Restore Naked pair Candidates %d at Unit %d Cells %d %d\n",
            a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]]);
#endif
          g[l[y][T[a][2]]] = k[T[a][2]];
          g[l[y][T[a][3]]] = k[T[a][3]];
          g[l[y][T[a][4]]] = k[T[a][4]];
          g[l[y][T[a][5]]] = k[T[a][5]];
          g[l[y][T[a][6]]] = k[T[a][6]];
          g[l[y][T[a][7]]] = k[T[a][7]];
          g[l[y][T[a][8]]] = k[T[a][8]];
          goto Tuple;
        }                    // Restore Naked pair Candidates to Unit other Cell positions
        continue;
      }
      K[0] &= K[0] ^ K[1];   // Found more than 2 Candidates in Unit pair Cell positions
      if (B[K[0]] == 2)      // Search Hidden pair Candidates in Unit pair Cell positions
      {                      // Remove other than Hidden pair Candidates from Unit pair Cell positions
        g[l[y][T[a][0]]] &= K[0];
        g[l[y][T[a][1]]] &= K[0];
#ifdef RJ
        printf ("%d) Found Hidden pair Candidates %d at Unit %d Cells %d %d\n",
          a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]]);
#endif
        if (solve (p))
          return 1;
#ifdef RJ
        printf ("%d) Restore Hidden pair Candidates %d at Unit %d Cells %d %d\n",
          a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]]);
#endif
        g[l[y][T[a][0]]] = k[T[a][0]];
        g[l[y][T[a][1]]] = k[T[a][1]];
        goto Tuple;
      }                      // Restore other than Hidden pair Candidates to Unit pair Cell positions
    }
    if (k[9] < 6)
      continue;              // Skip triplets and quads for less than 6 unsolved Cell positions
    for (; a < 120; ++a)     // Search Unit 84 triplet Cell positions
    {
      if (!k[T[a][0]] || !k[T[a][1]] || !k[T[a][2]])
      {                      // Skip solved Cell positions
        if (!k[T[a][0]])
        {
          int A[7] = {27,20,14, 9, 5, 2, 0};

          a += A[T[a][0]];
        }
        else
          if (!k[T[a][1]])
            a += 7 - T[a][1];
        continue;
      }
      int K[2] = {k[T[a][0]] | k[T[a][1]] | k[T[a][2]], k[T[a][3]] |
        k[T[a][4]] | k[T[a][5]] | k[T[a][6]] | k[T[a][7]] | k[T[a][8]]};

      if (B[K[0]] == 3)      // Search Naked triplet Candidates in Unit triplet Cell positions
      {
        if (K[0] & K[1])     // Search Naked triplet Candidates in Unit other Cell positions
        {                    // Remove Naked triplet Candidates from Unit other Cell positions
          g[l[y][T[a][3]]] &= ~K[0];
          g[l[y][T[a][4]]] &= ~K[0];
          g[l[y][T[a][5]]] &= ~K[0];
          g[l[y][T[a][6]]] &= ~K[0];
          g[l[y][T[a][7]]] &= ~K[0];
          g[l[y][T[a][8]]] &= ~K[0];
#ifdef RJ
          printf ("%d) Found Naked triplet Candidates %d at Unit %d Cells %d %d %d\n",
            a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]]);
#endif
          if (solve (p))
            return 1;
#ifdef RJ
          printf ("%d) Restore Naked triplet Candidates %d at Unit %d Cells %d %d %d\n",
            a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]]);
#endif
          g[l[y][T[a][3]]] = k[T[a][3]];
          g[l[y][T[a][4]]] = k[T[a][4]];
          g[l[y][T[a][5]]] = k[T[a][5]];
          g[l[y][T[a][6]]] = k[T[a][6]];
          g[l[y][T[a][7]]] = k[T[a][7]];
          g[l[y][T[a][8]]] = k[T[a][8]];
          goto Tuple;
        }                    // Restore Naked triplet Candidates to Unit other Cell positions
        continue;
      }
      K[0] &= K[0] ^ K[1];   // Found more than 3 Candidates in Unit triplet Cell positions
      if (B[K[0]] == 3)      // Search Hidden triplet Candidates in Unit triplet Cell positions
      {                      // Remove other than Hidden triplet Candidates from Unit triplet Cell positions
        g[l[y][T[a][0]]] &= K[0];
        g[l[y][T[a][1]]] &= K[0];
        g[l[y][T[a][2]]] &= K[0];
#ifdef RJ
        printf ("%d) Found Hidden triplet Candidates %d at Unit %d Cells %d %d %d\n",
          a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]]);
#endif
        if (solve (p))
          return 1;
#ifdef RJ
        printf ("%d) Restore Hidden triplet Candidates %d at Unit %d Cells %d %d %d\n",
          a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]]);
#endif
        g[l[y][T[a][0]]] = k[T[a][0]];
        g[l[y][T[a][1]]] = k[T[a][1]];
        g[l[y][T[a][2]]] = k[T[a][2]];
        goto Tuple;
      }                      // Restore other than Hidden triplet Candidates to Unit triplet Cell positions
    }
    if (k[9] < 8)
      continue;              // Skip quads for less than 8 unsolved Cell positions
    for (; a < 246; ++a)     // Search Unit 126 quad Cell positions in Unit quad Cell positions
    {
      if (!k[T[a][0]] || !k[T[a][1]] || !k[T[a][2]] || !k[T[a][3]])
      {                      // Skip solved Cell positions
        if (!k[T[a][0]])
        {
          int A[6] = {55,34,19, 9, 3, 0};

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

            a += A[T[a][1]];
          }
          else
            if (!k[T[a][2]])
              a += 7 - T[a][2];
        continue;
      }
      int K[2] = {k[T[a][0]] | k[T[a][1]] | k[T[a][2]] | k[T[a][3]],
        k[T[a][4]] | k[T[a][5]] | k[T[a][6]] | k[T[a][7]] | k[T[a][8]]};

      if (B[K[0]] == 4)      // Search Naked quad Candidates in Unit quad Cell positions
      {
        if (K[0] & K[1])     // Search Naked quad Candidates in Unit other Cell positions
        {                    // Remove Naked quad Candidates from Unit other Cell positions
          g[l[y][T[a][4]]] &= ~K[0];
          g[l[y][T[a][5]]] &= ~K[0];
          g[l[y][T[a][6]]] &= ~K[0];
          g[l[y][T[a][7]]] &= ~K[0];
          g[l[y][T[a][8]]] &= ~K[0];
#ifdef RJ
          printf ("%d) Found Naked quad Candidates %d at Unit %d Cells %d %d %d %d\n",
            a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]], l[y][T[a][3]]);
#endif
          if (solve (p))
            return 1;
#ifdef RJ
          printf ("%d) Restore Naked quad Candidates %d at Unit %d Cells %d %d %d %d\n",
            a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]], l[y][T[a][3]]);
#endif
          g[l[y][T[a][4]]] = k[T[a][4]];
          g[l[y][T[a][5]]] = k[T[a][5]];
          g[l[y][T[a][6]]] = k[T[a][6]];
          g[l[y][T[a][7]]] = k[T[a][7]];
          g[l[y][T[a][8]]] = k[T[a][8]];
          goto Tuple;
        }                    // Restore Naked quad Candidates to Unit other Cell positions
        continue;
      }
      K[0] &= K[0] ^ K[1];   // Found more than 4 Candidates in Unit quad Cell positions
      if (B[K[0]] == 4)      // Search Hidden quad Candidates in Unit quad Cell positions
      {                      // Remove other than Hidden quad Candidates from Unit quad Cell positions
        g[l[y][T[a][0]]] &= K[0];
        g[l[y][T[a][1]]] &= K[0];
        g[l[y][T[a][2]]] &= K[0];
        g[l[y][T[a][3]]] &= K[0];
#ifdef RJ
        printf ("%d) Found Hidden quad Candidates %d at Unit %d Cells %d %d %d %d\n",
          a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]], l[y][T[a][3]]);
#endif
        if (solve (p))
          return 1;
#ifdef RJ
        printf ("%d) Restore Hidden quad Candidates %d at Unit %d Cells %d %d %d %d\n",
          a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]], l[y][T[a][3]]);
#endif
        g[l[y][T[a][0]]] = k[T[a][0]];
        g[l[y][T[a][1]]] = k[T[a][1]];
        g[l[y][T[a][2]]] = k[T[a][2]];
        g[l[y][T[a][3]]] = k[T[a][3]];
        goto Tuple;
      }                      // Restore other than Hidden quad Candidates to Unit quad Cell positions
    }
  }
Tuple:
  for (y = 0; y < 54; ++y)   // Search 54 Box-Line Cell positions for Intersection Removal Candidate
    for (a = 0; a < 9; ++a)  // Search Intersection Removal Candidate for each Box-Line Cell positions
      if ((g[j[y][0]] >> a) & 1 || (g[j[y][1]] >> a) & 1 || (g[j[y][2]] >> a) & 1)
      {                      // Found Intersection Removal Candidate in Box-Line Cell positions
        if ((g[j[y][3]] >> a) & 1 || (g[j[y][4]] >> a) & 1 ||
          (g[j[y][5]] >> a) & 1 || (g[j[y][6]] >> a) & 1 ||
          (g[j[y][7]] >> a) & 1 || (g[j[y][8]] >> a) & 1)
        {                    // Found Intersection Removal Candidate in Line other Cell positions
          if (!((g[j[y][9]] >> a) & 1 || (g[j[y][10]] >> a) & 1 ||
            (g[j[y][11]] >> a) & 1 || (g[j[y][12]] >> a) & 1 ||
            (g[j[y][13]] >> a) & 1 || (g[j[y][14]] >> a) & 1))
          {                  // Intersection Removal Candidate not found in Box other Cell positions
            int k = (g[j[y][3]] >> a) & 1 | ((g[j[y][4]] >> a) & 1) << 1 |
              ((g[j[y][5]] >> a) & 1) << 2 | ((g[j[y][6]] >> a) & 1) << 3 |
              ((g[j[y][7]] >> a) & 1) << 4 | ((g[j[y][8]] >> a) & 1) << 5;
                             // Backup and remove Intersection Removal Candidate in Line other Cell positions
            g[j[y][3]] &= ~(1 << a);
            g[j[y][4]] &= ~(1 << a);
            g[j[y][5]] &= ~(1 << a);
            g[j[y][6]] &= ~(1 << a);
            g[j[y][7]] &= ~(1 << a);
            g[j[y][8]] &= ~(1 << a);
#ifdef RJ
            printf ("%d) Found Pointing and Claiming Intersection Removal Candidate %d at Cells %d %d %d\n",
              y, a + 1, j[y][0], j[y][1], j[y][2]);
#endif
            if (solve (p))
              return 1;
#ifdef RJ
            printf ("%d) Restore Pointing and Claiming Intersection Removal Candidate %d at Cells %d %d %d\n",
              y, a + 1, j[y][0], j[y][1], j[y][2]);
#endif
            g[j[y][3]] |= (k & 1) << a;
            g[j[y][4]] |= ((k >> 1) & 1) << a;
            g[j[y][5]] |= ((k >> 2) & 1) << a;
            g[j[y][6]] |= ((k >> 3) & 1) << a;
            g[j[y][7]] |= ((k >> 4) & 1) << a;
            g[j[y][8]] |= ((k >> 5) & 1) << a;
            goto IntRem;
          }                  // Restore Intersection Removal Candidate in Line other Cell positions
          continue;
        }                    // Intersection Removal Candidate not found in Line other Cell positions
        if ((g[j[y][9]] >> a) & 1 || (g[j[y][10]] >> a) & 1 ||
          (g[j[y][11]] >> a) & 1 || (g[j[y][12]] >> a) & 1 ||
          (g[j[y][13]] >> a) & 1 || (g[j[y][14]] >> a) & 1)
        {                    // Found Intersection Removal Candidate in Box other Cell positions
          int k = (g[j[y][9]] >> a) & 1 | ((g[j[y][10]] >> a) & 1) << 1 |
            ((g[j[y][11]] >> a) & 1) << 2 | ((g[j[y][12]] >> a) & 1) << 3 |
            ((g[j[y][13]] >> a) & 1) << 4 | ((g[j[y][14]] >> a) & 1) << 5;
                             // Backup and remove Intersection Removal Candidate in Box other Cell positions
          g[j[y][9]] &= ~(1 << a);
          g[j[y][10]] &= ~(1 << a);
          g[j[y][11]] &= ~(1 << a);
          g[j[y][12]] &= ~(1 << a);
          g[j[y][13]] &= ~(1 << a);
          g[j[y][14]] &= ~(1 << a);
#ifdef RJ
          printf ("%d) Found Box-Line Reduction Intersection Removal Candidate %d at Cells %d %d %d\n",
            y, a + 1, j[y][0], j[y][1], j[y][2]);
#endif
          if (solve (p))
            return 1;
#ifdef RJ
          printf ("%d) Restore Box-Line Reduction Intersection Removal Candidate %d at Cells %d %d %d\n",
            y, a + 1, j[y][0], j[y][1], j[y][2]);
#endif
          g[j[y][9]] |= (k & 1) << a;
          g[j[y][10]] |= ((k >> 1) & 1) << a;
          g[j[y][11]] |= ((k >> 2) & 1) << a;
          g[j[y][12]] |= ((k >> 3) & 1) << a;
          g[j[y][13]] |= ((k >> 4) & 1) << a;
          g[j[y][14]] |= ((k >> 5) & 1) << a;
          goto IntRem;
        }                    // Restore Intersection Removal Candidate in Box other Cell positions
      }
IntRem:
  for (y = 0; y < 18; ++y)   // Search Basic Fishes Line wise
  {
    int k[10],               // Backup Line Cell positions and Basic Fish Candidate
        Y = y < 9 ? 0 : 9;   // Either Row or Column wise

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

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

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

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

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

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

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

  for (g[r[p]] = 0; s[r[p]] = b[z & -z]; ++n, z &= z - 1)
  {                          // Remove current Cell position Candidates and solve current Cell position Candidate wise
    int k = 0;

    for (a = 0; a < 20; ++a)
      if (g[w[r[p]][a]] & (1 << (s[r[p]] - 1)))
      {
        k |= 1 << a;         // Backup affected 20 Cell positions current Candidate
        g[w[r[p]][a]] &= ~(1 << (s[r[p]] - 1));
      }                      // Remove current Candidate from affected 20 Cell positions
#ifdef RJ
    printf ("%d) Apply %s Candidate %d from Candidates %d at Cell %d\n",
      p, y ? (y > 1 ? "Trial and Error" : "Hidden Single") : "Naked Single",
      s[r[p]], b[K], r[p]);
#endif
    if (a > 19 && (p + 1 >= q || solve (p + 1)))
      return 1;              // If either all Cell positions solved or recursive solve for next unsolved Cell position
#ifdef RJ
    printf ("%d) Restore %s Candidate %d from Candidates %d at Cell %d\n",
      p, y ? (y > 1 ? "Trial and Error" : "Hidden Single") : "Naked Single",
      s[r[p]], b[K], r[p]);
#endif
    while (a > 0)            // Restore current Candidate to affected 20 Cell positions
      g[w[r[p]][--a]] |= ((k >> a) & 1) << (s[r[p]] - 1);
  }
  g[r[p]] = K;               // Restore Candidates to current Cell position
  return 0;
}

int check (int p, int q)
{
  for (int a = 0; a < 20; ++a)
    if (s[w[p][a]] == q)     // Check duplicate Candidate in affected 20 clue Cell positions
      return 0;
  return 1;
}

int invalid (void)
{
  for (int p = 0; p < 81; ++p)
    if (!s[p])               // Found unsolved Cell position
    {
      for (int a = 0; a < 9; ++a)
        g[p] |= check (p, a + 1) << a;
                             // Check constraint and assign Candidate for unsolved Cell position
      if (!g[p])             // Check no Candidate assigned
        return 1;
      r[q++] = p;            // Assign unsolved Cell position for sorting and eliminating
    }
    else
      if (!check (p, s[p]))  // Check constraint for clue Cell position
        return 1;
  return 0;
}

int main (void)
{
  int a = -1,
      m,
      i = 0,
      t = 0,
      u = 0,
      v = 0,
      y = 0;

  float c,
        d = 0,
        e = 0,
        f = 0,
        k = 0;

  FILE *o = fopen ("sudoku.txt", "r");

  if (o == NULL)
    printf ("Unable to open sudoku.txt file for read !!\n");
  else
    do
    {
      if ((m = fgetc (o)) != 10 && m != EOF && a < 80)
        s[++a] = m >= '1' && m <= '9' ? m - '0' : 0;
      else                   // Assign clue Cell positions
        if (m == 10 || m == EOF)
        {
#ifdef RJ
          printf ("\n");
#endif
          while (a < 80)     // Clear remaining unsolved Cell positions
            s[++a] = 0;
          n = h = q = 0;
          c = clock ();
          if (invalid ())
          {
            c = (clock () - c) / CLOCKS_PER_SEC * 1000;
            d += c;
            printf ("%ld) Error: Invalid Sudoku! # I%ld", ++t, ++i);
          }
          else
            if (!q)
            {
              c = (clock () - c) / CLOCKS_PER_SEC * 1000;
              k += c;
              printf ("%ld) Valid Sudoku # V%ld", ++t, ++y);
            }
            else
              if (solve (0))
              {
                c = (clock () - c) / CLOCKS_PER_SEC * 1000;
                e += c;
                printf ("%ld) ", ++t);
                for (a = 0; a < 81; ++a)
                  printf ("%c", s[a] + '0');
                printf (" # S%ld", ++v);
              }
              else
              {
                c = (clock () - c) / CLOCKS_PER_SEC * 1000;
                f += c;
                printf ("%ld) Error: Unsolvable Sudoku! # U%ld", ++t, ++u);
              }
          printf (" # N%ld # H%ld # %f\n", n, h, c);
          a = -1;
        }
#ifdef RJ
      if (m != EOF)
        printf ("%c", m);
#endif
    }
    while (m != EOF);
  printf ("=======================================\n");
  printf ("Total Sudoku puzzle read   : %ld\n", t);
  printf ("Total time for all puzzles : %f\n", d + e + f + y);
  printf ("Average time per puzzle    : %f\n", t ? (d + e + f + y) / t : 0);
  printf ("Number of valid puzzles    : %ld\n", y);
  printf ("Time for valid puzzles     : %f\n", k);
  printf ("Average time per valid     : %f\n", y ? k / y : 0);
  printf ("Number of invalid puzzles  : %ld\n", i);
  printf ("Time for invalid puzzles   : %f\n", d);
  printf ("Average time per invalid   : %f\n", i ? d / i : 0);
  printf ("Number of solved puzzles   : %ld\n", v);
  printf ("Time for solved puzzles    : %f\n", e);
  printf ("Average time per solved    : %f\n", v ? e / v : 0);
  printf ("Number of unsolved puzzle  : %ld\n", u);
  printf ("Time for unsolved puzzles  : %f\n", f);
  printf ("Average time per unsolved  : %f\n", u ? f / u : 0);
  if (fclose (o) == EOF)
    printf ("Unable to close sudoku.txt file !!");
}

Updated on 20151012:

Hidden Text: Show

1) For each Tuple combination, do not check Hidden if Naked found.

2) Changes in Hidden Tuple k[9] variable assignments logic by removing solved cells as follows:
Old for Pair:
k[9] = ~(k[T[a][2]] | k[T[a][3]] | k[T[a][4]] | k[T[a][5]] |
k[T[a][6]] | k[T[a][7]] | k[T[a][8]] | W[s[l[y][T[a][2]]]] |
W[s[l[y][T[a][3]]]] | W[s[l[y][T[a][4]]]] | W[s[l[y][T[a][5]]]] |
W[s[l[y][T[a][6]]]] | W[s[l[y][T[a][7]]]] | W[s[l[y][T[a][8]]]]) & 511;
New:
k[9] &= k[9] ^ (k[T[a][2]] | k[T[a][3]] | k[T[a][4]] | k[T[a][5]] |
k[T[a][6]] | k[T[a][7]] | k[T[a][8]]);

Old for Triplet:
k[9] = ~(k[T[a][3]] | k[T[a][4]] | k[T[a][5]] | k[T[a][6]] | k[T[a][7]] |
k[T[a][8]] | W[s[l[y][T[a][3]]]] | W[s[l[y][T[a][4]]]] |
W[s[l[y][T[a][5]]]] | W[s[l[y][T[a][6]]]] | W[s[l[y][T[a][7]]]] |
W[s[l[y][T[a][8]]]]) & 511;
New:
k[9] &= k[9] ^ (k[T[a][3]] | k[T[a][4]] | k[T[a][5]] |
k[T[a][6]] | k[T[a][7]] | k[T[a][8]]);

Old for Quad:
k[9] = ~(k[T[a][4]] | k[T[a][5]] | k[T[a][6]] | k[T[a][7]] | k[T[a][8]] |
W[s[l[y][T[a][4]]]] | W[s[l[y][T[a][5]]]] | W[s[l[y][T[a][6]]]] |
W[s[l[y][T[a][7]]]] | W[s[l[y][T[a][8]]]]) & 511;
New:
k[9] &= k[9] ^ (k[T[a][4]] | k[T[a][5]] |
k[T[a][6]] | k[T[a][7]] | k[T[a][8]]);

Updated on 20151014:

Hidden Text: Show

1. For Naked/Hidden tuple elimination routine, added skip for less unsolved cells.

2. Added variable K assignment for count unsolved cells:
K = (g[l[y][0]] ? 1 : 0) + (g[l[y][1]] ? 1 : 0) + (g[l[y][2]] ? 1 : 0) +
(g[l[y][3]] ? 1 : 0) + (g[l[y][4]] ? 1 : 0) + (g[l[y][5]] ? 1 : 0) +
(g[l[y][6]] ? 1 : 0) + (g[l[y][7]] ? 1 : 0) + (g[l[y][8]] ? 1 : 0);

3. Added before pairs checking loop:
if(K < 4)
continue; // Skip Unit for less than 4 unsolved Cells

4. Added before triplets checking loop:
if(K < 6)
continue; // Skip triplets and quads for less than 6 unsolved Cells

5. Added before quads checking loop:
if(K < 8)
continue; // Skip quads for less than 8 unsolved Cells

Updated on 20151017:

Hidden Text: Show

1. Lot of changes in comments area.

2. In Naked/Hidden tuple routine, swap k[9] array element and K variable assignments and usage for easy readability.

3. In Restore Pointing and Claiming Intersection Removal for Candidate:
Old:
g[j[y][3]] ^= (-(k & 1) ^ g[j[y][3]]) & (1 << a);
g[j[y][4]] ^= (-((k >> 1) & 1) ^ g[j[y][4]]) & (1 << a);
g[j[y][5]] ^= (-((k >> 2) & 1) ^ g[j[y][5]]) & (1 << a);
g[j[y][6]] ^= (-((k >> 3) & 1) ^ g[j[y][6]]) & (1 << a);
g[j[y][7]] ^= (-((k >> 4) & 1) ^ g[j[y][7]]) & (1 << a);
g[j[y][8]] ^= (-((k >> 5) & 1) ^ g[j[y][8]]) & (1 << a);
New:
g[j[y][3]] |= (k & 1) << a;
g[j[y][4]] |= ((k >> 1) & 1) << a;
g[j[y][5]] |= ((k >> 2) & 1) << a;
g[j[y][6]] |= ((k >> 3) & 1) << a;
g[j[y][7]] |= ((k >> 4) & 1) << a;
g[j[y][8]] |= ((k >> 5) & 1) << a;

4. In Restore Box-Line Reduction Intersection Removal for Candidate:
Old:
g[j[y][9]] ^= (-(k & 1) ^ g[j[y][9]]) & (1 << a);
g[j[y][10]] ^= (-((k >> 1) & 1) ^ g[j[y][10]]) & (1 << a);
g[j[y][11]] ^= (-((k >> 2) & 1) ^ g[j[y][11]]) & (1 << a);
g[j[y][12]] ^= (-((k >> 3) & 1) ^ g[j[y][12]]) & (1 << a);
g[j[y][13]] ^= (-((k >> 4) & 1) ^ g[j[y][13]]) & (1 << a);
g[j[y][14]] ^= (-((k >> 5) & 1) ^ g[j[y][14]]) & (1 << a);
New:
g[j[y][9]] |= (k & 1) << a;
g[j[y][10]] |= ((k >> 1) & 1) << a;
g[j[y][11]] |= ((k >> 2) & 1) << a;
g[j[y][12]] |= ((k >> 3) & 1) << a;
g[j[y][13]] |= ((k >> 4) & 1) << a;
g[j[y][14]] |= ((k >> 5) & 1) << a;

5. In Assign solved Cell Candidate wise routine, move Backup current Cell Candidates to above outside loop:
int K = g[r[p][0]]; // Backup current Cell position Candidates

6. In Assign solved Cell Candidate wise routine, move Restore current Cell Candidates to below outside loop:
g[r[p][0]] = K; // Restore Candidates current Cell position

Updated on 20151026:

Hidden Text: Show

1. Changed r[81][2] array from two dimensions to one r[81].

2. Changed w[81][20] array values from sorted order to 6 unique row, 2 common row and box, 4 unique box, 2 common box and column, 6 unique column cells order for also searching hidden single candidate.

3. Merged naked and hidden single candidate search routines:
Old:

Code: Select all

  for(a = p; a < q; ++a)
    if(B[z] > B[g[r[a][0]]])
      if(B[z = g[r[x = a][0]]] == 1)
        goto NHSCF;
  for(; y < 27; ++y)
    for(a = 0; a < 9; ++a)
      if(((g[l[y][0]] >> a) & 1) + ((g[l[y][1]] >> a) & 1) +
        ((g[l[y][2]] >> a) & 1) + ((g[l[y][3]] >> a) & 1) +
        ((g[l[y][4]] >> a) & 1) + ((g[l[y][5]] >> a) & 1) +
        ((g[l[y][6]] >> a) & 1) + ((g[l[y][7]] >> a) & 1) +
        ((g[l[y][8]] >> a) & 1) == 1)
      {
        ++h;
        x = (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;
        z = 1 << a;
        a = l[y][b[x] - 1];
        x = r[a][1];
#ifdef RJ
        y = 1;
#endif
        goto NHSCF;
      }

New:

Code: Select all

  for (a = p; a < q; ++a)
  {
    if (B[z] > B[g[r[a]]])
      if (B[z = g[r[x = a]]] == 1)
        goto NHSCF;
    int K[3] = {
      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]][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]])),
      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[0]] == 1)
      z = K[0];
    else
      if (B[K[1]] == 1)
        z = K[1];
      else
        if (B[K[2]] == 1)
          z = K[2];
        else
          continue;
    ++h;
    x = a;
#ifdef RJ
    y = 1;
#endif
    goto NHSCF;
  }

4. Slightly changed in Tuple checking. Now naked pair/triplet/quad candidates checked in pair/triplet/quad cell positions first then unit other cell positions for elimination. By this means, if naked pair/triplet/quad candidates not found then hidden pair/triplet/quad candidates checking in pair/triplet/quad cell positions is enough for elimination.

5. Bug fixed: Added summary for "Valid Sudoku". Now complete Sudoku grid given will also be checked only.

6. Some source code beautification and added comments.

Updated on 20151029: DOS command fc /n output:

Hidden Text: Show

Comparing files RJSolBit.CPP and RJSOLBW5.CPP
***** RJSolBit.CPP
342: {35,44,53, 8,17,26,62,71,80,33,34,42,43,51,52},
343: {62,71,80, 8,17,26,35,44,53,60,61,69,70,78,79}};
344:
***** RJSOLBW5.CPP
342: {35,44,53, 8,17,26,62,71,80,33,34,42,43,51,52},
343: {62,71,80, 8,17,26,35,44,53,60,61,69,70,78,79}},
344: W[10] = // Candidate position Bitwise
345: { 0, 1, 2, 4, 8, 16, 32, 64, 128, 256};
346:
*****

***** RJSolBit.CPP
401: }
402: int K[2] = {k[T[a][0]] | k[T[a][1]], k[T[a][2]] | k[T[a][3]] |
403: k[T[a][4]] | k[T[a][5]] | k[T[a][6]] | k[T[a][7]] | k[T[a][8]]};
404:
405: if (B[K[0]] == 2) // Search Naked pair Candidates
406: {
407: if (K[0] & K[1]) // Search Naked pair Candidates in Unit other Cell positions
408: { // Remove Naked pair Candidates from Unit other Cell positions
409: g[l[y][T[a][2]]] &= ~K[0];
410: g[l[y][T[a][3]]] &= ~K[0];
411: g[l[y][T[a][4]]] &= ~K[0];
412: g[l[y][T[a][5]]] &= ~K[0];
413: g[l[y][T[a][6]]] &= ~K[0];
414: g[l[y][T[a][7]]] &= ~K[0];
415: g[l[y][T[a][8]]] &= ~K[0];
416: #ifdef RJ
***** RJSOLBW5.CPP
403: }
404: int K = k[T[a][0]] | k[T[a][1]];
405:
406: if (B[K] == 2) // Search Naked pair Candidates
407: {
408: if (K & (k[T[a][2]] | k[T[a][3]] |
409: k[T[a][4]] | k[T[a][5]] | k[T[a][6]] | k[T[a][7]] | k[T[a][8]]))
410: { // Found Naked pair Candidates in Unit other Cell positions
411: // Remove Naked pair Candidates from Unit other Cell positions
412: g[l[y][T[a][2]]] &= ~K;
413: g[l[y][T[a][3]]] &= ~K;
414: g[l[y][T[a][4]]] &= ~K;
415: g[l[y][T[a][5]]] &= ~K;
416: g[l[y][T[a][6]]] &= ~K;
417: g[l[y][T[a][7]]] &= ~K;
418: g[l[y][T[a][8]]] &= ~K;
419: #ifdef RJ
*****

***** RJSolBit.CPP
417: printf ("%d) Found Naked pair Candidates %d at Unit %d Cells %d %d\n",
418: a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]]);
419: #endif
***** RJSOLBW5.CPP
420: printf ("%d) Found Naked pair Candidates %d at Unit %d Cells %d %d\n",
421: a, b[K], y, l[y][T[a][0]], l[y][T[a][1]]);
422: #endif
*****

***** RJSolBit.CPP
423: printf ("%d) Restore Naked pair Candidates %d at Unit %d Cells %d %d\n",
424: a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]]);
425: #endif
***** RJSOLBW5.CPP
426: printf ("%d) Restore Naked pair Candidates %d at Unit %d Cells %d %d\n",
427: a, b[K], y, l[y][T[a][0]], l[y][T[a][1]]);
428: #endif
*****

***** RJSolBit.CPP
435: }
436: K[0] &= K[0] ^ K[1]; // Pair Cell positions contain more than 2 Candidates
437: if (B[K[0]] == 2) // Search Hidden pair Candidates
438: { // Remove Hidden pair Candidates from pair Cell positions
439: g[l[y][T[a][0]]] &= K[0];
440: g[l[y][T[a][1]]] &= K[0];
441: #ifdef RJ
442: printf ("%d) Found Hidden pair Candidates %d at Unit %d Cells %d %d\n",
443: a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]]);
444: #endif
445: if (solve (p))
446: return 1;
447: #ifdef RJ
448: printf ("%d) Restore Hidden pair Candidates %d at Unit %d Cells %d %d\n",
449: a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]]);
450: #endif
451: g[l[y][T[a][0]]] = k[T[a][0]];
452: g[l[y][T[a][1]]] = k[T[a][1]];
453: } // Restore Candidates to pair Cell positions
454: }
***** RJSOLBW5.CPP
438: }
439: else
440: {
441: K &= K ^ (k[T[a][2]] | k[T[a][3]] | k[T[a][4]] | k[T[a][5]] |
442: k[T[a][6]] | k[T[a][7]] | k[T[a][8]]);
443: if (B[K] == 2) // Search Hidden pair Candidates
444: { // Remove Hidden pair Candidates from pair Cell positions
445: g[l[y][T[a][0]]] &= K;
446: g[l[y][T[a][1]]] &= K;
447: #ifdef RJ
448: printf ("%d) Found Hidden pair Candidates %d at Unit %d Cells %d %d\n",
449: a, b[K], y, l[y][T[a][0]], l[y][T[a][1]]);
450: #endif
451: if (solve (p))
452: return 1;
453: #ifdef RJ
454: printf ("%d) Restore Hidden pair Candidates %d at Unit %d Cells %d %d\n",
455: a, b[K], y, l[y][T[a][0]], l[y][T[a][1]]);
456: #endif
457: g[l[y][T[a][0]]] = k[T[a][0]];
458: g[l[y][T[a][1]]] = k[T[a][1]];
459: } // Restore Candidates to pair Cell positions
460: }
461: }
*****

***** RJSolBit.CPP
471: }
472: int K[2] = {k[T[a][0]] | k[T[a][1]] | k[T[a][2]], k[T[a][3]] |
473: k[T[a][4]] | k[T[a][5]] | k[T[a][6]] | k[T[a][7]] | k[T[a][8]]};
474:
475: if (B[K[0]] == 3) // Search Naked triplet Candidates
476: {
477: if (K[0] & K[1]) // Search Naked triplet Candidates in Unit other Cell positions
478: { // Remove Naked triplet Candidates from Unit other Cell positions
479: g[l[y][T[a][3]]] &= ~K[0];
480: g[l[y][T[a][4]]] &= ~K[0];
481: g[l[y][T[a][5]]] &= ~K[0];
482: g[l[y][T[a][6]]] &= ~K[0];
483: g[l[y][T[a][7]]] &= ~K[0];
484: g[l[y][T[a][8]]] &= ~K[0];
485: #ifdef RJ
***** RJSOLBW5.CPP
478: }
479: int K = k[T[a][0]] | k[T[a][1]] | k[T[a][2]];
480:
481: if (B[K] == 3) // Search Naked triplet Candidates
482: {
483: if (K & (k[T[a][3]] | k[T[a][4]] |
484: k[T[a][5]] | k[T[a][6]] | k[T[a][7]] | k[T[a][8]]))
485: { // Found Naked triplet Candidates in Unit other Cell positions
486: // Remove Naked triplet Candidates from Unit other Cell positions
487: g[l[y][T[a][3]]] &= ~K;
488: g[l[y][T[a][4]]] &= ~K;
489: g[l[y][T[a][5]]] &= ~K;
490: g[l[y][T[a][6]]] &= ~K;
491: g[l[y][T[a][7]]] &= ~K;
492: g[l[y][T[a][8]]] &= ~K;
493: #ifdef RJ
*****

***** RJSolBit.CPP
486: printf ("%d) Found Naked triplet Candidates %d at Unit %d Cells %d %d %d\n",
487: a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]]);
488: #endif
***** RJSOLBW5.CPP
494: printf ("%d) Found Naked triplet Candidates %d at Unit %d Cells %d %d %d\n",
495: a, b[K], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]]);
496: #endif
*****

***** RJSolBit.CPP
492: printf ("%d) Restore Naked triplet Candidates %d at Unit %d Cells %d %d %d\n",
493: a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]]);
494: #endif
***** RJSOLBW5.CPP
500: printf ("%d) Restore Naked triplet Candidates %d at Unit %d Cells %d %d %d\n",
501: a, b[K], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]]);
502: #endif
*****

***** RJSolBit.CPP
500: g[l[y][T[a][8]]] = k[T[a][8]];
501: } // Restore Candidates to Unit other Cell positions
502: continue;
503: }
504: K[0] &= K[0] ^ K[1]; // Triplet Cell positions contain more than 3 Candidates
505: if (B[K[0]] == 3) // Search Hidden triplet Candidates
506: { // Remove Hidden triplet Candidates from triplet Cell positions
507: g[l[y][T[a][0]]] &= K[0];
508: g[l[y][T[a][1]]] &= K[0];
509: g[l[y][T[a][2]]] &= K[0];
510: #ifdef RJ
511: printf ("%d) Found Hidden triplet Candidates %d at Unit %d Cells %d %d %d\n",
512: a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]]);
513: #endif
514: if (solve (p))
515: return 1;
516: #ifdef RJ
517: printf ("%d) Restore Hidden triplet Candidates %d at Unit %d Cells %d %d %d\n",
518: a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]]);
519: #endif
520: g[l[y][T[a][0]]] = k[T[a][0]];
521: g[l[y][T[a][1]]] = k[T[a][1]];
522: g[l[y][T[a][2]]] = k[T[a][2]];
523: } // Restore Candidates to triplet Cell positions
524: }
***** RJSOLBW5.CPP
508: g[l[y][T[a][8]]] = k[T[a][8]];
509: continue; // Restore Candidates to Unit other Cell positions
510: }
511: }
512: else
513: {
514: K &= K ^ (k[T[a][3]] | k[T[a][4]] | k[T[a][5]] |
515: k[T[a][6]] | k[T[a][7]] | k[T[a][8]]);
516: if (B[K] == 3) // Search Hidden triplet Candidates
517: { // Remove Hidden triplet Candidates from triplet Cell positions
518: g[l[y][T[a][0]]] &= K;
519: g[l[y][T[a][1]]] &= K;
520: g[l[y][T[a][2]]] &= K;
521: #ifdef RJ
522: printf ("%d) Found Hidden triplet Candidates %d at Unit %d Cells %d %d %d\n",
523: a, b[K], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]]);
524: #endif
525: if (solve (p))
526: return 1;
527: #ifdef RJ
528: printf ("%d) Restore Hidden triplet Candidates %d at Unit %d Cells %d %d %d\n",
529: a, b[K], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]]);
530: #endif
531: g[l[y][T[a][0]]] = k[T[a][0]];
532: g[l[y][T[a][1]]] = k[T[a][1]];
533: g[l[y][T[a][2]]] = k[T[a][2]];
534: } // Restore Candidates to triplet Cell positions
535: }
536: }
*****

***** RJSolBit.CPP
525: if (k[9] < 8)
526: continue; // Skip quads for less than 8 unsolved Cell positions
527: for (; a < 246; ++a) // Search 126 quad Cell positions for each Unit
***** RJSOLBW5.CPP
537: if (k[9] < 8)
538: continue; // Skip quads for less than 8 unsolved Cells
539: for (; a < 246; ++a) // Search 126 quad Cell positions for each Unit
*****

***** RJSolBit.CPP
548: }
549: int K[2] = {k[T[a][0]] | k[T[a][1]] | k[T[a][2]] | k[T[a][3]],
550: k[T[a][4]] | k[T[a][5]] | k[T[a][6]] | k[T[a][7]] | k[T[a][8]]};
551:
552: if (B[K[0]] == 4) // Search Naked quad Candidates
553: {
554: if (K[0] & K[1]) // Search Naked quad Candidates in Unit other Cell positions
555: { // Remove Naked quad Candidates from Unit other Cell positions
556: g[l[y][T[a][4]]] &= ~K[0];
557: g[l[y][T[a][5]]] &= ~K[0];
558: g[l[y][T[a][6]]] &= ~K[0];
559: g[l[y][T[a][7]]] &= ~K[0];
560: g[l[y][T[a][8]]] &= ~K[0];
561: #ifdef RJ
***** RJSOLBW5.CPP
560: }
561: int K = k[T[a][0]] | k[T[a][1]] | k[T[a][2]] | k[T[a][3]];
562:
563: if (B[K] == 4) // Search Naked quad Candidates
564: {
565: if (K & (k[T[a][4]] | k[T[a][5]] |
566: k[T[a][6]] | k[T[a][7]] | k[T[a][8]]))
567: { // Found Naked quad Candidates in Unit other Cell positions
568: // Remove Naked quad Candidates from Unit other Cell positions
569: g[l[y][T[a][4]]] &= ~K;
570: g[l[y][T[a][5]]] &= ~K;
571: g[l[y][T[a][6]]] &= ~K;
572: g[l[y][T[a][7]]] &= ~K;
573: g[l[y][T[a][8]]] &= ~K;
574: #ifdef RJ
*****

***** RJSolBit.CPP
562: printf ("%d) Found Naked quad Candidates %d at Unit %d Cells %d %d %d %d\n",
563: a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]], l[y][T[a][3]]);
564: #endif
***** RJSOLBW5.CPP
575: printf ("%d) Found Naked quad Candidates %d at Unit %d Cells %d %d %d %d\n",
576: a, b[K], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]], l[y][T[a][3]]);
577: #endif
*****

***** RJSolBit.CPP
568: printf ("%d) Restore Naked quad Candidates %d at Unit %d Cells %d %d %d %d\n",
569: a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]], l[y][T[a][3]]);
570: #endif
***** RJSOLBW5.CPP
581: printf ("%d) Restore Naked quad Candidates %d at Unit %d Cells %d %d %d %d\n",
582: a, b[K], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]], l[y][T[a][3]]);
583: #endif
*****

***** RJSolBit.CPP
575: g[l[y][T[a][8]]] = k[T[a][8]];
576: } // Restore Candidates to Unit other Cell positions
577: continue;
578: }
579: K[0] &= K[0] ^ K[1]; // Quad Cell positions contain more than 4 Candidates
580: if (B[K[0]] == 4) // Search Hidden quad Candidates
581: { // Remove Hidden quad Candidates from quad Cell positions
582: g[l[y][T[a][0]]] &= K[0];
583: g[l[y][T[a][1]]] &= K[0];
584: g[l[y][T[a][2]]] &= K[0];
585: g[l[y][T[a][3]]] &= K[0];
586: #ifdef RJ
587: printf ("%d) Found Hidden quad Candidates %d at Unit %d Cells %d %d %d %d\n",
588: a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]], l[y][T[a][3]]);
589: #endif
590: if (solve (p))
591: return 1;
592: #ifdef RJ
593: printf ("%d) Restore Hidden quad Candidates %d at Unit %d Cells %d %d %d %d\n",
594: a, b[K[0]], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]], l[y][T[a][3]]);
595: #endif
596: g[l[y][T[a][0]]] = k[T[a][0]];
597: g[l[y][T[a][1]]] = k[T[a][1]];
598: g[l[y][T[a][2]]] = k[T[a][2]];
599: g[l[y][T[a][3]]] = k[T[a][3]];
600: } // Restore Candidates to quad Cell positions
601: }
***** RJSOLBW5.CPP
588: g[l[y][T[a][8]]] = k[T[a][8]];
589: continue; // Restore Candidates to Unit other Cell positions
590: }
591: }
592: else
593: {
594: K &= K ^ (k[T[a][4]] | k[T[a][5]] |
595: k[T[a][6]] | k[T[a][7]] | k[T[a][8]]);
596: if (B[K] == 4) // Search Hidden quad Candidates
597: { // Remove Hidden quad Candidates from quad Cell positions
598: g[l[y][T[a][0]]] &= K;
599: g[l[y][T[a][1]]] &= K;
600: g[l[y][T[a][2]]] &= K;
601: g[l[y][T[a][3]]] &= K;
602: #ifdef RJ
603: printf ("%d) Found Hidden quad Candidates %d at Unit %d Cells %d %d %d %d\n",
604: a, b[K], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]], l[y][T[a][3]]);
605: #endif
606: if (solve (p))
607: return 1;
608: #ifdef RJ
609: printf ("%d) Restore Hidden quad Candidates %d at Unit %d Cells %d %d %d %d\n",
610: a, b[K], y, l[y][T[a][0]], l[y][T[a][1]], l[y][T[a][2]], l[y][T[a][3]]);
611: #endif
612: g[l[y][T[a][0]]] = k[T[a][0]];
613: g[l[y][T[a][1]]] = k[T[a][1]];
614: g[l[y][T[a][2]]] = k[T[a][2]];
615: g[l[y][T[a][3]]] = k[T[a][3]];
616: } // Restore Candidates to quad Cell positions
617: }
618: }
*****

***** RJSolBit.CPP
641: } // Restore Intersection Removal Candidate within Line unsolved 6 Cell positions
642: continue;
643: } // Not Found Intersection Removal Candidate within Line unsolved 6 Cell positions
644: if ((g[j[y][9]] >> a) & 1 || (g[j[y][10]] >> a) & 1 ||
645: (g[j[y][11]] >> a) & 1 || (g[j[y][12]] >> a) & 1 ||
646: (g[j[y][13]] >> a) & 1 || (g[j[y][14]] >> a) & 1)
647: { // Found Intersection Removal Candidate within Box unsolved 6 Cell positions
648: int k = (g[j[y][9]] >> a) & 1 | ((g[j[y][10]] >> a) & 1) << 1 |
649: ((g[j[y][11]] >> a) & 1) << 2 | ((g[j[y][12]] >> a) & 1) << 3 |
650: ((g[j[y][13]] >> a) & 1) << 4 | ((g[j[y][14]] >> a) & 1) << 5;
651: // Backup Intersection Removal Candidate within Box unsolved 6 Cell positions
652: g[j[y][9]] &= ~(1 << a);
653: g[j[y][10]] &= ~(1 << a);
654: g[j[y][11]] &= ~(1 << a);
655: g[j[y][12]] &= ~(1 << a);
656: g[j[y][13]] &= ~(1 << a);
657: g[j[y][14]] &= ~(1 << a);
658: #ifdef RJ
659: printf ("%d) Found Box-Line Reduction Intersection Removal for Candidate %d at Cells %d %d %d\n",
660: y, a + 1, j[y][0], j[y][1], j[y][2]);
661: #endif
662: if (solve (p))
663: return 1;
664: #ifdef RJ
665: printf ("%d) Restore Box-Line Reduction Intersection Removal for Candidate %d at Cells %d %d %d\n",
666: y, a + 1, j[y][0], j[y][1], j[y][2]);
667: #endif
668: g[j[y][9]] |= (k & 1) << a;
669: g[j[y][10]] |= ((k >> 1) & 1) << a;
670: g[j[y][11]] |= ((k >> 2) & 1) << a;
671: g[j[y][12]] |= ((k >> 3) & 1) << a;
672: g[j[y][13]] |= ((k >> 4) & 1) << a;
673: g[j[y][14]] |= ((k >> 5) & 1) << a;
674: } // Restore Intersection Removal Candidate within Box unsolved 6 Cell positions
675: }
***** RJSOLBW5.CPP
658: } // Restore Intersection Removal Candidate within Line unsolved 6 Cell positions
659: }
660: else // Not Found Intersection Removal Candidate within Line unsolved 6 Cell positions
661: if ((g[j[y][9]] >> a) & 1 || (g[j[y][10]] >> a) & 1 ||
662: (g[j[y][11]] >> a) & 1 || (g[j[y][12]] >> a) & 1 ||
663: (g[j[y][13]] >> a) & 1 || (g[j[y][14]] >> a) & 1)
664: { // Found Intersection Removal Candidate within Box unsolved 6 Cell positions
665: int k = (g[j[y][9]] >> a) & 1 | ((g[j[y][10]] >> a) & 1) << 1 |
666: ((g[j[y][11]] >> a) & 1) << 2 | ((g[j[y][12]] >> a) & 1) << 3 |
667: ((g[j[y][13]] >> a) & 1) << 4 | ((g[j[y][14]] >> a) & 1) << 5;
668: // Backup Intersection Removal Candidate within Box unsolved 6 Cell positions
669: g[j[y][9]] &= ~(1 << a);
670: g[j[y][10]] &= ~(1 << a);
671: g[j[y][11]] &= ~(1 << a);
672: g[j[y][12]] &= ~(1 << a);
673: g[j[y][13]] &= ~(1 << a);
674: g[j[y][14]] &= ~(1 << a);
675: #ifdef RJ
676: printf ("%d) Found Box-Line Reduction Intersection Removal for Candidate %d at Cells %d %d %d\n",
677: y, a + 1, j[y][0], j[y][1], j[y][2]);
678: #endif
679: if (solve (p))
680: return 1;
681: #ifdef RJ
682: printf ("%d) Restore Box-Line Reduction Intersection Removal for Candidate %d at Cells %d %d %d\n",
683: y, a + 1, j[y][0], j[y][1], j[y][2]);
684: #endif
685: g[j[y][9]] |= (k & 1) << a;
686: g[j[y][10]] |= ((k >> 1) & 1) << a;
687: g[j[y][11]] |= ((k >> 2) & 1) << a;
688: g[j[y][12]] |= ((k >> 3) & 1) << a;
689: g[j[y][13]] |= ((k >> 4) & 1) << a;
690: g[j[y][14]] |= ((k >> 5) & 1) << a;
691: } // Restore Intersection Removal Candidate within Box unsolved 6 Cell positions
692: }
*****

***** RJSolBit.CPP
790: k += c;
791: printf ("%ld) Valid Sudoku # V%ld", ++t, ++y);
792: }
***** RJSOLBW5.CPP
807: k += c;
808: printf ("%ld) Valid Sudoku # V%ld", ++t, ++y);
809: }
*****

Updated on 20151117:

Hidden Text: Show

1. Lot of changes in comments.

2. Some more code beautifications.

3. Change the order of digit from descending to ascending order in b[512] array. Digit 8 missing in two elements 155 and 411 - Fixed.

4. Added Basic Fishes searching routine.

5. Remove unnecessary code:

Code: Select all

694:         if (B[g[w[r[p]][a]]] == 1)
695:           break;             // Found one Candidate assigned

Updated on 20151119:

Hidden Text: Show

Converted Basic Fishes routine as per Naked/Hidden Tuples routine.
Although, there is no significant change in speed, but now both routines' variables and structure are matched.

Updated on 20151120:

Hidden Text: Show

1. Fixed bug in Basic Fishes restore routine.

2. Applied immediate exit from restore all deduction strategies after first time found and reached dead end.
(Note: it helps to check whether restore routine is working correctly or not.)

R. Jamil

[rjamil]

Hi,

I am sharing herewith my latest Bitwise Sudoku Solver program source code for experts' comments / suggestions / criticisms.

Please look into separate pieces of modules in solve function for Naked/Hidden Singles/Tuples, Intersection Removals, Basic Fish, guesses and trial & error logic with optional debugging steps included.

I have modified the program to my level best in order to speed things up, coded as simple as possible and commented in order to understand each and every statement easily.

Hope to have received positive response from serious/senior Sudoku programmers.

R. Jamil
_________________
Updated 20151209:
In Hidden Single routine, in line # 358, 364 and 370, replace "if (B[K] == 1)" with "if (B[K])" statement.

Updated 2060112:
1. Discarded above mentioned update suggestion.

2. Remove " * 1000" from line # 991, 998, 1005 and 1014 for time calculation in seconds:
Old: c = (clock () - c) / CLOCKS_PER_SEC * 1000;
New: c = (clock () - c) / CLOCKS_PER_SEC;

[rjamil]

Hi all again,

I have modified my RJSolBit.cpp program based on what I understand from the guidelines provided by JasonLion and Champagne; and Zhouyundong_2012 respectively.

Main changes are as follows:
1. Added static int J[20] global array containing integer values from 1 to 20 (from right to left) bitwise positions.
2. In intersection removals routine, search candidates available in box-line cell positions as a bit instead of loop for each candidate from 1 to 9 and check if candidate exists in box-line cell positions. This also simplifies checking for existence/non-existence, backup, removal and restoration of candidate in box and line other cell positions respectively.
3. In basic fishes routine, introduce separate loop of 2 times for row and column wise each candidate from 1 to 9 searching. This replaces single loop of 18 times and line direction variable assigning 18 times.
4. Convert all occurrences of left and right bit shifting operations from intersection removals, basic fishes and solve cell position routines to either union with constants or inline condition function (condition ? true : false) where applicable.

R. Jamil

[rjamil]

Hi,

Surprised to see that my last modified program has been downloaded 5 times within short time.

However, a minor changes has also been made by myself in RJSolBit.cpp program.

In basic fishes routine, change variable X to single dimension array of 2, 3 or 4 elements for X-Wing, Sword Fish and Jelly Fish respectively in order to hold values for future restoration purpose. This will help to reduce the recalculation of the same each time and skip if no changes made in opposite line other cell positions at restoration time.

R. Jamil

[rjamil]

Hi,

I have modified my RJSolBit.cpp program from C++ language to C99 standard C language (RJSolBit.c) for easy convenience.

However, please note that I have reversed modification made in naked single and least candidate cell position search routine by reinstating count bitwise candidate array size to 513 element and added beyond acceptable bit count size as last element. This will definitely check first available empty cell position as naked single and/or least candidate available for guessing.

R. Jamil

Updated on 20160302:
Reinstate statement to check one candidate remain within affected 20 cell positions in order to rollback earlier that was withdrawn on 20151117 update:
In RJSolBit.c, replace line # from 914 to 919; and in RJSolBit.cpp, line # from 902 to 907 with 2 additional lines as follows:

Code: Select all

    for (++n[y], a = 0; a < 20; ++a)
      if (g[w[r[p]][a]] & J[s[r[p]] - 1])
      {
        if(B[g[w[r[p]][a]]] == 1)
          break;             // Found one Candidate assigned
        k |= J[a];           // Backup 20 affected Cell positions current Candidate
        g[w[r[p]][a]] &= ~J[s[r[p]] - 1];
      }                      // Remove current Candidate from 20 affected Cell positions

[rjamil]

Hi all,

Please note that, I now realized that my programs unnecessary taken steps after wrong guess. After investigating, it was revealed that I removed a check at the time of placing a clue and removing candidate from affected cell positions that was included before 20151117 update.

After implementing the above mentioned checking statements, here I am sharing the summary timings in seconds without debugging option included (my laptop configuration is mentioned below):

PG26855.txt:
Total Sudoku puzzle read : 26855
Total time for all puzzles : 52.018757
Average time per puzzle : 0.001937
Number of valid puzzles : 0
Time for valid puzzles : 0.000000
Average time per valid : 0.000000
Number of invalid puzzles : 0
Time for invalid puzzles : 0.000000
Average time per invalid : 0.000000
Number of solved puzzles : 26855
Time for solved puzzles : 52.018757
Average time per solved : 0.001937
Number of unsolved puzzle : 0
Time for unsolved puzzles : 0.000000
Average time per unsolved : 0.000000

17 clue 49157 puzzles:
Total Sudoku puzzle read : 49157
Total time for all puzzles : 19.536041
Average time per puzzle : 0.000397
Number of valid puzzles : 0
Time for valid puzzles : 0.000000
Average time per valid : 0.000000
Number of invalid puzzles : 0
Time for invalid puzzles : 0.000000
Average time per invalid : 0.000000
Number of solved puzzles : 49157
Time for solved puzzles : 19.536041
Average time per solved : 0.000397
Number of unsolved puzzle : 0
Time for unsolved puzzles : 0.000000
Average time per unsolved : 0.000000

R. Jamil
______________________________________________________
Toshiba Satellite C855D
AMD E-450 APU with Radeon (tm) HD Graphics 1.65 GHz
4 GB RAM
Windows 10 Pro, 64-bit operating system, x64 based processor

[rjamil]

Hi,

I am pleased to announce the release of my newest Bitwise Sudoku solver program source code written in C and C++ languages.

Added:
- XY-Wing Type 1 (like X-Wing) and Type 2 (Box-Line)
- XYZ-Wing
- Debugging

And lot of minor improvements in various area.

Note: Just look at XY-Wing Type 2 and XYZ-Wing routine, how reference table is used efficiently.

R. Jamil

20161030:
Bug fix in XY-Wings Type 1 routine.
In RJSolBit.cpp line number 916 and RJSolBit.c line number 931 replace as follows:
Old: K[3] = K[1] - y + (y < 27 ? 27 : 54);
New: K[3] = K[2] - K[0] + K[1];

20161111:
Tweak in XY-Wings Type 2 and XYZ-Wings routine.
In RJSolBit.cpp line number 950 and RJSolBit.c line number 966 replace as follows:
Old: for (a = 0; a < q; ++a)
New: for (a = p; a < q; ++a)

20161119:
Tweak in XY-Wings Type 2 and XYZ-Wings routine.
In RJSolBit.cpp line number 954 and RJSolBit.c line number 970 replace as follows:
Old: if (B[g[A]] < 2 || B[g[A]] > 3)
New: if (B[g[A]] > 3)

Corrected line number of RJSolBit.c in 20161111 tweak from 963 to 966.

[rjamil]

Hi again,

Find RJSolBit program in C and C++ language.

Recent changes include:
- Added Guess depth count (although my solver program using recursive call after each and every move)
- Remove Bit position array by using bit shifting instead
- Added XYZ-Wing Hybrid strategy
- Corrected debugging option 4, i.e., printing pencil mark after each step

R. Jamil

[rjamil]

Hi all again,

Find latest RJSolBit.cpp and RJSolBit.c contained:
Added:
Unit zero state check;
XYZ-Wings Hybrid Type 2;

Updated:
Seprated Naked and Hidden single search routine that was merged on 20151026;
Match variables of XY-Wings Type 2, XYZ-Wings and XYZ-Wings Hybrid search routine with XY-Wings Type 1 search routine;

Removed:
Peer cell values zero check on naked single, hidden single and guess that was removed on 20151117 and reinstated on 20160302.

R. Jamil

[rjamil]

Hi all,

Find attached herewith latest RJSolBit.cpp and RJSolBit.c program included:
Added:
In summary at last containing Total solved without guess, Maximum guess and depth;
WXYZ-Wings Type 1, 2a, 2b and 3;

Updated:
Match variables of Intersection removal routine with other routines (variable a and y interchanged);
Changed XY-Wings Type 1 routine to search each Pivot cell from unsolved cells.

R. Jamil

[rjamil]

Hi all again,

Wish to share my latest RJSolver.c and RJSolver.cpp Sudoku solver program.

Only WXYZ-Wings routines have been updated. Now they catch WXYZ-Wings patterns of one apex and three wings within apex 20 peers, row-column and box-line wise, and having any number of clues between 2 to 4 in each cell. WXYZ-Wings now included Type 1 (8 exemplars, 1 elimination), Type 2a (14 exemplars, up to 5 eliminations), Type 2b (6 exemplars, up to 2 eliminations), Type 3 (20 exemplars, up to 2 eliminations), Type 4a (2 exemplars, up to 4 eliminations) and Type 4b (4 exemplars, 1 elimination).

Nothing change in rest of the routines except whole program optimized for speed.

R. Jamil