The New Sudoku Players' Forum

[rjamil]

Hi Blue,

I have checked both your given puzzles with my routine and it catches Naked pair and triple as mentioned in your post respectively.

Also googling and found one more example of Hidden quad, my routine detect the same:

Code: Select all

005407810000102700001056002107000408402001009806000201600010000013908000004703100

However as per this site's first hidden quad example, my routine is unable to detect hidden quad:

Code: Select all

650087024000649050040025000570438061000501000310902085000890010000213000130750098

I have included step-by-step debugging for solving technics in to my Bitwise Sudoku solver program. Here is the output of above mentioned puzzle:

Code: Select all

650087024000649050040025000570438061000501000310902085000890010000213000130750098
31) Found Naked pair 73 at unit 20 at Cell 17 25
1) Trial and Error from least digits 31 at Cell 3
0) Apply Digit 1 from 31 at Cell 3
2) Found Naked Single 9 at Cell 6
1) Apply Digit 9 from 9 at Cell 6
2) Found Naked Single 3 at Cell 2
2) Apply Digit 3 from 3 at Cell 2
10) Found Naked Single 3 at Cell 21
3) Apply Digit 3 from 3 at Cell 21
12) Found Naked Single 7 at Cell 25
4) Apply Digit 7 from 7 at Cell 25
7) Found Naked Single 3 at Cell 17
5) Apply Digit 3 from 3 at Cell 17
13) Found Naked Single 6 at Cell 26
6) Apply Digit 6 from 6 at Cell 26
15) Found Naked Single 2 at Cell 33
7) Apply Digit 2 from 2 at Cell 33
14) Found Naked Single 9 at Cell 29
8) Apply Digit 9 from 9 at Cell 29
36) Found Naked Single 4 at Cell 70
9) Apply Digit 4 from 4 at Cell 70
21) Found Naked Single 3 at Cell 43
10) Apply Digit 3 from 3 at Cell 43
37) Found Naked Single 7 at Cell 71
11) Apply Digit 7 from 7 at Cell 71
22) Found Naked Single 9 at Cell 44
12) Apply Digit 9 from 9 at Cell 44
31) Found Naked Single 2 at Cell 62
13) Apply Digit 2 from 2 at Cell 62
27) Found Naked Single 6 at Cell 55
14) Apply Digit 6 from 6 at Cell 55
29) Found Naked Single 4 at Cell 59
15) Apply Digit 4 from 4 at Cell 59
26) Found Naked Single 7 at Cell 54
16) Apply Digit 7 from 7 at Cell 54
28) Found Naked Single 5 at Cell 56
17) Apply Digit 5 from 5 at Cell 56
30) Found Naked Single 3 at Cell 60
18) Apply Digit 3 from 3 at Cell 60
34) Found Naked Single 8 at Cell 65
19) Apply Digit 8 from 8 at Cell 65
32) Found Naked Single 9 at Cell 63
20) Apply Digit 9 from 9 at Cell 63
20) Rollback Digit 9 from 0 at Cell 63
19) Rollback Digit 8 from 0 at Cell 65
18) Rollback Digit 3 from 0 at Cell 60
17) Rollback Digit 5 from 0 at Cell 56
16) Rollback Digit 7 from 0 at Cell 54
15) Rollback Digit 4 from 0 at Cell 59
14) Rollback Digit 6 from 0 at Cell 55
13) Rollback Digit 2 from 0 at Cell 62
12) Rollback Digit 9 from 0 at Cell 44
11) Rollback Digit 7 from 0 at Cell 71
10) Rollback Digit 3 from 0 at Cell 43
9) Rollback Digit 4 from 0 at Cell 70
8) Rollback Digit 9 from 0 at Cell 29
7) Rollback Digit 2 from 0 at Cell 33
6) Rollback Digit 6 from 0 at Cell 26
5) Rollback Digit 3 from 0 at Cell 17
4) Rollback Digit 7 from 0 at Cell 25
3) Rollback Digit 3 from 0 at Cell 21
2) Rollback Digit 3 from 0 at Cell 2
1) Rollback Digit 9 from 0 at Cell 6
0) Rollback Digit 1 from 0 at Cell 3
0) Apply Digit 3 from 31 at Cell 3
3) Found Naked Single 1 at Cell 21
1) Apply Digit 1 from 1 at Cell 21
2) Trial and Error from least digits 91 at Cell 2
2) Apply Digit 1 from 91 at Cell 2
3) Found Naked Single 9 at Cell 6
3) Apply Digit 9 from 9 at Cell 6
6) Found Naked Single 6 at Cell 26
4) Apply Digit 6 from 6 at Cell 26
7) Found Naked Single 2 at Cell 33
5) Apply Digit 2 from 2 at Cell 33
8) Found Naked Single 9 at Cell 29
6) Apply Digit 9 from 9 at Cell 29
11) Found Naked Single 7 at Cell 71
7) Apply Digit 7 from 7 at Cell 71
9) Found Naked Single 4 at Cell 70
8) Apply Digit 4 from 4 at Cell 70
11) Found Naked Single 3 at Cell 17
9) Apply Digit 3 from 3 at Cell 17
11) Found Naked Single 7 at Cell 25
10) Apply Digit 7 from 7 at Cell 25
11) Found Naked Single 3 at Cell 43
11) Apply Digit 3 from 3 at Cell 43
12) Found Naked Single 9 at Cell 44
12) Apply Digit 9 from 9 at Cell 44
13) Found Naked Single 2 at Cell 62
13) Apply Digit 2 from 2 at Cell 62
14) Found Naked Single 6 at Cell 55
14) Apply Digit 6 from 6 at Cell 55
15) Found Naked Single 4 at Cell 59
15) Apply Digit 4 from 4 at Cell 59
16) Found Naked Single 7 at Cell 54
16) Apply Digit 7 from 7 at Cell 54
17) Found Naked Single 5 at Cell 56
17) Apply Digit 5 from 5 at Cell 56
18) Found Naked Single 3 at Cell 60
18) Apply Digit 3 from 3 at Cell 60
19) Found Naked Single 8 at Cell 65
19) Apply Digit 8 from 8 at Cell 65
20) Found Naked Single 9 at Cell 63
20) Apply Digit 9 from 9 at Cell 63
20) Rollback Digit 9 from 0 at Cell 63
19) Rollback Digit 8 from 0 at Cell 65
18) Rollback Digit 3 from 0 at Cell 60
17) Rollback Digit 5 from 0 at Cell 56
16) Rollback Digit 7 from 0 at Cell 54
15) Rollback Digit 4 from 0 at Cell 59
14) Rollback Digit 6 from 0 at Cell 55
13) Rollback Digit 2 from 0 at Cell 62
12) Rollback Digit 9 from 0 at Cell 44
11) Rollback Digit 3 from 0 at Cell 43
10) Rollback Digit 7 from 0 at Cell 25
9) Rollback Digit 3 from 0 at Cell 17
8) Rollback Digit 4 from 0 at Cell 70
7) Rollback Digit 7 from 0 at Cell 71
6) Rollback Digit 9 from 0 at Cell 29
5) Rollback Digit 2 from 0 at Cell 33
4) Rollback Digit 6 from 0 at Cell 26
3) Rollback Digit 9 from 0 at Cell 6
2) Rollback Digit 1 from 0 at Cell 2
2) Apply Digit 9 from 91 at Cell 2
3) Found Naked Single 1 at Cell 6
3) Apply Digit 1 from 1 at Cell 6
6) Found Naked Single 2 at Cell 29
4) Apply Digit 2 from 2 at Cell 29
5) Found Naked Single 9 at Cell 33
5) Apply Digit 9 from 9 at Cell 33
31) Found Naked Single 8 at Cell 15
6) Apply Digit 8 from 8 at Cell 15
22) Found Naked Single 2 at Cell 10
7) Apply Digit 2 from 2 at Cell 10
14) Found Naked Single 6 at Cell 55
8) Apply Digit 6 from 6 at Cell 55
15) Found Naked Single 4 at Cell 59
9) Apply Digit 4 from 4 at Cell 59
21) Found Naked Single 7 at Cell 9
10) Apply Digit 7 from 7 at Cell 9
15) Found Naked Single 3 at Cell 17
11) Apply Digit 3 from 3 at Cell 17
16) Found Naked Single 2 at Cell 54
12) Apply Digit 2 from 2 at Cell 54
13) Found Naked Single 7 at Cell 62
13) Apply Digit 7 from 7 at Cell 62
14) Found Naked Single 4 at Cell 70
14) Apply Digit 4 from 4 at Cell 70
16) Found Naked Single 2 at Cell 44
15) Apply Digit 2 from 2 at Cell 44
17) Found Naked Single 5 at Cell 56
16) Apply Digit 5 from 5 at Cell 56
18) Found Naked Single 3 at Cell 60
17) Apply Digit 3 from 3 at Cell 60
21) Found Naked Single 7 at Cell 25
18) Apply Digit 7 from 7 at Cell 25
21) Found Naked Single 3 at Cell 43
19) Apply Digit 3 from 3 at Cell 43
22) Found Naked Single 6 at Cell 71
20) Apply Digit 6 from 6 at Cell 71
27) Found Naked Single 8 at Cell 18
21) Apply Digit 8 from 8 at Cell 18
22) Found Naked Single 9 at Cell 63
22) Apply Digit 9 from 9 at Cell 63
26) Found Naked Single 4 at Cell 36
23) Apply Digit 4 from 4 at Cell 36
26) Found Naked Single 6 at Cell 47
24) Apply Digit 6 from 6 at Cell 47
26) Found Naked Single 7 at Cell 49
25) Apply Digit 7 from 7 at Cell 49
26) Found Naked Single 4 at Cell 51
26) Apply Digit 4 from 4 at Cell 51
29) Found Naked Single 1 at Cell 11
27) Apply Digit 1 from 1 at Cell 11
30) Found Naked Single 8 at Cell 38
28) Apply Digit 8 from 8 at Cell 38
29) Found Naked Single 7 at Cell 65
29) Apply Digit 7 from 7 at Cell 65
30) Found Naked Single 9 at Cell 37
30) Apply Digit 9 from 9 at Cell 37
31) Found Naked Single 9 at Cell 26
31) Apply Digit 9 from 9 at Cell 26
32) Found Naked Single 7 at Cell 42
32) Apply Digit 7 from 7 at Cell 42
33) Found Naked Single 8 at Cell 64
33) Apply Digit 8 from 8 at Cell 64
34) Found Naked Single 6 at Cell 40
34) Apply Digit 6 from 6 at Cell 40
35) Found Naked Single 5 at Cell 69
35) Apply Digit 5 from 5 at Cell 69
36) Found Naked Single 3 at Cell 20
36) Apply Digit 3 from 3 at Cell 20
37) Found Naked Single 6 at Cell 24
37) Apply Digit 6 from 6 at Cell 24
38) Found Naked Single 4 at Cell 74
38) Apply Digit 4 from 4 at Cell 74
39) Found Naked Single 6 at Cell 77
39) Apply Digit 6 from 6 at Cell 77
40) Found Naked Single 2 at Cell 78
40) Apply Digit 2 from 2 at Cell 78
6) 659387124721649853843125679572438961498561732316972485265894317987213546134756298 # S6 # N40 # H0 # 0.000000

