subsets: how to identify the target and solve?

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

Postby daj95376 » Mon Sep 22, 2008 12:28 pm

tarek wrote:
In the superior variants thread, I wrote:Naked subsets are actually not bound by unit constraint.
if 3 cells that see each other have only 3 candidates, then these 3 candidates must be in these 3 cells, therfore the cells that can see all of these 3 cells cannot house these candidates.


then Pat wrote:
the term "naked" subset
refers to cells which are a subset of some set (unit, sector);
your new "naked" beast
it is no longer a subset,
and we should find a new term to reflect this;
also, it would be good to have a few words by way of proof.

Sudopedia: Subsets wrote:Complex problems can often be solved by finding ways to split them into several smaller problems. In a Sudoku, each house is a problem that has 362880 possible solutions (the possible permutations for the 9 digits). To reduce this number, a player will try to isolate groups of cells and digits from the remainder of the house.

When N cells and N digits are isolated, a subset of size N is formed.

It sure sounds to me like a Naked/Hidden Single qualifies as a Subset.

However, no one performs 3x Naked/Hidden Single operations -- one house/unit at a time!

I contend that the same should be acceptable for (Locked) Naked/Hidden Pair/Triple.

Why can't it be handled the same:?:
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Mon Sep 22, 2008 1:09 pm

daj95376 wrote:It sure sounds to me like a Naked/Hidden Single qualifies as a Subset.

However, no one performs 3x Naked/Hidden Single operations -- one house/unit at a time!

I contend that the same should be acceptable for (Locked) Naked/Hidden Pair/Triple.

Why can't it be handled the same:?:

I don't think singles and subsets are comparable.

When a [edit: hidden] single is found in one unit, the placement unconditionally causes eliminations in two other units.

When a naked subset is found in one unit, an elimination in a second unit is conditional -- meaning the same subset must exist in the second unit as well.
Last edited by ronk on Tue Sep 23, 2008 2:45 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

every "single" does also qualify as a subset of si

Postby Pat » Tue Sep 23, 2008 6:20 am

daj95376 wrote:It sure sounds to me like a Naked/Hidden Single qualifies as a Subset.



the subset terminology
is based on cells which are a sub-set of some "set" (unit, sector, house) --
  • a "naked" subset of size j means that, within a specific unit,
    we've identified j cells for which only j possible digits remain;
    therefore, we must reserve these digits for these cells
    -- exclude these digits elsewhere in this unit.
  • a "hidden" subset of size j means that, for a specific unit,
    we've identified j digits for which only j possible cells remain;
    therefore, we must reserve these cells for these digits
    -- exclude any other possibilities in these cells.
so -- yes, daj95376, you are right, every "single" does also qualify as a subset of size 1
    this keeps the subset definitions beautifully simple
    (i.e. a subset can be of any size, no need to require size > 1)
it has, however, only theoretical interest -- as you said, in practice we alwasys use a "single" rather than a subset of size 1 --
  • a "naked" subset of size 1
    would merely give us the exclusion of this digit in the other cells of that unit --
    thus, for this one cell
    we'd have to recognize 3 "naked" subsets of size 1 (one in each unit)
  • a "hidden" subset of size 1
    would merely give us the exclusion of all other digits in that cell --
    we would then have to wait for the next "step"
    to recognize this cell as 3 "naked" subsets of size 1 (one in each unit)---
