Does this technique have a name?

Post the puzzle or solving technique that's causing you trouble and someone will help

Does this technique have a name?

Postby RSW » Sat Dec 01, 2018 7:51 am

Hi everyone. This is my first post here.

This is a strategy that I used by hand very early on when I was a beginner at solving Sudokus. Please refer to the attached diagram, and Row C in particular.
PuzzleA.png
PuzzleA.png (30.86 KiB) Viewed 1028 times

Candidates for empty cells in Row C:
C1 - 1 3
C2 - 1 2
C4 - 1 6
C5 - 1 3 4 6
C7 - 1 2 6

Here is the output from my solver program explaining the solution of C1 and C5.

---
There are 3 valid ways of arranging the 5 unassigned digits in row C:
31-64-2--
32-14-6--
32-64-1--
In every case: C1=3, C5=4. Therefore, these are the actual cell values.
* Solved Cell C1=3
* Solved Cell C5=4
---

Although it's programmed into my solver, It's easy to do by hand, because once a puzzle reaches a stage where many of the candidates have been eliminated, then there are usually only a few ways of arranging the digits in the unfilled cells of a row, column or box. So, it's just a matter of writing them out and checking for a persistent digit in one or more cells.

I've looked through quite a few webpages explaining the various strategies, but I haven't seen this one mentioned. It may be a special case of a more general strategy though. If it has a name, then please let me know. If it doesn't have a name, then I would suggest that it be called "Musical Chairs" for reasons which hopefully are apparent. Thanks.
Last edited by RSW on Wed Dec 12, 2018 11:43 pm, edited 1 time in total.
RSW
 
Posts: 611
Joined: 01 December 2018
Location: Western Canada

Re: Does this strategy have a name?

Postby RSW » Sun Dec 02, 2018 10:09 am

Sorry, in my haste to find an example, I overlooked the fact that there's a naked triple that leads to the same solution. Normally, my solver applies a search for naked subsets before it searches for this, but I forced it to look directly for this type of situation in order to find an example quickly.

In normal operation, the solver sometimes comes up with positive matches for this situation, even after a search for naked subsets. So, this is not an exact equivalent of a naked subset. But after finding other examples, I've discovered what is happening.

There are cases where a row, column or box may have two cells which can be solved by two separate applications of the same or different methods, such as two naked subsets, or a hidden single and a naked subset. In some cases, one will overlap the other so that the naked subset is not immediately detected. The technique described in the first post finds them both in the same step, but they both would have eventually been found by basic strategies.
RSW
 
Posts: 611
Joined: 01 December 2018
Location: Western Canada

Re: Does this strategy have a name?

Postby SpAce » Sun Dec 02, 2018 10:47 am

RSW wrote:Hi everyone. This is my first post here.

Hi RSW, and welcome to the forum.

I've looked through quite a few webpages explaining the various strategies, but I haven't seen this one mentioned. It may be a special case of a more general strategy though. If it has a name, then please let me know.

"Aligned Pair/Triple Exclusion" seems like the closest match to me.

http://sudopedia.enjoysudoku.com/Aligned_Pair_Exclusion.html
http://sudopedia.enjoysudoku.com/Aligned_Triple_Exclusion.html
http://www.sudokuwiki.org/Aligned_Pair_Exclusion

Then again, why would you want to use something like that here because your puzzle state requires singles only?

PS. Please don't call it (or any individual solving tactic or technique) "strategy" ;) (Many do but that doesn't make them right.)

WikiPedia wrote:The terms tactic and strategy are often confused: tactics are the actual means used to gain an objective, while strategy is the overall campaign plan, which may involve complex operational patterns, activity, and decision-making that govern tactical execution. (source)
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Does this strategy have a name?

Postby eleven » Sun Dec 02, 2018 3:02 pm

RSW wrote:Although it's programmed into my solver, It's easy to do by hand, because once a puzzle reaches a stage where many of the candidates have been eliminated, then there are usually only a few ways of arranging the digits in the unfilled cells of a row, column or box.

Hi RSW,

as SpAce said, the first question is, why obvious singles are not filled out, like A1=9, F2=4 (which somehow you must have used, because 49 are missing as candidate in some, but not all cells seeing them), which alone would solve the puzzle.

Second, looking at row C alone in your diagram, a manual solver would use the triple 126 in C247 to eliminate these digits in C14, getting C1=3 and then C5=4 too. You cannot get any eliminations with this method, when looking at a single unit (row/columen/box) only, which you would not get by the easier methods of pairs, triples or quads (where for most manual solvers the corresponding hidden pairs/triples are spotted easier).

However this method of enumerating all possible combinations in a unit, and looking for a common outcome - for which i don't know a special name - , can be useful in harder puzzles, as again SpAce pointed out with the aligned pairs/triples exclusions using cells outside the unit. (I think that this method is covered by the more popular ALS XZ).

Finally i have tried this method as a last resort for extremely hard puzzles: If you have a unit with relatively few possible combinations (say less than 8), try one after the other, and look, if you run into a contradiction or a common outcome. This turned out to be similarly successful - and cumbersome - than to start with all 2 or 3 possibilities of a digit in a unit.
eleven
 