R. Jamil

[David P Bird]

Original post temporarily withdrawn for review

As I originally posted 'Thinking about how my code could be patched following Blue's findings, it struck me that most of the time a tuple search will fail so the main objective should be to optimise a complete unsuccessful search, not to find a hit as quickly as possible.'

After I went to bed I realised that in the following code I posted I had left out the same trap that I omitted in my earlier pseudo-code description, so I got up and pulled my post. Unfortunately looking at the extra code required for trapping triples and quads, the time saving over 4 nested loops would be minimal.

DPB
.

[rjamil]

Hi,

After completing Naked/Hidden tuples search routine by enumerating all possible combinations of each tuple then loop pair, triplet and quad separately for each unit, noticed that there are some extra unnecessary iterations found for which I worked out and overcome by skipping number of unnecessary iterations at the same time.

Here I am sharing the skipping portion of final routine for separate tuple as follows:

For pair:

Code: Select all

      if(!k[T[a][0]] || !k[T[a][1]])
      {                      // Skip empty Cell Candidate or filled Cell position
        if(!k[T[a][0]])
          a += 7 - T[a][0];
        continue;
      }

For triplet:

Code: Select all

      if(!k[T[a][0]] || !k[T[a][1]] || !k[T[a][2]])
      {                      // Skip empty Cell Candidate or filled Cell position
        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;
      }