-- we each discovered "singles" long before learning about subsets,
and whenever we notice a "single", we do all this in just one "step" --
  • "naked single" means that we've identified a cell in which only one possible digit can be placed.
    (that's a property of the cell, never involving any unit whatsoever.)
    this allows us to solve the cell (often called "making a placement", as we're placing this digit in this cell).
    which is immediately followed by the Basic Exclusions --
    excluding this digit in all the peer cells (yes, in 3 different units).
    and all of this is considered part of one "step" in solving the puzzle.
  • "hidden single" means that, within a specific unit, we've identified a digit for which only one possible cell is available.
    this allows us to solve the cell (incidentally removing all other possibilities in this cell).
    which is immediately followed by the Basic Exclusions --
    excluding this digit in all the peer cells.
    and all of this is considered part of one "step" in solving the puzzle.

thus, daj95376, it seems we do agree about "singles" -- but still differ about the larger subsets.

consider your earlier example -- "naked" duo r3c13=35 --
    as i said in my earlier post,
    r3c13 is a "naked" duo in r3 and also (at the very same time) a "naked" duo in b1.

    when counting "steps" of solving, these 2 duos obviously belong in the same "step";
    but when counting the subsets i've used, i'd have to count them as 2 different duos.
this is my opportunity to thank Jean-Christophe and tarek
for the discussion in the Superior Variants Topic (2008.Jul.31),
where i first bumped into this new type of "naked" beast
(and an extra thank-you to tarek for bringing it to our attention in the present Topic!)
    while Jean-Christophe calls this beast a "Generalized Naked Subset",
    and while i agree that it is indeed stronger than the "naked" subset,
    i still think it needs a better name
    as it is not a sub-set of any "set" (unit, sector, house)
so daj95376, getting back to those 2-"naked"-duos-in-the-same-cells,
obviously you do have a valid reason to consider these 2 as just one instance of some beast,
and this beast is the so-called "Generalized Naked Subset".
    (which is -- let me repeat -- not a subset.
    it provides the desired exclusions,
    but the logic is not based on the theory of subsets.)
User avatar
Pat
 
Posts: 3640
Joined: 18 July 2005

Postby daj95376 » Tue Sep 23, 2008 9:12 am

Thanks to those who participated in this discussion:!:

I think Pat finally came very close to saying what I'd been fighting to hear from the start.

DAJ's Goal wrote:There's no logical reason why Subsets can't perform eliminations in multiple units concurrently, but convention dictates that eliminations for Subsets > 1 candidate be restricted to one unit at a time.

I'm perfectly happy to go along with convention because it simplifies the use of Subsets and makes them easier to explain.

In my solver, I perform eliminations one unit at a time for Subsets >1 candidate. I just flag them to indicate their relationship.

Code: Select all
   c1b7  Locked Pair                     <> 69   [r79c3]
   c1b7  cloned Pair                     <> 69   [r3c1]
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby tarek » Tue Sep 23, 2008 9:51 am

Pat,
Thanks for the kind words

daj95376,
I don't think that Pat disputed the logic behind what you said ... It is the Wording that seems to cause all this confusion.

Drop the word "subset" and use some other term ....

The use of "SET" IMO should be correct.

Code: Select all
Naked Set: Any group of N cells that SEE each other and contain N different candidates only. Similar candidates in ANY cell that can be seen by ALL N cells can be safely eliminated


In the group of cells: A + B (where A are the Set cells & B are All other cells seen by ALL A cells)

The naked set is Locked in cells A & eliminate similar candidates froms cells B ... Therefore another possible name is "Locked set"

I agree that all Naked eliminations should happen in one step ... The shift from Hidden to Naked eliminations has to happen over 2 steps IMO because the Hidden logic depends on being a subset.

tarek
User avatar
tarek
 
Posts: 2698
Joined: 05 January 2006

Postby daj95376 » Tue Sep 23, 2008 3:35 pm

tarek: Okay. Naked/Hidden Single are Set eliminations, and Naked/Hidden Pair/Triple/Quad are Subset eliminations. However, it is agreed that Naked/Hidden Pair/Triple Set eliminations exist but aren't used ... and referring to them as Locked (in two units) is acceptable.

tarek wrote:I agree that all Naked eliminations should happen in one step ... The shift from Hidden to Naked eliminations has to happen over 2 steps IMO because the Hidden logic depends on being a subset.

Yes, the issue of Hidden S(ubs)et eliminations is still muddied by the distinction of eliminations in the N-tuple cells and eliminations in the unit(s) containing the N-tuple cells. I must admit that I don't know for sure how a Hidden Subset operation should be performed. I'll review Pat's comments above!

I did a modest test on Hidden Sets. It was far from definitive, but it did expose, in my sample puzzles, that almost all Locked Hidden Pair/Triple occurrences only produced eliminations in the N-tuple cells anyway.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby tarek » Tue Sep 23, 2008 5:30 pm

daj95376 wrote:I did a modest test on Hidden Sets. It was far from definitive, but it did expose, in my sample puzzles, that almost all Locked Hidden Pair/Triple occurrences only produced eliminations in the N-tuple cells anyway.
For this to possibly work in vanilla puzzles there has to be a hidden subset of 1 sector that results in a locked set which is a simultaneous subset of 2 sectors.

And Thanks to everyone for an interesting discussion. It has just showed me another reason why these Locked sets are easier to find ... They are frequently simultaneous Hidden & Naked subsets:idea:

tarek
User avatar
tarek
 
Posts: 2698
Joined: 05 January 2006

Postby daj95376 » Tue Sep 23, 2008 11:21 pm

tarek wrote:
daj95376 wrote:I did a modest test on Hidden Sets. It was far from definitive, but it did expose, in my sample puzzles, that almost all Locked Hidden Pair/Triple occurrences only produced eliminations in the N-tuple cells anyway.
For this to possibly work in vanilla puzzles there has to be a hidden subset of 1 sector that results in a locked set which is a simultaneous subset of 2 sectors.

Aaaaahhh, right:?:

Here's what I noticed from my very small set of sample puzzles. All Hidden Subsets contain a complementary Naked Subset/N-tuple that produces the same eliminations.

The Hidden (67) Pair has a Naked (2359) Quad in [b2] that performs the same eliminations in [r12c5]. Similarly, there is a Naked (234589) N-tuple in [c5] that performs the same eliminations in [r12c5].

Code: Select all
 *-----------------------------------------------------------------------------*
 | 1       23468   5       | 239     67-239  29      | 24789   23479   3489    |
 | 23468   23468   234     | 2359    67-2359 1       | 24789   23479   34589   |
 | 7       23      9       | 4       235     8       | 1       6       35      |
 |-------------------------+-------------------------+-------------------------|
 | 24      247     8       | 6       249     3       | 2479    5       1       |
 | 23456   234567  234     | 259     1       259     | 24789   2479    489     |
 | 245     9       1       | 8       245     7       | 3       24      6       |
 |-------------------------+-------------------------+-------------------------|
 | 2389    238     6       | 239     2389    4       | 5       1       7       |
 | 23459   2345    7       | 1       2359    259     | 6       8       349     |
 | 34589   1       34      | 7       3589    6       | 49      349     2       |
 *-----------------------------------------------------------------------------*

The Hidden (78) Pair has a Naked (34) Pair in [b2] that performs the same eliminations in [r12c6]. However, there isn't a Hidden (78) Pair in [c6] because of the 8 candidate in [r79c6].

Code: Select all
 *-----------------------------------------------------------------------------*
 | 4       367     5       | 2       1       78-3    | 9       368     368     |
 | 137     12379   1379    | 6       34      78-34   | 5       1348    2348    |
 | 8       1236    136     | 5       34      9       | 136     7       2346    |
 |-------------------------+-------------------------+-------------------------|
 | 5       369     4       | 39      7       1       | 2       368     3689    |
 | 2       379     379     | 39      8       6       | 4       5       1       |
 | 1367    13679   8       | 4       5       2       | 367     36      3679    |
 |-------------------------+-------------------------+-------------------------|
 | 9       5       136     | 7       2       34-8    | 1368    13468   3468    |
 | 137     13478   2       | 138     6       5       | 1378    9       3478    |
 | 1367    134678  1367    | 138     9       34-8    | 13678   2       5       |
 *-----------------------------------------------------------------------------*

Now, if I understand what's been discussed above, then the Hidden (78) Pair only exists in [b2], and the eliminations could just as easily been performed by the Naked (34) Pair. A subsequent Naked (78) Pair in [c6] performs [r79c6]<>8. Two steps!

Hidden Subsets never eliminate their values, and can be replaced with Naked Subsets most of the time:!:

Fortunately for me, my default solver hierarchy is all Naked Subsets before any Hidden Subsets.

So, why aren't Naked Subsets larger than Naked Quad defined ... and just do away with the Hidden Subsets?

Wait!!! Forget that I ever asked that last question!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby tarek » Wed Sep 24, 2008 7:54 am

daj95376 wrote:The Hidden (78) Pair has a Naked (34) Pair in [b2] that performs the same eliminations in [r12c6]. However, there isn't a Hidden (78) Pair in [c6] because of the 8 candidate in [r79c6].
Code: Select all
 *-----------------------------------------------------------------------*
 | 4       367     5     | 2       1       78-3  | 9       368     368   |
 | 137     12379   1379  | 6       34      78-34 | 5       1348    2348  |
 | 8       1236    136   | 5       34      9     | 136     7       2346  |
 |-----------------------+-----------------------+-----------------------|
 | 5       369     4     | 39      7       1     | 2       368     3689  |
 | 2       379     379   | 39      8       6     | 4       5       1     |
 | 1367    13679   8     | 4       5       2     | 367     36      3679  |
 |-----------------------+-----------------------+-----------------------|
 | 9       5       136   | 7       2       34-8  | 1368    13468   3468  |
 | 137     13478   2     | 138     6       5     | 1378    9       3478  |
 | 1367    134678  1367  | 138     9       34-8  | 13678   2       5     |
 *-----------------------------------------------------------------------*
Now, if I understand what's been discussed above, then the Hidden (78) Pair only exists in [b2], and the eliminations could just as easily been performed by the Naked (34) Pair. A subsequent Naked (78) Pair in [c6] performs [r79c6]<>8. Two steps!
A very nice example indeed of the transformation from hidden to naked:D

Many Machine solvers do not implement Hidden subsets because of the counterpart Naked subsets ... Human solvers still use them..

tarek
User avatar
tarek
 
Posts: 2698
Joined: 05 January 2006

Postby daj95376 » Thu Sep 25, 2008 9:04 pm

Well, everything has become cloudy again. I decided to go to Sudopedia to review Naked/Hidden Singles as well as Naked/Hidden Subsets.

What I discovered is information describing how to identify a Naked/Hidden Single, but it doesn't mention anything about where eliminations occur. The Naked Subsets page doesn't mention anything about where eliminations occur, either. However, it did contain this clashing piece of information compared to everything everyone has been telling me.

Sudopedia: Naked Subsets wrote:When all cells are located in an intersection, spotting the subset is much easier. Because there are only 3 cells in an intersection, it is not possible to find Naked Quads in an intersection. The subset can cause eliminations in both intersecting houses. A size 2 is called a Locked Pair and size 3 is a Locked Triple.

The Hidden Subsets page says specifically that eliminations occur only in the n-tuple cells. So, it doesn't matter if they are in an intersection or not.
Last edited by daj95376 on Fri Sep 26, 2008 1:06 am, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby tarek » Fri Sep 26, 2008 3:10 am

A naked subset being in the intersection is different than a hidden subset in an intersection ....

The hidden subset of 2 intersecting sectors (which means that it is a hidden subset in EACH of these sectors) will have a naked subset counterpart for EACH sector in that intersection.

tarek
User avatar
tarek
 
Posts: 2698
Joined: 05 January 2006

Postby daj95376 » Fri Sep 26, 2008 5:11 am

tarek wrote:A naked subset being in the intersection is different than a hidden subset in an intersection ....

The hidden subset of 2 intersecting sectors (which means that it is a hidden subset in EACH of these sectors) will have a naked subset counterpart for EACH sector in that intersection.

tarek

I'm not sure I follow you. Here's how I read it for Hidden Subsets locked in an intersection.

a) Eliminations are performed for non-candidate values in locked cells. A Naked Subset results.
b) Eliminations occur in both houses/units for the Naked Subset.
c) Two steps.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby tarek » Fri Sep 26, 2008 6:41 am

