## What if Naked pair/triplet found within chute

Programs which generate, solve, and analyze Sudoku puzzles

### Re: What if Naked pair/triplet found within chute

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
`65008702400064905004002500057043806100050100031090208500089001000021300013075009831) Found Naked pair 73 at unit 20 at Cell 17 251) Trial and Error from least digits 31 at Cell 30) Apply Digit 1 from 31 at Cell 32) Found Naked Single 9 at Cell 61) Apply Digit 9 from 9 at Cell 62) Found Naked Single 3 at Cell 22) Apply Digit 3 from 3 at Cell 210) Found Naked Single 3 at Cell 213) Apply Digit 3 from 3 at Cell 2112) Found Naked Single 7 at Cell 254) Apply Digit 7 from 7 at Cell 257) Found Naked Single 3 at Cell 175) Apply Digit 3 from 3 at Cell 1713) Found Naked Single 6 at Cell 266) Apply Digit 6 from 6 at Cell 2615) Found Naked Single 2 at Cell 337) Apply Digit 2 from 2 at Cell 3314) Found Naked Single 9 at Cell 298) Apply Digit 9 from 9 at Cell 2936) Found Naked Single 4 at Cell 709) Apply Digit 4 from 4 at Cell 7021) Found Naked Single 3 at Cell 4310) Apply Digit 3 from 3 at Cell 4337) Found Naked Single 7 at Cell 7111) Apply Digit 7 from 7 at Cell 7122) Found Naked Single 9 at Cell 4412) Apply Digit 9 from 9 at Cell 4431) Found Naked Single 2 at Cell 6213) Apply Digit 2 from 2 at Cell 6227) Found Naked Single 6 at Cell 5514) Apply Digit 6 from 6 at Cell 5529) Found Naked Single 4 at Cell 5915) Apply Digit 4 from 4 at Cell 5926) Found Naked Single 7 at Cell 5416) Apply Digit 7 from 7 at Cell 5428) Found Naked Single 5 at Cell 5617) Apply Digit 5 from 5 at Cell 5630) Found Naked Single 3 at Cell 6018) Apply Digit 3 from 3 at Cell 6034) Found Naked Single 8 at Cell 6519) Apply Digit 8 from 8 at Cell 6532) Found Naked Single 9 at Cell 6320) Apply Digit 9 from 9 at Cell 6320) Rollback Digit 9 from 0 at Cell 6319) Rollback Digit 8 from 0 at Cell 6518) Rollback Digit 3 from 0 at Cell 6017) Rollback Digit 5 from 0 at Cell 5616) Rollback Digit 7 from 0 at Cell 5415) Rollback Digit 4 from 0 at Cell 5914) Rollback Digit 6 from 0 at Cell 5513) Rollback Digit 2 from 0 at Cell 6212) Rollback Digit 9 from 0 at Cell 4411) Rollback Digit 7 from 0 at Cell 7110) Rollback Digit 3 from 0 at Cell 439) Rollback Digit 4 from 0 at Cell 708) Rollback Digit 9 from 0 at Cell 297) Rollback Digit 2 from 0 at Cell 336) Rollback Digit 6 from 0 at Cell 265) Rollback Digit 3 from 0 at Cell 174) Rollback Digit 7 from 0 at Cell 253) Rollback Digit 3 from 0 at Cell 212) Rollback Digit 3 from 0 at Cell 21) Rollback Digit 9 from 0 at Cell 60) Rollback Digit 1 from 0 at Cell 30) Apply Digit 3 from 31 at Cell 33) Found Naked Single 1 at Cell 211) Apply Digit 1 from 1 at Cell 212) Trial and Error from least digits 91 at Cell 22) Apply Digit 1 from 91 at Cell 23) Found Naked Single 9 at Cell 63) Apply Digit 9 from 9 at Cell 66) Found Naked Single 6 at Cell 264) Apply Digit 6 from 6 at Cell 267) Found Naked Single 2 at Cell 335) Apply Digit 2 from 2 at Cell 338) Found Naked Single 9 at Cell 296) Apply Digit 9 from 9 at Cell 2911) Found Naked Single 7 at Cell 717) Apply Digit 7 from 7 at Cell 719) Found Naked Single 4 at Cell 708) Apply Digit 4 from 4 at Cell 7011) Found Naked Single 3 at Cell 179) Apply Digit 3 from 3 at Cell 1711) Found Naked Single 7 at Cell 2510) Apply Digit 7 from 7 at Cell 2511) Found Naked Single 3 at Cell 4311) Apply Digit 3 from 3 at Cell 4312) Found Naked Single 9 at Cell 4412) Apply Digit 9 from 9 at Cell 4413) Found Naked Single 2 at Cell 6213) Apply Digit 2 from 2 at Cell 6214) Found Naked Single 6 at Cell 5514) Apply Digit 6 from 6 at Cell 5515) Found Naked Single 4 at Cell 5915) Apply Digit 4 from 4 at Cell 5916) Found Naked Single 7 at Cell 5416) Apply Digit 7 from 7 at Cell 5417) Found Naked Single 5 at Cell 5617) Apply Digit 5 from 5 at Cell 5618) Found Naked Single 3 at Cell 6018) Apply Digit 3 from 3 at Cell 6019) Found Naked Single 8 at Cell 6519) Apply Digit 8 from 8 at Cell 6520) Found Naked Single 9 at Cell 6320) Apply Digit 9 from 9 at Cell 6320) Rollback Digit 9 from 0 at Cell 6319) Rollback Digit 8 from 0 at Cell 6518) Rollback Digit 3 from 0 at Cell 6017) Rollback Digit 5 from 0 at Cell 5616) Rollback Digit 7 from 0 at Cell 5415) Rollback Digit 4 from 0 at Cell 5914) Rollback Digit 6 from 0 at Cell 5513) Rollback Digit 2 from 0 at Cell 6212) Rollback Digit 9 from 0 at Cell 4411) Rollback Digit 3 from 0 at Cell 4310) Rollback Digit 7 from 0 at Cell 259) Rollback Digit 3 from 0 at Cell 178) Rollback Digit 4 from 0 at Cell 707) Rollback Digit 7 from 0 at Cell 716) Rollback Digit 9 from 0 at Cell 295) Rollback Digit 2 from 0 at Cell 334) Rollback Digit 6 from 0 at Cell 263) Rollback Digit 9 from 0 at Cell 62) Rollback Digit 1 from 0 at Cell 22) Apply Digit 9 from 91 at Cell 23) Found Naked Single 1 at Cell 63) Apply Digit 1 from 1 at Cell 66) Found Naked Single 2 at Cell 294) Apply Digit 2 from 2 at Cell 295) Found Naked Single 9 at Cell 335) Apply Digit 9 from 9 at Cell 3331) Found Naked Single 8 at Cell 156) Apply Digit 8 from 8 at Cell 1522) Found Naked Single 2 at Cell 107) Apply Digit 2 from 2 at Cell 1014) Found Naked Single 6 at Cell 558) Apply Digit 6 from 6 at Cell 5515) Found Naked Single 4 at Cell 599) Apply Digit 4 from 4 at Cell 5921) Found Naked Single 7 at Cell 910) Apply Digit 7 from 7 at Cell 915) Found Naked Single 3 at Cell 1711) Apply Digit 3 from 3 at Cell 1716) Found Naked Single 2 at Cell 5412) Apply Digit 2 from 2 at Cell 5413) Found Naked Single 7 at Cell 6213) Apply Digit 7 from 7 at Cell 6214) Found Naked Single 4 at Cell 7014) Apply Digit 4 from 4 at Cell 7016) Found Naked Single 2 at Cell 4415) Apply Digit 2 from 2 at Cell 4417) Found Naked Single 5 at Cell 5616) Apply Digit 5 from 5 at Cell 5618) Found Naked Single 3 at Cell 6017) Apply Digit 3 from 3 at Cell 6021) Found Naked Single 7 at Cell 2518) Apply Digit 7 from 7 at Cell 2521) Found Naked Single 3 at Cell 4319) Apply Digit 3 from 3 at Cell 4322) Found Naked Single 6 at Cell 7120) Apply Digit 6 from 6 at Cell 7127) Found Naked Single 8 at Cell 1821) Apply Digit 8 from 8 at Cell 1822) Found Naked Single 9 at Cell 6322) Apply Digit 9 from 9 at Cell 6326) Found Naked Single 4 at Cell 3623) Apply Digit 4 from 4 at Cell 3626) Found Naked Single 6 at Cell 4724) Apply Digit 6 from 6 at Cell 4726) Found Naked Single 7 at Cell 4925) Apply Digit 7 from 7 at Cell 4926) Found Naked Single 4 at Cell 5126) Apply Digit 4 from 4 at Cell 5129) Found Naked Single 1 at Cell 1127) Apply Digit 1 from 1 at Cell 1130) Found Naked Single 8 at Cell 3828) Apply Digit 8 from 8 at Cell 3829) Found Naked Single 7 at Cell 6529) Apply Digit 7 from 7 at Cell 6530) Found Naked Single 9 at Cell 3730) Apply Digit 9 from 9 at Cell 3731) Found Naked Single 9 at Cell 2631) Apply Digit 9 from 9 at Cell 2632) Found Naked Single 7 at Cell 4232) Apply Digit 7 from 7 at Cell 4233) Found Naked Single 8 at Cell 6433) Apply Digit 8 from 8 at Cell 6434) Found Naked Single 6 at Cell 4034) Apply Digit 6 from 6 at Cell 4035) Found Naked Single 5 at Cell 6935) Apply Digit 5 from 5 at Cell 6936) Found Naked Single 3 at Cell 2036) Apply Digit 3 from 3 at Cell 2037) Found Naked Single 6 at Cell 2437) Apply Digit 6 from 6 at Cell 2438) Found Naked Single 4 at Cell 7438) Apply Digit 4 from 4 at Cell 7439) Found Naked Single 6 at Cell 7739) Apply Digit 6 from 6 at Cell 7740) Found Naked Single 2 at Cell 7840) Apply Digit 2 from 2 at Cell 786) 659387124721649853843125679572438961498561732316972485265894317987213546134756298 # S6 # N40 # H0 # 0.000000`