For quad:

Code: Select all

      if(!k[T[a][0]] || !k[T[a][1]] || !k[T[a][2]] || !k[T[a][3]])
      {                      // Skip empty Cell Candidate or filled Cell position
        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;
      }

Now, I realized that N-loop for N-tuple routine will have draw back for searching unit other cell positions. It also need enumerated tuple array. However, need additional effort to map the enumerated unit for tuple.

Complete source code has been shared on separate post.

R. Jamil

[David P Bird]

Today I've considered alternative screening ideas to avoid making a full scan when there a 9 unresolved cells, and have a couple of contenders to explore further. However it may take some time as there's a heavy match program for the Rugby World Cup over this week end which requires my attention.

This is the easiest to explain.
In the (digits)house,position grid look for naked sets of digits in the cells with <= N\2 candidates where N = the number of unresolved cells.
In the alternative (positions)house,digit representations look for naked sets of positions for digits that occupy <= N\2 cells (in the standard work grid these will be hidden sets).

DPB
.

[rjamil]

Hi David,

Keep watching Rugby World Cup matches and have a nice weekend.

In the (digits)house,position grid look for naked sets of digits in the cells with <= N\2 candidates where N = the number of unresolved cells.
In the alternative (positions)house,digit representations look for naked sets of positions for digits that occupy <= N\2 cells (in the standard work grid these will be hidden sets).