Posts: 3081
Joined: 10 February 2008

Re: Does this strategy have a name?

Postby SpAce » Sun Dec 02, 2018 7:37 pm

eleven wrote:as SpAce said, the first question is, why obvious singles are not filled out, like A1=9, F2=4

As well as B4=5.

(which somehow you must have used, because 49 are missing as candidate in some, but not all cells seeing them), which alone would solve the puzzle.

I'm eagerly awaiting RSW's explanation, but in the mean time my theory is that, if this was the output of the mentioned solver program, it's using a weird hierarchy of solving methods (and/or perhaps some basics aren't implemented at all). Looks like it's missed all hidden singles, but instead used a naked pair, a claiming, and even a chute X-Wing (or at least I can't easily explain the missing candidates otherwise):

Code: Select all
.------------------.-------------------.------------.
| 19-3  8      34  | 7    169-34  1239 | 126  34  5 |
| 6     127-4  347 | 159  139-4   1239 | 12   34  8 |
| 13    12-4   5   | 16   1346    8    | 126  9   7 |
:------------------+-------------------+------------:
| 5     17     37  | 2    13      6    | 4    8   9 |
| 2     6      9   | 4    8       5    | 3    7   1 |
| 13    14     8   | 19   7       139  | 5    6   2 |
:------------------+-------------------+------------:
| 4     5      2   | 689  69      7    | 89   1   3 |
| 8     9      1   | 3    5       4    | 7    2   6 |
| 7     3      6   | 189  2       19   | 89   5   4 |
'------------------'-------------------'------------'

Naked Pair (34)r1 => -3 r1c15, -4 r1c5
Claiming (4)c3\b1 => -4 r23c2
X-Wing (4)c38\r12 => -4 r2c5

Then again, that theory doesn't explain why the claiming (9)r2\b2 => -9 r1c56, or the naked pair (13)c1 => -13 r1c1, were missed.

RSW wrote:If it doesn't have a name, then I would suggest that it be called "Musical Chairs" for reasons which hopefully are apparent.

I think that would have been a much better name than "Aligned Pair Exclusion" :)
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Does this strategy have a name?

Postby RSW » Mon Dec 03, 2018 1:12 am

First of all, thank you all for the replies.
Since I'm a noob here, my posts have to be approved before they appear on the forum. So, there's going to be a bit of time lag between your comments and my responses. My second post was sent before my first post had received any replies, after realizing I'd used a poor example. I was trying to anticipate some of the comments.