daj95376 wrote:I'm not sure I follow you. Here's how I read it for Hidden Subsets locked in an intersection.

a) Eliminations are performed for non-candidate values in locked cells. A Naked Subset results.
b) Eliminations occur in both houses/units for the Naked Subset.
c) Two steps.
My comments were to cast out the confusion cause by the sudopedia definitions .... There is use of the terms "Locked", "Subsets" in addition to our latest discussion.

Your latest comment tells me that you understand well how to work the hidden subset / Naked set logic very well. Your understanding of the logic "regardless of the terms used" is the primary issue. The terms then are a secondary issue (but still important).

Wording is the reason behind all of the confusion related to this thread:(

tarek
User avatar
tarek
 
Posts: 2698
Joined: 05 January 2006

re: subsets

Postby Pat » Sun Sep 28, 2008 7:08 am

daj95376 wrote:I decided to go to Sudopedia to review Naked/Hidden Singles as well as Naked/Hidden Subsets.

What I discovered is information describing how to identify a Naked/Hidden Single,
but it doesn't mention anything about where eliminations occur.

The Naked Subsets page doesn't mention anything about where eliminations occur, either.
However, it did contain this clashing piece of information compared to everything everyone has been telling me --

Sudopedia: Naked Subsets wrote:When all cells are located in an intersection, spotting the subset is much easier. Because there are only 3 cells in an intersection, it is not possible to find Naked Quads in an intersection. The subset can cause eliminations in both intersecting houses. A size 2 is called a Locked Pair and size 3 is a Locked Triple.



hey daj95376,

as you noticed, the SuDoPedia articles ( "naked single", "hidden single"; "naked" subset, "hidden" subset ) are not as clear as may have been hoped.
    which may be part of the reason why i took the trouble to spell out everything in such excessive detail (Sep.23 above).
also as you noticed, Ruud's discussion of "naked" subsets has an extra paragraph about a different term --
"locked" subsets, which is his terminology for the case where the same cells form 2 "naked" subsets (one in each house).



daj95376 wrote:The Hidden Subsets page says specifically that eliminations occur only in the n-tuple cells. So, it doesn't matter if they are in an intersection or not.


exactly, the "hidden" subset provides exclusions in the cells of the subset.

a result of these exclusions is, that these cells become (in the next "step") a "naked" subset --
within that same house (which is of course not useful).

there is, however, an interesting case where these cells are within 2 houses. ({2,4,7} in the example.)
in this case, after the exclusions of the "hidden" subset,
these cells become (in the next "step") a "naked" subset -- within each of those 2 houses.
    in the one house, this is of course not useful;
    but in the other house, can be very useful !!

daj95376 wrote:Here's how I read it for Hidden Subsets locked in an intersection.

a) Eliminations are performed for non-candidate values in locked cells. A Naked Subset results.
b) Eliminations occur in both houses/units for the Naked Subset.
c) Two steps.


yes indeed.
    to echo tarek's comment --
    we all know that you know the logic of subsets,
    even when we debate the proper phrasing.
User avatar
Pat
 
Posts: 3640
Joined: 18 July 2005

Previous

Return to Help with puzzles and solving techniques