As per my understanding, it is easier to search Naked for more than quad as compared to search Hidden triple or above. So, I searched Hidden N as complementary of Naked 9-N as follows:

Searching Naked as, for each combination of cells in one unit, if number of candidates (by applying bitwise OR between cells) is equal to number of cells then that number's Naked found. For example, if only 3 candidates exist in 3 cells then Naked triplet found. However, we need to further check, for elimination purpose that if at least one or more number of candidates exist within other cells' candidates (by applying bitwise OR between other cells) with bitwise AND operator.

Similarly, searching Hidden as, for each combination of cells In one unit, take number of candidates (solved and unsolved) for other cells in one unit by applying bitwise OR, then take one's complement by applying bitwise NOT will give remaining candidates for that combination of cells. If remaining candidates is equal to number of cells then that number's Hidden found. However, we need to further check, for elimination purpose that if number of candidates (by applying bitwise OR between cells) is greater than number of cells. (Is this the best way to search for hidden tuples?)

Hope that the above explanation is clear to understand.

Regards,
R. Jamil

[David P Bird]

Rizwam it seems you understand my points but to make everything as clear as possible here is an example row:

Code: Select all

    *-----------------------*-----------------------*------------------------*
    | 2356   135    12      | 13     569    569     | 78     1234568 1245678 |
    *-----------------------*-----------------------*------------------------*

      C1     C2*    C3*       C4*    C5     C6        C7*    C8     C9