R. Jamil
rjamil

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

### Re: What if Naked pair/triplet found within chute

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
.
Last edited by David P Bird on Fri Oct 09, 2015 9:31 pm, edited 1 time in total.
David P Bird
2010 Supporter

Posts: 938
Joined: 16 September 2008
Location: Middle England

### Re: What if Naked pair/triplet found within chute

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;      }`

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
rjamil

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

### Re: What if Naked pair/triplet found within chute

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
.
David P Bird
2010 Supporter

Posts: 938
Joined: 16 September 2008
Location: Middle England

### Re: What if Naked pair/triplet found within chute

Hi David,

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

David P Bird wrote: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
rjamil

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

### Re: What if Naked pair/triplet found within chute

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       | 125689D6  | 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
.
David P Bird
2010 Supporter

Posts: 938
Joined: 16 September 2008
Location: Middle England

### Re: What if Naked pair/triplet found within chute

Hi,
R. Jamil wrote: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?)

David P Bird wrote: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 combinationsDim B(0 to 512) As Integer ' pre-define bit-countDim Unit(1 To 9) As IntegerDim k As IntegerDim a As IntegerUnit(1) = 2356Unit(2) = 135Unit(3) = 12Unit(4) = 13Unit(5) = 569Unit(6) = 569Unit(7) = 78Unit(8) = 1234568Unit(9) = 1245678' For checking Naked/Hidden pair routineFor 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 IfNext 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 !!!!
rjamil

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

### Re: What if Naked pair/triplet found within chute

Rizwan
You wrote: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
David P Bird
2010 Supporter

Posts: 938
Joined: 16 September 2008
Location: Middle England

### Re: What if Naked pair/triplet found within chute

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
rjamil

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

### Re: What if Naked pair/triplet found within chute

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).

JasonLion
2017 Supporter

Posts: 620
Joined: 25 October 2007
Location: Silver Spring, MD, USA

### Re: What if Naked pair/triplet found within chute

Hi Jason,

JasonLion wrote: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
rjamil

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

rjamil wrote:

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

Pat

Posts: 3292
Joined: 18 July 2005

### Re: What if Naked pair/triplet found within chute

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
rjamil

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

### Re: What if Naked pair/triplet found within chute

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 solvedunsigned int SolGrid[81];// Naked Singles FIFO stack - new singles found are stored here beforechar  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 Flagsint  Changed;          // Flag to indicate Grid has changedchar ChangedGroup[27]; // Marks which groups have changedchar 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 structurechar GuessPos[128];int  GuessVal[128];int  OneStepP[81], OneStepI;// Key global variables used throughout the solvinglong   PuzzleCnt = 0;    // Total puzzles testedlong   SolvedCnt = 0;    // Total puzzles solvedint    PuzSolCnt;        // Solutions for a single puzzleint    No_Sol;           // Flag to indicate there is no solution possibleint    PIdx;             // Position Index, used for guessing and backtracking// Debug statsint  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]; }    }  }}`
dobrichev
2016 Supporter

Posts: 1302
Joined: 24 May 2010

### Re: What if Naked pair/triplet found within chute

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
rjamil

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

PreviousNext