To keep things in chronological order, I'm now posting after SpAce's second comment. (My second post hasn't appeared yet.)

I think my second post addresses SpAce's first comments.

Regarding eleven's comment, this is a technique that I used very early on when I first started doing Sudokus, and wasn't very familiar with the standard solving methods. I was self taught up to that point. I was applying techniques like naked pairs/triples and pointing pairs/triples techniques erratically, without exactly knowing that there was a systematic way to look for them. So, at that time, the idea of looking at the possible arrangements of unused digits, was the only systematic way that I could think of, even though it is indeed cumbersome.

I had suspected that it was redundant and could be removed from my solver program, except for the previously mentioned fact that it would occasionally solve a cell even when applied immediately after a search for naked subsets. I now understand why that was happening. (Best way to answer my own question is to post it on a forum, and then right after I click the "Post" button, the answer comes to me, and I slap my forehead.)

My conclusion is that the "musical chairs" technique will solve all cells in a row, column or box that could have been solved by any other non-intersection technique or combination thereof, and does it in one application. However, it's unlikely that this technique would be any more efficient than that combination of techniques.

In looking for examples of why this technique solved cells when the other methods didn't catch the pattern, I found that it was simply due to the solve order. In one case there would have been a naked triple, but one of the participating cells was also a hidden single, which obscured the triple.

My solver program is definitely a work in progress, and no doubt the solve order is not optimal.
In its current form, it detects:
- Naked singles
- Hidden singles
- Naked subsets (pairs, triples, all the way up to naked septuples)
- Box/Line intersections (pointing pairs/triples etc.)
- X-wing
- XY-wing

I didn't include hidden pairs/triples/quads because the complementary naked subsets are detected, and my naked subset routine seemed to be far more efficient than I could make a hidden subset routine. At some point I'll have another look at that. My immediate priority is to add swordfish and some colouring techniques.

As for the solve order, this is how it goes:
Code: Select all
1. Do an initial scan to set the cell candidates and solve any naked singles;
Loop:
2.  Scan the grid repeatedly for hidden singles until no more can be found;
3.  Scan the grid repeatedly for naked subsets until no more can be found;
4.  Scan the grid repeatedly for box/line intersections until no more can be found;
5.  Scan the grid once for "musical chairs;"
6.  Scan the grid once for XY-wings;
7.  Scan the grid once for X-wings;
8.  If puzzle is not completely solved then:
    Did the previous steps result in at least one candidate elimination?
    - If yes, then go back and repeat starting at step 2.
    - If no, then find the empty cell with the fewest candidates and call this main routine recursively, trying each of the cell's candidates until the correct one is found and the puzzle is solved.

Whenever any of the above techniques results in a naked single, that cell is solved, and a "RemoveCandidates" subroutine is called to remove that cell's value from the candidates of cells in the intersecting row/column/box. If that results in one or more naked singles then those cells are immediately solved and RemoveCandidates is called recursively. So, there is no need for a separate step in the main loop to solve naked singles.


So, with the above solve order and the RemoveCandidates routine, naked singles are immediately solved, but hidden singles won't be solved until the loop repeats.

FYI, I haven't looked at any existing solver source code to see how others have done it. I wanted to do this on my own, at least until I get to the point where I can't figure out how to proceed.
RSW
 
Posts: 611
Joined: 01 December 2018
Location: Western Canada

Re: Does this strategy have a name?

Postby eleven » Sat Dec 08, 2018 12:34 am

Glad, if the answers helped you a bit. Good luck in creating your own solver.

I agree, that it is most delightful to find things on one's own - and interesting then, how similar or not it is compared to what others found.

On the other hand, when i needed a solver, which has complex techniques implemented or a very fast solver, in order to be able to make other findings on my own, i was very impressed, how higly opimized they were.
eleven
 
Posts: 3081
Joined: 10 February 2008

Re: Does this strategy have a name?

Postby RSW » Sat Dec 08, 2018 5:58 am

Yes, it will be interesting to compare the efficiency of my implementations to those of other solver software. I've done my best to make my code as efficient as possible. However, this is offset by the fact that the program generates detailed solve notes. This probably adds quite a bit of time when solving a puzzle, but there's no convenient way to turn it off without stripping it completely out of the program code. As it is, it solves the puzzles in the Supreme Puzzle thread in about 30 milliseconds, which is certainly far faster than a human could do them manually. The Supreme puzzles are a good test for my solver, in its current form, because these puzzles can all be solved without the solver resorting to trial & error. (If trial & error is required, then the solve time jumps to about 1.3 seconds on average.)

FYI, following are the verbose solve notes for Supreme puzzle #002:
.5......73..2.65.9.4..5.6....7.68...............42.8....5.9..2.6.28.3..49......1.
Solver Output: Show
RSW's Solver wrote:Using "K9" notation:
* Cell J6 is the only valid location in row J for digit 2
* Cell H8 is the only valid location in row H for digit 5
- Removing candidate 5 from D8 E8 F8 J9
* Cell J4 is the only valid location in row J for digit 5
- Removing candidate 5 from D4 E4
* Cell A3 is the only valid location in row A for digit 6
- Removing candidate 6 from E3 F3
* Cell J9 is the only valid location in row J for digit 6
- Removing candidate 6 from E9 F9 G9
* Cell G4 is the only valid location in column 4 for digit 6
* Cell G9 is the only valid location in block 9 for digit 8
- Removing candidate 8 from G1 G2 C9
* Cell H7 is the only valid location in row H for digit 9
- Removing candidate 9 from D7 E7
* Cell C3 is the only valid location in block 1 for digit 9
- Removing candidate 9 from C4 C6 E3 F3
In column 7, G7 J7 have identical candidates: 3 7
- Removing candidate 3 from A7 D7 E7
- Removing candidate 7 from E7
In row F, the digits 1 3 5 must go in cells F1 F3 F9 (unspecified order)
These digits can then be eliminated from the other cells in row F
- Removing candidate(s) 1 3 from cell F2
- Removing candidate(s) 1 5 from cell F6
- Removing candidate(s) 3 from cell F8
In column 2, the digits 1 3 7 8 must go in cells B2 G2 H2 J2 (unspecified order)
These digits can then be eliminated from the other cells in column 2
- Removing candidate(s) 1 3 from cell D2
- Removing candidate(s) 1 3 8 from cell E2
In column 6, the digits 1 4 7 9 must go in cells A6 C6 F6 G6 (unspecified order)
These digits can then be eliminated from the other cells in column 6
- Removing candidate(s) 1 7 9 from cell E6
In column 8, the digits 3 4 8 must go in cells A8 B8 C8 (unspecified order)
These digits can then be eliminated from the other cells in column 8
- Removing candidate(s) 3 4 from cell D8
- Removing candidate(s) 3 4 from cell E8
In column 8, the digits 3 4 8 9 must go in cells A8 B8 C8 D8 (unspecified order)
These digits can then be eliminated from the other cells in column 8
- Removing candidate(s) 9 from cell E8
- Removing candidate(s) 9 from cell F8
In block 3, the digits 3 4 8 must go in cells A8 B8 C8 (unspecified order)
These digits can then be eliminated from the other cells in block 3
- Removing candidate(s) 4 from cell A7
- Removing candidate(s) 3 from cell C9
In block 4, the digits 2 6 9 must go in cells D2 E2 F2 (unspecified order)
These digits can then be eliminated from the other cells in block 4
- Removing candidate(s) 2 from cell D1
- Removing candidate(s) 2 from cell E1
* Cell D8 now has only one possible value: 9
- Removing candidate 9 from D2 D4
* Cell D2 now has only one possible value: 2
- Removing candidate 2 from D7 D9 E2
* Cell E6 now has only one possible value: 5
- Removing candidate 5 from E1 E9
In column 2, the only valid positions for digit 3 are G2 J2
- Removing candidate 3 from block 7 J3
X-wing: In rows B & H, digit 7 must go in column 2 or 5
Therefore candidate 7 can be removed from all other cells in columns 2 & 5
Removing candidate 7 from E5 G2 J2 J5
* Cell J5 now has only one possible value: 4
- Removing candidate 4 from J3 A5 B5 G6
* Cell J3 now has only one possible value: 8
- Removing candidate 8 from J2 B3 E3
* Cell J2 now has only one possible value: 3
- Removing candidate 3 from J7 G2
* Cell J7 now has only one possible value: 7
- Removing candidate 7 from G7
* Cell G7 now has only one possible value: 3
* Cell G2 now has only one possible value: 1
- Removing candidate 1 from G1 G6 B2 H2
* Cell G6 now has only one possible value: 7
- Removing candidate 7 from G1 C6 F6 H5
* Cell G1 now has only one possible value: 4
- Removing candidate 4 from D1 E1
* Cell C6 now has only one possible value: 1
- Removing candidate 1 from C1 C4 C9 A6 A4 A5 B5
* Cell C9 now has only one possible value: 2
- Removing candidate 2 from C1 E9 A7
* Cell A7 now has only one possible value: 1
- Removing candidate 1 from A1 D7 E7
* Cell D7 now has only one possible value: 4
- Removing candidate 4 from E7
* Cell E7 now has only one possible value: 2
* Cell F6 now has only one possible value: 9
- Removing candidate 9 from F2 A6 E4
* Cell F2 now has only one possible value: 6
- Removing candidate 6 from F8 E2
* Cell F8 now has only one possible value: 7
- Removing candidate 7 from E8
* Cell E8 now has only one possible value: 6
* Cell E2 now has only one possible value: 9
* Cell A6 now has only one possible value: 4
- Removing candidate 4 from A8
* Cell H5 now has only one possible value: 1
- Removing candidate 1 from E5
* Cell E5 now has only one possible value: 3
- Removing candidate 3 from E3 E4 E9 A5 D4
* Cell E9 now has only one possible value: 1
- Removing candidate 1 from E1 E3 E4 D9 F9
* Cell E1 now has only one possible value: 8
- Removing candidate 8 from A1 C1
* Cell A1 now has only one possible value: 2
* Cell C1 now has only one possible value: 7
- Removing candidate 7 from C4 B2
* Cell C4 now has only one possible value: 3
- Removing candidate 3 from C8 A4
* Cell C8 now has only one possible value: 8
- Removing candidate 8 from A8 B8
* Cell A8 now has only one possible value: 3
* Cell B8 now has only one possible value: 4
* Cell A4 now has only one possible value: 9
* Cell B2 now has only one possible value: 8
- Removing candidate 8 from B5
* Cell B5 now has only one possible value: 7
* Cell E3 now has only one possible value: 4
* Cell E4 now has only one possible value: 7
* Cell A5 now has only one possible value: 8
* Cell D4 now has only one possible value: 1
- Removing candidate 1 from D1
* Cell D1 now has only one possible value: 5
- Removing candidate 5 from D9 F1
* Cell D9 now has only one possible value: 3
- Removing candidate 3 from F9
* Cell F9 now has only one possible value: 5
* Cell F1 now has only one possible value: 1
- Removing candidate 1 from F3
* Cell F3 now has only one possible value: 3
* Cell H2 now has only one possible value: 7
* Cell B3 now has only one possible value: 1

Solution:

256 984 137
381 276 549
749 351 682

527 168 493
894 735 261
163 429 875

415 697 328
672 813 954
938 542 716

Total solution time: 33.44 milliseconds
Last edited by RSW on Fri Dec 14, 2018 6:06 am, edited 1 time in total.
RSW
 
Posts: 611
Joined: 01 December 2018
Location: Western Canada

Re: Does this strategy have a name?

Postby StrmCkr » Sat Dec 08, 2018 10:57 am

I didn't include hidden pairs/triples/quads because the complementary naked subsets are detected, and my naked subset routine seemed to be far more efficient than I could make a hidden subset routine. At some point I'll have another look at that. My immediate priority is to add swordfish and some colouring techniques.


heres how i do it, however i use set-wise mathematics...
see my StormDoku for further information

note:
other options is a tidle function to bit-swap the digits and search the opposite set size ie a size 2 naked set swapped to the opposite size = 7 which means if the size 2 cells has all 7 digits "off" then those 2 cells is holding a size 2 hidden set. and all other digits in those cells can be swapped off. {that is if you are using RN,Rn,Cn,Bn, space}

hidden data space: Show
Code: Select all
{hidden sets} saves location of digit. by noted area} /code]
Rn: array [Rcb,digits] of RCBnums;   {nums represet Col #}
Cn: array [Rcb,digits] of RCBnums;   {nums represet Row #}
Bn: array [Rcb,digits] of RCBnums;   {nums represet Box ordering #}


Hidden Pair: Show
Code: Select all
procedure HP(k:integer);
var
xn,yn,n,n2,z,g,q:integer;
begin

if k =0 then begin g:=0; setlength(techwrite,g+1,11);  end;
For xn:= 0 to 8 do

   For n:= 1 to 8 do
    for n2:= (n+1) to 9 do
       begin

         If   (R[xn,n] > 0) and (R[xn,n] < 3 )
           and (R[xn,n2] > 0) and (R[xn,n2] < 3 )
            then
              for yn:= 9 to 44 do
                if Rn[xn,n] + Rn[xn,n2] = comboset2[yn]
                 then
                   begin
                    active:= true;

                     for z:= 0 to 8 do
                       if z in comboset2[yn]
                        then
                         begin
                           covered[rset[xn,z]]:= covered[rset[xn,z]] * [n,n2] * pm[rset[xn,z]];

                         if k = 0 then
                          begin

                           for q in pm[rset[xn,z]] - [n,n2] do
                            techwrite[g,q]:=techwrite[g,q]+ [rset[xn,z]];

                          end;
                         end;

                    if (k = 0) and (techwrite[g,1] + techwrite[g,2] + techwrite[g,3] + techwrite[g,4] + techwrite[g,5] + techwrite[g,6] + techwrite[g,7] + techwrite[g,8]+ techwrite[g,9] <> [])
                     then
                       begin
                        for q in comboset2[yn] do
                          techwrite[g,10]:=techwrite[g,10] + [rset[xn,q]];
                          techwrite[g,0]:=techwrite[g,0] + [n,n2];

                          g:=g+1;
                          setlength(techwrite,g+1,11);

                       end;

                  end;

           If  (C[xn,n] > 0) and (C[xn,n] < 3 )
           and (C[xn,n2] > 0) and (C[xn,n2] < 3 )
            then
              for yn:= 9 to 44 do
                if Cn[xn,n] + Cn[xn,n2] = comboset2[yn]
                 then
                   begin
                    active:= true;

                     for z:= 0 to 8 do
                       if z in comboset2[yn]
                        then
                   begin
                           covered[Cset[xn,z]]:= covered[Cset[xn,z]] * [n,n2] * pm[Cset[xn,z]];
                    if k = 0 then
                          begin

                           for q in pm[Cset[xn,z]] - [n,n2] do
                            techwrite[g,q]:=techwrite[g,q]+ [Cset[xn,z]];

                          end;
                         end;

                    if (k = 0) and (techwrite[g,1] + techwrite[g,2] + techwrite[g,3] + techwrite[g,4] + techwrite[g,5] + techwrite[g,6] + techwrite[g,7] + techwrite[g,8]+ techwrite[g,9] <> [])
                     then
                       begin
                        for q in comboset2[yn] do
                          techwrite[g,10]:=techwrite[g,10] + [Cset[xn,q]];
                          techwrite[g,0]:=techwrite[g,0] + [n,n2];

                          g:=g+1;
                          setlength(techwrite,g+1,11);

                       end;

                  end;

           If  (b[xn,n] > 0) and (b[xn,n] < 3 )
           and (b[xn,n2] > 0) and (b[xn,n2] < 3 )
            then
              for yn:= 9 to 44 do
                if bn[xn,n] + bn[xn,n2] = comboset2[yn]
                 then
                   begin
                    active:= true;

                     for z:= 0 to 8 do
                       if z in comboset2[yn]
                        then
                   begin
                           covered[bset[xn,z]]:= covered[bset[xn,z]] * [n,n2] * pm[bset[xn,z]];
                      if k = 0 then
                          begin

                           for q in pm[bset[xn,z]] - [n,n2] do
                            techwrite[g,q]:=techwrite[g,q]+ [bset[xn,z]];

                          end;
                         end;

                    if (k = 0) and (techwrite[g,1] + techwrite[g,2] + techwrite[g,3] + techwrite[g,4] + techwrite[g,5] + techwrite[g,6] + techwrite[g,7] + techwrite[g,8]+ techwrite[g,9] <> [])
                     then
                       begin
                        for q in comboset2[yn] do
                          techwrite[g,10]:=techwrite[g,10] + [bset[xn,q]];
                          techwrite[g,0]:=techwrite[g,0] + [n,n2];

                          g:=g+1;
                          setlength(techwrite,g+1,11);

                       end;


                  end;

        end;

if k = 0 then techdisplay(#61,g);

end;{hidden pair}


Naked save data space: Show
Code: Select all
{Naked sets} saves each digit in Cell
RC: array[RCB,RCB] of nums;      {# in row x col}
BS: array[RCB,RCB] of nums;      {# in box - square}


Naked Pair: Show
Code: Select all
{Naked pairs}
procedure NP(k:integer);
var
xn,yn,n,n2,z,g,q:integer;
begin

if k = 0 then begin g:=0; setlength(techwrite,g+1,11); end;

For xn:= 0 to 8 do
  For n:= 0 to 7 do
    for n2:= (n+1) to 8 do

        begin

           if(RC[xn,n] <> []) and (RC[xn,n2] <> [])
           and (nm[rset[xn,n]] <3) and (nm[rset[xn,n2]] <3)
            then
             for yn:= 9 to 44 do
              if ( RC[xn,n] + RC[xn,n2] = comboset[yn])
               then
                   begin
                     active:= true;


                     for z:= 0 to 8 do
                       if  not (z in [n,n2] )
                        then
                           begin

                           covered[rset[xn,z]]:= covered[rset[xn,z]] - (comboset[yn] * pm[rset[xn,z]]);

                           if k= 0
                            then
                             begin
                              for q in pm[rset[xn,z]] * comboset[yn] do
                                techwrite[g,q]:=techwrite[g,q]+[rset[xn,z]];
                             end;

                           end;

                   if (k = 0) and (techwrite[g,1] + techwrite[g,2] + techwrite[g,3] + techwrite[g,4] + techwrite[g,5] + techwrite[g,6] + techwrite[g,7] + techwrite[g,8]+ techwrite[g,9] <> [])
                    then
                      begin
                       techwrite[g,0]:= techwrite[g,0]+ [rset[xn,n]]+[rset[xn,n2]];
                       techwrite[g,10]:=techwrite[g,10] + comboset[yn];
                       g:=g+1;
                       setlength(techwrite,g+1,11);

                      end;

                  end; {rows}

           if (RC[n,xn] <> []) and (RC[n2,xn] <> [])
           and (nm[Rset[n,xn]] < 3 ) and (nm[Rset[n2,xn]] <3)
            then
             for yn:= 9 to 44 do
              if (RC[n,xn] + RC[n2,xn] = comboset[yn] )
                then
                   begin
                    active:= true;

                     for z:= 0 to 8 do
                       if  not (z in [n,n2] )
                        then
                         begin
                           covered[Cset[xn,z]]:= covered[Cset[xn,z]] - (comboset[yn]* pm[Cset[xn,z]]);

                            if k= 0
                            then
                             begin
                              for q in pm[Cset[xn,z]] * comboset[yn] do
                                techwrite[g,q]:=techwrite[g,q]+[Cset[xn,z]];
                             end;

                         end;

                   if (k = 0) and (techwrite[g,1] + techwrite[g,2] + techwrite[g,3] + techwrite[g,4] + techwrite[g,5] + techwrite[g,6] + techwrite[g,7] + techwrite[g,8]+ techwrite[g,9] <> [])
                    then
                      begin
                       techwrite[g,0]:= techwrite[g,0]+ [Cset[xn,n]]+[Cset[xn,n2]];
                       techwrite[g,10]:=techwrite[g,10] + comboset[yn];

                       g:=g+1;
                       setlength(techwrite,g+1,11);

                      end;

                  end;{cols}

           if (Bs[xn,n] <> []) and (BS[xn,n2] <> [])
           and (nm[bset[xn,n]] < 3) and (nm[bset[xn,n2]] <3)
            then
             for yn:= 9 to 44 do
              if (BS[xn,n] + Bs[xn,n2] = comboset[yn] )
               then
                   begin
                    active:= true;

                     for z:= 0 to 8 do
                       if  not (z in [n,n2] )
                        then
                         begin
                           covered[Bset[xn,z]]:= covered[Bset[xn,z]] - (comboset[yn]* pm[Bset[xn,z]]);

                          if k= 0
                            then
                             begin
                              for q in pm[Bset[xn,z]] * comboset[yn] do
                                techwrite[g,q]:=techwrite[g,q]+[Bset[xn,z]];
                             end;

                         end;

                     if (k = 0) and (techwrite[g,1] + techwrite[g,2] + techwrite[g,3] + techwrite[g,4] + techwrite[g,5] + techwrite[g,6] + techwrite[g,7] + techwrite[g,8]+ techwrite[g,9] <> [])
                    then
                      begin
                       techwrite[g,0]:= techwrite[g,0]+ [Bset[xn,n]]+[Bset[xn,n2]];
                       techwrite[g,10]:=techwrite[g,10] + comboset[yn];
                       g:=g+1;
                       setlength(techwrite,g+1,11);

                      end;

                  end; {box}

        end;
if k = 0 then techdisplay(#86,g);
end;{naked pair}
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006

Re: Does this strategy have a name?

Postby RSW » Mon Dec 10, 2018 12:01 am

Thanks for posting your code. I was surprised to see Pascal code. I used to write Macintosh applications years ago using Lightspeed Pascal, until they abandoned it. I eventually switched to XOJO which is a compiled Basic variant with a nice GUI framework, and it builds cross-platform applications.

I'll have to dig through your code in some detail before it all sinks in. However, the thing that I noticed immediately is your use of arrays of constants to allow quick access to the candidate bit patterns by row column or box. I also use bit patterns for candidates, but I use a function to return the bit pattern by RCB and element number.

Using bitwise operations is especially efficient for naked subsets. I ended up splitting naked subsets into two types: Dense and Sparse.
Dense is where every cell in the subset has exactly the same candidates. Pairs are inherently dense, while triples, quads etc. may not be.
Sparse is where the cells in the subset may have anywhere between 2 and N candidates in an N-tuple naked subset. The reason for distinguishing between dense and sparse is that I can use a method for finding the dense ones that is quite a bit more efficient than the one that finds the sparse ones. I don't have time right now, but I'll post my code for these later.
RSW
 
Posts: 611
Joined: 01 December 2018
Location: Western Canada

Re: Does this strategy have a name?

Postby StrmCkr » Mon Dec 10, 2018 4:08 am

Awh, I don't have to examine each cell or break the parts down, I call a sector and positing combinations for the set size check the set matches the container. Since adding same digits to a set dosent change in set wise math unlike bits.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006

Re: Does this strategy have a name?

Postby SpAce » Mon Dec 10, 2018 5:21 am

RSW wrote:My solver program is definitely a work in progress, and no doubt the solve order is not optimal.

My recommendation is to keep it flexible and allow the user to choose the active techniques and their order freely. The latter is not possible in the SudokuWiki solver, for example, which is pretty annoying because its solving hierarchy (especially with basics) doesn't correspond with typical pencil&paper solving. Most p&p solvers start without candidates and detect hidden singles and even hidden subsets before naked singles and naked subsets, but that style can't be mimicked if the hierarchy is fixed. Hodoku is nice because it allows one to tweak the hierarchy in a lot of ways (I'd like even more options, though). There's no point in trying to fix an "optimal" solver order because there's no objective way to measure it.

I didn't include hidden pairs/triples/quads because the complementary naked subsets are detected, and my naked subset routine seemed to be far more efficient than I could make a hidden subset routine. At some point I'll have another look at that.

I would do that, for the aforementioned reasons. I also don't see why the hidden stuff should be harder to find. My understanding is that you could use the same routine to find naked and hidden subsets as well as fishes with the same exact code, as long as your data spaces support that.

FYI, I haven't looked at any existing solver source code to see how others have done it. I wanted to do this on my own, at least until I get to the point where I can't figure out how to proceed.

I hear you. At some point I might like to code a solver too, but haven't got around to it. Until then, I don't want to look at others' code. I coded a basic solver in a few days almost two years ago, but back then basic techniques were all I knew so I couldn't continue the project. My plan was to study advanced techniques just enough so I could code them, because I was pretty sure I would never be able to find any chains and stuff manually.

Turned out I was wrong about that, which kind of defeated the purpose of completing the solver, so I haven't touched that project since then :D Besides, there are such good solvers around already that it's hard to see why I should write my own, except as a possibly fun exercise. However, I'm pretty sure that it would actually make me a better manual solver too, because coding requires one to think things through in a very detailed way, as you've probably noticed.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Does this strategy have a name?

Postby RSW » Mon Dec 10, 2018 7:12 am

StrmCkr wrote:Awh, I don't have to examine each cell or break the parts down, I call a sector and positing combinations for the set size check the set matches the container. Since adding same digits to a set dosent change in set wise math unlike bits.

Sorry, I misread your comments and interpreted your set operations as bitwise operations.

For my bitwise operations in the naked subset routine, I'm just doing OR operations which doesn't increase the count of elements either. (I use XOR operations to find XY-wings.) However, I see now that I could expand what it's doing to operate on a full row, column or box at at time.

SpAce wrote:My recommendation is to keep it flexible and allow the user to choose the active techniques and their order freely.

That has always been my intent. In fact the solver has a separate button for each solve technique, so that I can load a puzzle and then click the naked singles button or the hidden singles button, or any of the other solve technique buttons in any order, and the program will scan the grid once for each click of the button, and then update the grid accordingly. This is the way that I used the program up until a couple of weeks ago when I finally added a single button to repeatedly apply all techniques to solve the puzzle completely. So, the individual buttons will stay in the solver permanently. I've attached a screen shot of my solver that shows the buttons for individual solving techniques, and a partially solved puzzle. The colours of the solved digits correspond to the technique used to solve them. The original clue values are black.
SpAce wrote:
I didn't include hidden pairs/triples/quads because the complementary naked subsets are detected, and my naked subset routine seemed to be far more efficient than I could make a hidden subset routine. At some point I'll have another look at that.

I would do that, for the aforementioned reasons. I also don't see why the hidden stuff should be harder to find. My understanding is that you could use the same routine to find naked and hidden subsets as well as fishes with the same exact code, as long as your data spaces support that.

I will definitely get to this at some point. It may indeed be just a trivial change to the program.

SpAce wrote:Besides, there are such good solvers around already that it's hard to see why I should write my own, except as a possibly fun exercise.

My reasons for writing a solver were for fun and to help me learn to solve manually. In that regard, it's been successful so far. I'm not sure how much further that I'll go with it. It will depend on the difficulty of coding the advanced strategies.
Attachments
SolverWindow1.png
Solver Screenshot
SolverWindow1.png (31.57 KiB) Viewed 919 times
RSW
 
Posts: 611
Joined: 01 December 2018
Location: Western Canada

Re: Does this strategy have a name?

Postby StrmCkr » Mon Dec 10, 2018 7:26 am

SpAce

I would do that, for the aforementioned reasons. I also don't see why the hidden stuff should be harder to find. My understanding is that you could use the same routine to find naked and hidden subsets as well as fishes with the same exact code, as long as your data spaces support that.


comes down to realizing the difference in what the sectors are looking at for being able to use the same space but a cost of slightly higher run times see below of why i say higher run times and cross check my code above.
{RC space is faster for naked set-checking as it uses Pencil marks for the cell's checked vs positions left per digit in Rn,CN,Bn space}

with Rn,Cn,Bn space: {0 - 8 base}
for an example check out my programs Col example of a naked & hidden pair.
Col - # x box
the hidden naked pair uses whats left on for the "2" size set for 2 digits {1&2) marked as Col 0 R28

the naked pair on col 4 R1,7 as all other 7 cols are "off" @ R1,7

now if u you look at the Row-# x col graph
above it the hidden pair is very easily identifiable as the 0 col position in 2 rows for 2 digits,

to spot the naked you have to notice that digits 3456789 are off @ 4 col position in 2 rows. which means digits 12 only have 2 cells left to be in on these 2 rows on 1 col.

{hope you notice which one is significantly easier to code with}

first example:
cycles 1 sector for 2 digits with 7 identical spots off. {for hidden}

2nd example cycles :
2 digits with 2 rows with 8 off spots. {for hidden}

first example:
cycles 1 Col for 7 digits with 2 identical spots off. {naked}

2nd example:
cycles 2 rows for 7 digits with 1 identical spots off. {naked}

{also to note here is that you can use rows or cols interchangeable to find the same eliminations between cells, thus the search can be reduced to[ [Row or Col] & box] for subsets to potentially increase speed.

personally i use example 1 for the Hidden sets, and example 1 again for naked sets using its different data set so that both sets are optimized for "n" positions/digits "on" in a "n sized container"

{technically writing this out i just noticed this interesting aspect of reducing the search space from R/C/B to the note above...so that's neat. edit: further thinking you could even get it down to just box space by realizing what 3 box's are aligned and knowing which 3 sets of positions are linked to the respective space} { like box 1,2,3 all share position 012 for Row 0, & 0,3,6 for col 0}
probably to complicated}

Sorry, I misread your comments and interpreted your set operations as bit-wise operations.
all good i may have miss interpreted your comments when comparing + operations to bit-wise as well..
set-wise " + " is a " * " function ie " or " in bit-wise.

Dense and Sparse.

which should lead you to conclude that there is no difference between 4 digits and 1 digit in a size 4 set when comparing pm's of the 4 cells as true to a bit value. ........
Attachments
naked vs hidden.PNG
naked vs hidden.PNG (77.63 KiB) Viewed 919 times
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006

Re: Does this strategy have a name?

Postby SpAce » Tue Dec 11, 2018 8:51 am

RSW wrote:
SpAce wrote:My recommendation is to keep it flexible and allow the user to choose the active techniques and their order freely.

That has always been my intent. In fact the solver has a separate button for each solve technique, so that I can load a puzzle and then click the naked singles button or the hidden singles button, or any of the other solve technique buttons in any order, and the program will scan the grid once for each click of the button, and then update the grid accordingly.

Ok, good!

This is the way that I used the program up until a couple of weeks ago when I finally added a single button to repeatedly apply all techniques to solve the puzzle completely. So, the individual buttons will stay in the solver permanently. I've attached a screen shot of my solver that shows the buttons for individual solving techniques, and a partially solved puzzle.

For this functionality it would also be useful to be able to reorder the technique hierarchy at will. (Perhaps you have that too.)

The colours of the solved digits correspond to the technique used to solve them. The original clue values are black.

I was wondering about those color codings, but that explains! I like the idea of recording the reasonings for the placements, but I can predict a couple of problems and limitations with the coloring implementation. One, what are you going to do when you add more techniques and run out of distinctive colors? Two, you're probably going to need colors for other purposes when you add new techniques and want to visualize them, and then those existing codings would make it pretty messy and confusing. Three, there are really only two techniques that can solve a cell: naked and hidden singles. (Almost) all other techniques can just eliminate candidates, so you should actually record them within the eliminations and not within the placed digits (which are a side-effect of eliminations -- often several of them which may have very different reasons).

Instead of using colors for that purpose, I'd probably add a small identifier (an incrementing number) with both (non-trivial) eliminations and solved cells, which would be mapped to the corresponding line in the recorded solve path. That way you could easily lookup a detailed explanation for each placement and elimination as well as see the order in which they took place. I'd love to do it in pencil&paper solving too, but there's just no room for such extra markings. With a software GUI you can hide those markings when not needed, though.

My reasons for writing a solver were for fun and to help me learn to solve manually.

We're on the same boat then, except that my project got frozen almost as soon as it started. I can say, however, that even that short exercise helped me become a better manual solver. I thought I was a decent basic solver when I started that project, but I was pretty shocked when I got it running and saw how many basic patterns I'd been failing to spot! That prompted me to first hone my manual technique to the same level and then go beyond that. Now it would be much harder to write a software solver that would beat me, except in speed (and brute force) of course.

In that regard, it's been successful so far. I'm not sure how much further that I'll go with it. It will depend on the difficulty of coding the advanced strategies.

I wish you good luck with that! I hope you keep up with it, because it would be interesting to hear about your experiences in adding more complex techniques. Perhaps that'd help me find a new motivation to restart my project too.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Next

Return to Help with puzzles and solving techniques