----*-----------------------*-----------------------*------------------------*-------
D1  | .      x      x       | x      .      .       | .      x       x       | 23489 
D2  | x      .      x       | .      .      .       | .      x       x       | 1389 
D3  | x      x      .       | x      .      .       | .      x       .       | 1248 
----*-----------------------*-----------------------*------------------------*-------
D4* | .      .      .       | .      .      .       | .     <x>     <x>      | 89   
D5  | x      x      .       | .      x      x       | .      x       x       | 125689
D6  | x      .      .       | .      x      x       | .      x       x       | 15689
----*-----------------------*-----------------------*------------------------*-------
D7* | .      .      .       | .      .      .       |<x>     .      <x>      | 79     
D8* | .      .      .       | .      .      .       |<x>    <x>     <x>      | 789   
D9* | .      .      .       | .      x      x       | .      .       .       | 56   
----*-----------------------*-----------------------*------------------------*-------
    | 2356   135    12      | 13     569    569     | 78     1234568 1245678 |

The table is digit/column grid for the row showing where each digit appears as a candidate.
At the bottom is the how the row appears in the standard work grid (data set1).
In this form there is a hidden triple (d478)c789 with a naked sextet (d123569)c123456
On the right is how the columns holding each digit would appear in the alternative representation (data set2).
Here the equivalent sets become a naked triple (c789)d478 and a hidden sextet(c123456)d123569

The method I'm suggesting is to look for naked sets of size 1 to 4 in each data set.
Those that are found in data set 2 can then be translated into hidden sets in the standard data set 1 format.
There is therefore no need to write different search code for naked and hidden sets.

If 2 cells are known the search for naked quads isn't needed as if one exists it will be quicker to find it's hidden triple complement.

If you have studied fish eliminations, you will recognise that the entries marked <x> make a 3-Fish pattern.

When making a search for a naked triple it is obvious that member cells must hold 2 or 3 candidates. The search can therefore be restricted to c2347 and d123578 (the digits in these columns).
In the other direction the locked digits in a hidden triple must occupy 2 or 3 cells which limits the search to d4789 and c56789 (the columns holding these digits).
You must judge if these checks will save time though, and that will depend on your data structure.

Once the eliminations from this hit have been made the row will hold two complementary naked sets. When this happens there is no reason to report these sets again as there are no further eliminations to make. This is important because any elimination in a cell may cause a locked set to be made in the houses that contain it and these tests must be repeated.

David
.

[rjamil]

Hi,

Similarly, searching Hidden as, for each combination of cells In one unit, take number of candidates (solved and unsolved) for other cells in one unit by applying bitwise OR, then take one's complement by applying bitwise NOT will give remaining candidates for that combination of cells. If remaining candidates is equal to number of cells then that number's Hidden found. However, we need to further check, for elimination purpose that if number of candidates (by applying bitwise OR between cells) is greater than number of cells. (Is this the best way to search for hidden tuples?)

Please allow me to answer my own question, i.e., NO. I have one more suggestion to search for hidden tuples as follows:

Let Unit means 9 cells either row or column or box wise (Houses), tuple cells means those cells in which tuple candidates are found, other cells means remaining unit's cells (or other than tuple cells in unit). Also, tuple cell candidates can be calculated with bitwise OR between tuple cells; and other cell candidates can be calculated with bitwise OR between other cells.

Searching Hidden tuples as, for each combination of tuple cells in one unit, tuple candidates can be calculated with bitwise AND between tuple cell candidates and (bitwise XOR between tuple cell candidates and other cell candidates). (However, is there a better way to search for Hidden tuples?)

Rizwan it seems you understand my points ...

I think maintaining separate Digit-Unit is data redundancy and time consuming for maintaining the same.

However, as per my logic for Hidden tuple, I suggest if unit's candidates are stored in to an array then applying my logic for Naked and Hidden tuples are just one assignment and one checking respectively.

Pseudo code as follows:

Code: Select all

Dim Tuples(1 To 246, 1 To 9) As Integer ' pre-define tuple combinations
Dim B(0 to 512) As Integer ' pre-define bit-count
Dim Unit(1 To 9) As Integer
Dim k As Integer
Dim a As Integer
Unit(1) = 2356
Unit(2) = 135
Unit(3) = 12
Unit(4) = 13
Unit(5) = 569
Unit(6) = 569
Unit(7) = 78
Unit(8) = 1234568
Unit(9) = 1245678

' For checking Naked/Hidden pair routine
For a = 1 To 36
  k = (Unit(1) Or Unit(2)) And ((Unit(1) Or Unit(2)) XOR (Unit(3) Or Unit(4) Or Unit(5) Or Unit(6) Or Unit(7) Or Unit(8) Or Unit(9)))
  If B(k) = 2 And B(Unit(1) Or Unit(2)) = 2 Then
    ' Naked pair found
  ElseIf B(k) = 2 And B(Unit(1) Or Unit(2)) > 2 Then
    ' Hidden pair found
  End If
Next a

Please note that the above pseudo code is hard coded for fixed first combination of pair combination within unit. I left applying Tuple combination array usage intentionally. I can't check my pseudo code as well.

R. Jamil
__________________________________________
Don’t see others doing better than you,
Beat your own records everyday because,
Success is a fight between YOU & YOURSELF !!!!

[David P Bird]

Rizwan

I think maintaining separate Digit-Unit is data redundancy and time consuming for maintaining the same.

Yes, there is truth in this. I admit that presenting the source data in another format to simplify the bitwise operations has a cost and will only be worthwhile if the later savings are large enough. As my VB code is for a spreadsheet helper and your C++ code is for a solver, our cost/savings comparisons are different, but before you make a final decision you should consider if the alternative formats would make any of the other procedures you will need easier.

I can see the intentions of your pseudo code which looks OK but it will be quite a job to create the loop structure to cover pairs, triples and quads!

Now that I believe you understand my approach I feel I've reached the limit of how far I can help you. Perhaps someone who has written their own C++ solver can advise you further.

Good luck with the rest of your project.

David

[rjamil]

Hi,

While I am waiting for any response regarding my routine to check Naked/Hidden tuples, I am thinking to speed up further by introducing to skip minimum unsolved cells per unit.

What are the minimum number of unsolved cells in unit required to check Naked/Hidden Tuples? 3 for pair, 5 for triplet and 7 for quad?

I have implemented the same in my solver but not sure whether it works or miss something sometime.

Regards,
R. Jamil

[JasonLion]

Searching for naked tuples, you can also ignore cells with more than N pencil marks; where N is the size of the largest tuple you are looking for (typically 4).

[rjamil]

Hi Jason,

Searching for naked tuples, you can also ignore cells with more than N pencil marks; where N is the size of the largest tuple you are looking for (typically 4).

Thanks for the great idea. How about ignoring cells with more than 2 pencil marks for naked pairs, 3 for naked triplets and 4 for naked quads?

However, searching both naked and hidden tuple within one loop routine, it is either almost impossible to implement or cause performance degradation.

Regards,
R. Jamil

[Pat]

What are the minimum number of unsolved cells in unit required to check Naked/Hidden Tuples? 3 for pair, 5 for triplet and 7 for quad?

4,6,8

[rjamil]

Hi Pat,

Thanks for the correction, i.e., 4,6,8 instead of 3,5,7.

However, I have already implemented the same but need confirmation from expert.

R. Jamil

[dobrichev]

Below is the most compact code for subsets I have ever read.

Hidden Text: Show

Code: Select all

/****************************************************************\
**  BB_Sudoku  Bit Based Sudoku Solver                          **
\****************************************************************/

/****************************************************************\
**  (c) Copyright Brian Turner, 2008-2009.  This file may be    **
**      freely used, modified, and copied for personal,         **
**      educational, or non-commercial purposes provided this   **
**      notice remains attached.                                **
\****************************************************************/

// G - Grid data structure
//       This contains everything needed for backtracking.
//       The larger this gets, the slower backtracking will be
//         since the entire structure is copied.
struct Grid_Type
{ int          CellsLeft;  // Cells left to solve
  unsigned short Grid[81];   // Possibilities left for each cell
  unsigned short Grp[27];    // Values found in each group
} G[64];

// Solution Grid, which will contain the answer after the puzzle is solved
unsigned int SolGrid[81];

// Naked Singles FIFO stack - new singles found are stored here before
char  SingleCnt = 0;
char  SinglePos[128];
//unsigned int SingleVal[128];
unsigned short SingleVal[128];
#define PushSingle(p, b) { SinglePos[SingleCnt] = p; SingleVal[SingleCnt] = b; SingleCnt++; Changed = 1; }


// Changed Flags
int  Changed;          // Flag to indicate Grid has changed
char ChangedGroup[27]; // Marks which groups have changed
char ChangedLC[27];
int  SingleGroup[27];
//#define MarkChanged(x) { ChangedGroup[C2Grp[x][2]] = ChangedGroup[C2Grp[x][1]] = ChangedGroup[C2Grp[x][0]] = Changed = 1; }
#define MarkChanged(x) { ; }


// Guess structure
char GuessPos[128];
int  GuessVal[128];
int  OneStepP[81], OneStepI;


// Key global variables used throughout the solving
long   PuzzleCnt = 0;    // Total puzzles tested
long   SolvedCnt = 0;    // Total puzzles solved
int    PuzSolCnt;        // Solutions for a single puzzle
int    No_Sol;           // Flag to indicate there is no solution possible
int    PIdx;             // Position Index, used for guessing and backtracking


// Debug stats
int  SCnt  = 0,  HCnt  = 0, GCnt  = 0, LCCnt  = 0, SSCnt  = 0, FCnt  = 0, OneCnt  = 0, TwoCnt  = 0;
long TSCnt = 0,  THCnt = 0, TGCnt = 0, TLCCnt = 0, TSSCnt = 0, TFCnt = 0, TOneCnt = 0, TTwoCnt = 0;
int  MaxDepth = 0, Givens = 0;


// forward procedure declarations
       int  DecodePuzzleString (int ret_puz, char* buffer);
inline void InitGrid ();
//       void ProcessInitSingles (void);
       void ProcessSingles (void);
inline void FindHiddenSingles (void);
       void FindLockedCandidates (void);
       void FindSubsets (void);
       void FindFishies (void);
       void DoStep (int doing_2_step, int use_methods);
inline void MakeGuess (void);

..............

/*****************\
**  FindSubsets  ************************************************\
**                                                              **
**    FindSubsets will find all disjoint subsets (Naked/Hidden  **
**    Pairs/Triples/Quads).  While this reduces the solving     **
**    time on some puzzles, and reduces the numbers of guesses  **
**    by around 18%, the overhead increases solving time for    **
**    general puzzles by 100% (doubling the time).              **
**                                                              **
\****************************************************************/
void FindSubsets (void)
{
  int i, g, p, m, t[8], v[8];

  for (g = 0; g < 27; g++)
  { if (Changed) break;
    m = 7 - NSet[G[PIdx].Grp[g]];
    if (m < 2) continue;
    p = 1; t[1] = -1;

    while(p > 0)
    { t[p]++;
      if (t[p] == 9) { p--; continue; }
      if (p == 1)
      { v[1] = G[PIdx].Grid[Group[g][t[p]]];
        if ((!v[1]) || (NSet[v[1]] > m)) continue;
        p++; t[2] = t[1]; continue;
      }
      if (!G[PIdx].Grid[Group[g][t[p]]]) continue;
      v[p] = v[p-1] | G[PIdx].Grid[Group[g][t[p]]];
      if (NSet[v[p]] > m) continue;
      if (NSet[v[p]] == p)
      { for (i = 0; i < 9; i++)
          if ((G[PIdx].Grid[Group[g][i]] & ~v[p]) && (G[PIdx].Grid[Group[g][i]] & v[p]))
          { G[PIdx].Grid[Group[g][i]] &= ~v[p];
            if (B2V[G[PIdx].Grid[Group[g][i]]])
              PushSingle(Group[g][i], G[PIdx].Grid[Group[g][i]]);
            MarkChanged(Group[g][i]);
          }
        p = 1;
        continue;
      }
      if (p < m) { p++; t[p] = t[p-1]; }
    }
  }
}


[rjamil]

Hi Dobrichev,

It seems to me that I have coded Naked/Hidden tuple checking condition exactly the same way as written in bb_sudoku Solver by Brian Turner.

However, bb_sudoku V1.0 is, no doubt, a complete optimized and generic coding.

Edited on 20151018:
I have carefully compared both bb_sudoku and my RJSolBit program for Naked/Hidden tuple routine (source code). Here is outcome:

Hidden Text: Show

Code: Select all

/*****************\
**  FindSubsets  ************************************************\
**                                                              **
**    FindSubsets will find all disjoint subsets (Naked/Hidden  **
**    Pairs/Triples/Quads).  While this reduces the solving     **
**    time on some puzzles, and reduces the numbers of guesses  **
**    by around 18%, the overhead increases solving time for    **
**    general puzzles by 100% (doubling the time).              **
**                                                              **
\****************************************************************/
void FindSubsets (void)
{
  int i,
      g,
      p,
      m,
      t[8],
      v[8];

  for (g = 0; g < 27; g++)                       for (y = 0; y < 27; ++y)
  {                                              {
    if (Changed)
      break;
    m = 7 - NSet[G[PIdx].Grp[g]];                  k[9] = (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)};
    if (m < 2)                                     if (k[9] < 4)
      continue;                                      continue;
    p = 1;
    t[1] = -1;

    while(p > 0)                                   for (a = 0; a < 36; ++a)
    {                                              {
      t[p]++;                                      for (; a < 120; ++a)
      if (t[p] == 9)                               {
      {                                            for (; a < 246; ++a)
        p--;                                       {
        continue;                                  // separate loop for pair/triplet/quad
      }                                            // ^
      if (p == 1)                                  // ^
      {                                            // ^
        v[1] = G[PIdx].Grid[Group[g][t[p]]];         int k[0..8] = {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]],
        if ((!v[1]) || (NSet[v[1]] > m))             if (!k[T[a][0]] || !k[T[a][1]])
          continue;                                  {
        p++;                                           if (!k[T[a][0]])
        t[2] = t[1];                                     a += 7 - T[a][0];
        continue;                                      continue;
      }                                              }
      if (!G[PIdx].Grid[Group[g][t[p]]])             // ^
        continue;                                    // ^
      v[p] = v[p-1] | G[PIdx].Grid[Group[g][t[p]]];  int K = k[T[a][0]] | k[T[a][1]];
      if (NSet[v[p]] > m)
        continue;
      if (NSet[v[p]] == p)                           if (B[K] == 2 &&
      {                                              // v
        for (i = 0; i < 9; i++)                      // v
          if ((G[PIdx].Grid[Group[g][i]] & ~v[p])                     B[k[T[a][0]] | k[T[a][1]]] > 2)
            && (G[PIdx].Grid[Group[g][i]] & v[p]))                    K & (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]]))
          {                                          {
            G[PIdx].Grid[Group[g][i]] &= ~v[p];        g[l[y][T[a][2/3/4..8]]] &= ~K; // for Naked pair/triplet/quad
                                                       K &= K ^ (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]]);
                                                       g[l[y][T[a][0..1/2/3]]] &= K; // for Hidden pair/triplet/quad
            if (B2V[G[PIdx].Grid[Group[g][i]]])
              PushSingle(Group[g][i], G[PIdx].Grid[Group[g][i]]);
            MarkChanged(Group[g][i]);
          }                                          }
          p = 1;
          continue;
      }
      if (p < m)
      {
        p++;
        t[p] = t[p-1];
      }
    }
  }
}

My routine store few variables for backtracking purpose as compared with Brian Turner's routine, which store whole board even when just few cells changed.

Edited on 20151019:
After I compared my program with bb_sudoku for Naked/Hidden tuple, I concluded that the bb_sudoku routine does not check Hidden tuple at all. It searches Naked pair, triplet, quadruple, quintuple, sextuple and septuplet instead of Naked and Hidden pair, triplet, quadruple. Therefore, my claim still stands.

Regards,
R. Jamil