Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Simple Precise Definitions of Naked/Hidden Subsets

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Mark

Joined: 19 Oct 2005
Posts: 30
:
Location: Arizona

Items
PostPosted: Wed Nov 16, 2005 10:09 am    Post subject: Simple Precise Definitions of Naked/Hidden Subsets Reply with quote

There's a wealth of information about subsets on this forum. Ruud's and Lummox's threads on "optimizing subsets" and "bitwise math" are particularly informative and useful.

Yet, it can be difficult to follow the finer points of those discussions unless one already has a clear notion of what a "naked" or "hidden" subset is (in its most general sense). For example, the thread on "programming the hidden subset" shows the missteps that can occur if one's notions aren't entirely clear.

So, as rudimentary as the idea sounds, I'm trying to form precise definitions of those terms. It's not easy, so any ideas or suggestions would be welcomed. Here's what I have so far:

A set S is a "naked subset" of a group (i.e. row, column, or block) iff there exist exactly |S| cells of this group such that the union of candidates for those cells is equal to S.

A set S is a "hidden subset" of a group iff there exist exactly |S| cells of this group such that the intersection of S with all candidates outside of those cells is empty.

Ugh!

What I'm shooting for here is to build up a series of simple proofs to eventually show that the positional versions of subsets will find X-Wings, Swordfish, etc. I certainly don't doubt the power of Lummox's code to do that, but the details aren't entirely clear at this point.

Mark
Back to top
View user's profile Send private message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Wed Nov 16, 2005 3:34 pm    Post subject: Reply with quote

One thing to be careful of is whether the objects of your sets are cells or candidates. I would argue that you need to distinguish them. Thus, we have a size-3 naked subset of candidates Y={1,2,7} in the cell set S={12, 27, 17}.

Quote:
A set S is a "hidden subset" of a group iff there exist exactly |S| cells of this group such that the intersection of S with all candidates outside of those cells is empty.


I might say:

Define X the set of givens in a group of cells G.
Define K the set of cells containing these givens.
Clearly |X|=|K|, because one such cell contains one such given.
Define Y the set of candidates in a naked subset.
Define S the set of cells containing that naked subset.
By definition of naked subsets, |Y|=|S|

Then:

For each naked subset S, the complementary set of yet to be determined candidates Z={123456789 - X - C} in the compementary set of yet to be determined cells H={G - K - S} constitutes a "hidden subset".

Thus, for example, if in the Group of cells {a,b,c,d,e,f,g,h,i} we have:

Code:

{2789, 1278, 19, 18, 89, 6, 4, 5, 3}
    a     b   c   d   e  f  g  h  i

then

X={3,4,5,6}
K={f,g,h,i}
Y={1,8,9}
S={c,d,e}

and

Z={123456789 - X - C} = {2,7}
H={abcdefghi - K - S} = {a,b}

The hidden set {2,7} is in cells {a,b}

As I've previously noted, all operations including

naked/hidden subsets, X-wings, Swordfish, and related grid-based analyses are all the same, just looked at from different perspectives.

see http://www.stolaf.edu/people/hansonr/sudoku and
http://www.stolaf.edu/people/hansonr/sudoku/explain.htm#grids
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Wed Nov 16, 2005 4:21 pm    Post subject: Reply with quote

I don't think you really need a proof to show that X-wings are a positional version of a naked or hidden pair. All you have to do is reformulate the way you look at subsets.

That is, when finding a naked or hidden subset you're basically taking a slice of the 9x9x9 cube which represents all possible placements within the puzzle. Either you're slicing by column and digit, by row and digit, or by box and digit and "unrolling" that to get a 9x9 binary grid. Each "cell" in the grid is either true (a possibility) or false (not possible). The 9x9 grid has two axes: Digit and position. Position is the position within that particular house (box/column/row).

Now let's say the horizontal axis is digit, and the vertical axis is position. A hidden subset appears when you have N columns (digits) that only have possibilities in N rows (positions), i.e. N digits can appear in only N cells. The subset is a new one, and yields eliminations, if there are other candidates within some of those rows; they can be eliminated. Other digits cannot appear in those N cells.

Conversely, a naked subset appears when you have N rows (positions) that can only appear in N columns (digits), i.e. N cells can hold only N digits. If there are other placements within the N columns, they can be eliminated. The N digits cannot appear in other cells.

An X-wing or swordfish (or higher-order forms) is just a different slice of the cube. Instead of slicing by a house and a digit, you're going by row and column--that is, taking just the possibilities for a single digit. The logic that applies to subsets applies to any such 9x9 binary grid, so you can find X-wings or swordfish by either column or row.

When searching for subsets, I immediately cull out any column/row where a single choice exists. This reduces the grid to size MxM, where M<=N. The largest subset you need to look for is size M/2, since the two types of subset (or, X-fish by column or row) complement each other. If M<4, then you'll find no susbets, because the smallest set would be a single which we already ruled out. One more optimization you could use, which I currently don't but should, is that if you look for one type of subset up to size M/2, you can look for the other up to (M-1)/2.
Back to top
View user's profile Send private message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Wed Nov 16, 2005 5:17 pm    Post subject: Reply with quote

Absolutely. To see the cube, just go to

http://www.stolaf.edu/people/hansonr/sudoku

and click on "3D mode"

Clicking a row or column number under the model brings up just that row or column, which shows, for instance, a {12,23,13} naked set as a simple Swordfish in that dimension.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Mark

Joined: 19 Oct 2005
Posts: 30
:
Location: Arizona

Items
PostPosted: Thu Nov 17, 2005 12:00 am    Post subject: Reply with quote

Lummox JR wrote:
That is, when finding a naked or hidden subset you're basically taking a slice of the 9x9x9 cube which represents all possible placements within the puzzle ...

An X-wing or swordfish (or higher-order forms) is just a different slice of the cube.



This is a very helpful piece of annotation to your code. I appreciate the insights provided by you and Bob Hanson on the complementary nature of differing views of the grid, and how they account for the higher-order techniques.

Bob Hanson wrote:
Absolutely. To see the cube, just go to

http://www.stolaf.edu/people/hansonr/sudoku

and click on "3D mode"

Clicking a row or column number under the model brings up just that row or column, which shows, for instance, a {12,23,13} naked set as a simple Swordfish in that dimension.


Yes. Very nice!

What I continue to wrestle with is finding a minimal language by which to encapsulate the logic of subsets. The row/column logic for the 9x9 binary grids mentioned by Lummox comes very close to nailing it. That's probably the most succint way of showing that all these techniques ultimately reduce to the logic of naked subsets.
Back to top
View user's profile Send private message
xyzzy

Joined: 24 Aug 2005
Posts: 80
:

Items
PostPosted: Thu Nov 17, 2005 2:50 am    Post subject: Reply with quote

Consider a three dimensional cube of possibilities, either true or false. The X, Y, and Z axes are column, row, and digit. To search for subsets we slice a 9x9x1 plane from this 9x9x9 cube. It's clear there are three different ways to do this; you can cut an XZ, YZ, or XY plane from the cube.

In order to search the plane for subsets, cut it into nine 9x1x1 lines. There are two different directions to do this, e.g. if you have an XY plane, you can cut lines that go along the X axis, or along the Y axis. Consider each of these nine lines as a set, s, where the elements of s are the coordinates of the nodes in the line which are true. For example, if we take an XY plane of nodes, each node in the plane has the same Z coordinate. Now we take that plane and cut it into lines that run along the X axis. Each node in one of these lines has the same Y coordinate, but different X coordinates. 's' would be the set of all the X coordinates for the nodes in the line which are true. Call the set of sets made up of the set s for each line the set S. Again, s = set of coordinates, S = set of sets of coordinates. If S is the set of sets made by slicing a plane into lines in one direction, then we call the set of sets made by slicing in the other direction, the 'transpose sets', T.

For the sudoku pattern often called 'subsets' I will use the less common name 'tuple', as subset has another meaning in set theory.

Lower case letters will refer to sets which have coordinates as their elements. Capital letters will refer to sets of sets. For example, x = {1,2,3}, y = {4,5,6}, z = {7,8,9}, Z = {x,y,z}. A subset of Z could be {x,y} or {y}, or {x,y,z}. If A is a subset of Z, then the set of all the elements of Z not in A are all called the compliment of A with respect to Z. e.g. if A = {x} and Z = {x,y,z} then the compliment of A with respect to Z is {y,z}.

The number of elements in the set x is denoted |x|, which can be called the cardinality of x. The number of sets in the set of sets X is denoted |X|.

The locked tuple rule
Consider the set of sets X, which is a subset of S. Let the union of the sets of X be u. If |u| = |X|, then X is said to be a locked tuple. The nodes u can be removed from the sets in the compliment of X with respect to S.

Elimination of singles
If s is one of the sets in S, and |s| = 1, then s can be removed from S, and any locked tuples that existed in S with size > 1 will still exist. There will also always be a corresponding set t in T where |t| = 1, which must be removed as well, so that |S| = |T|.

Complementing nature of locked tuples
If X is a locked tuple and a subset of S, there always exists another locked tuple X' which is a subset of T (the transpose sets). The nodes eliminated by X are the same as those eliminated by X'. Furthermore, |X| + |X'| = |S| = |T|.

Limiting the size of tuples to be searched for
Do to the complementing nature of tuples, a search for all tuples in S will also find the complements to all tuples in T, so that T need not be searched. It is also possible to look for locked tuples X in S such that |X| <= |S|/2, and locked tuples X' in T such that |X'| <= (|T|-1)/2. This is also sure to find all tuples in S and T, but this search is faster than the former, as fewer tuples need to be considered.

Finding useless tuples
A tuples is useless if the nodes it allows to be eliminated have already been eliminated, i.e. is causes no new eliminations. If u is the union of the sets in locked tuple X, and e the union of the sets in S not in X, and the intersection of e and u is the empty set, then X is a useless tuple.

Another way to find if a tuple is useless exists be examining the transpose sets. If t is the union of the sets in T that correspond to the elements of u, and |u| = |t|, then it follows that u = t, and that the tuple X with union u is useless. Thus the tuple X can be found useless without know what X is, just by knowing u and finding the cardinality of t.

Names for tuples
If a tuple is found in the X-Z or column-digit plane, is is called a tuple in rows. If the plane is sliced along the Z axis, it is called naked, if the plane was sliced along the X axis it is called hidden. If the size of the tuple is two, it can be called a pair, size three can be called a triple, and so on.

The Y-Z plane finds tuples in columns. Hidden if the plane is sliced along the Y axis and naked if sliced along the Z axis.

Tuples in the X-Y plane are called X-wings if they are of size two, swordfish of size three, and jellyfish of size 4. There is no naked/hidden distinction for slices along the X axis vs Y axis. There is no name for this kind of tuples of any size.

What about boxes
So far I've only talked about rows, columns, and digits while ignoring boxes. For boxes, think of the 9x9x9 cube with axes for rows, columns, and digits translated into a new cube with axes for box, position in box, and digit. Each X-Y plane has been translated so that all the nodes are still there, they are just in a different order. For the row/column/digit cube, sudoku requires that each line of cells you make in any direction have one and only one node set to true. For the box/position/digit cube, this requirement still exists for the position axis and digit axis, but NOT along the box axis. That would be like saying that each digit needs to appear once in the upper left corner of all the boxes. Because there is no constraint in the box axis, we can't search for tuples in the box-digit and box-position plane, only in the position-digit plane.
Back to top
View user's profile Send private message Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Thu Nov 17, 2005 6:02 am    Post subject: Reply with quote

here is my attempt to describe subsets (naked or hidden,
that's the same here) in exact-cover-speak.
In fact, it's even more general but for sudoku it would
probably essentially reduce to naked/hidden subsets.
I pretend, that probably most constraint programming
with alldifferent can be done more nicely in exact-cover-speak,
but I couldn't find whether anybody had already tried this.
I had email with W.vanHoeve, he wrote a large online-survey
about alldifferent constraints, but wasn't even aware that these
can be transformed into exact-cover problems, nor had he
any reference for this.
I'd really like to know, whether this sort of formulation has been
described elsewhere.




----------Definitions:
exact-cover problem:
given a binary n*m matrix A with n rows and m columns,
find a subset S of the rows which sums to the all-1-vector.
Row r is adjacent to column c, iff A(r,c)=1
("placement r satisfies constraint c").
Let _S be the set of all solutions.

Two rows(columns) are called adjacent, iff there exists a column(row)
to which they both are adjacent.
For a set D of columns(rows) let N(D) be the set of all rows(columns)
adjacent to any column(row) in D.

The exact-cover problem is being solved by recursively selecting some
row r, deleting columns N({r}) and rows N(N({r}) and thus
reducing it to a smaller exact-cover problem called E(A,r).
Just deleting row r without any other changes gives problem E(r)

For any column c, the exact-cover-problem A has a solution S,
iff there exists r in N(c), r in S such that the reduced exact-cover problem
E(A,r) has the solution S-{r}.


---------------subsets-theorem :
Let D be a set of k different,mutually nonadjacent columns.
Assume N(D) partitions into k disjoint sets R1,..,Rk
each consisting of mutually adjacent rows.
If r is a row not in N(D) but adjacent to all rows in R1 then
_S=_S(E(r)) , so r can be deleted.
proof:
This is because placement r would delete all of R1 but none of D.
Any subsequent placement q in Ri deletes all of Ri and one of D,
so one in D would be left without adjacent rows.

In case of sudokus,the Ri would typically be given as subsets
of neighbor-sets of some columns ci adjacent to D. Ri<=N(ci).


example: (r:row,c:column,s:symbol, "851" is short for r8c5s1)
suppose after some placements block 8 has these candidate-sets:
Code:

r7c4:{4,5,6,9}  r7c5:{4,9}        r7c6:{5,6,9}
r8c4:{2,4}      r8c5:{1,2,3,4,7}  r8c6:{1,2,3,7}
r9c4:{2,5,6}    r9c5:{1,2,7}      r9c6:{8}


we have D={b8s1,b8s3,b8s7},k=3,N(D)={851,853,857,861,863,867,961,967}
R1={851,853,857}
R2={861,863,867}
R3={961,967}
r=854, N(r)>=R1, r not in N(D), so r can be deleted
"hidden triple in block 8 for symbols 1,3,7"

extract of the exact-cover-matrix: ("o": 1 "." : 0 )

Code:

   |r8c5 r8c6 r9c6 {b8s1,b8s3,b8s7}=D
---+--------------------------------
851| o    .    .     o    .    .
853| o    .    .     .    o    .
857| o    .    .     .    .    o
861| .    o    .     o    .    .
863| .    o    .     .    o    .
867| .    o    .     .    .    o
961| .    .    o     o    .    .
967| .    .    o     .    .    o
854| o    .    .     .    .    .
   
                   ---------------
sum  ?    ?    ?     3    2    3

Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Thu Nov 17, 2005 12:40 pm    Post subject: Reply with quote

Quote:
Tuples in the X-Y plane are called X-wings if they are of size two, swordfish of size three, and jellyfish of size 4. There is no naked/hidden distinction for slices along the X axis vs Y axis. There is no name for this kind of tuples of any size.


As also pointed out in this excellent summary, each "locked tuple" has its complement. In the case of X-Wings and such, this complement appears in the 90-degree rotated direction. That is, while it is common to think of an X-Wing as a grid-like object that disallows candidates along both its rows and columns, I like to think of them as only disallowing along one coordinate. In effect, the other coordinate is, in this way of thinking, taken care of by the "other" complementary locked tuple.

If you pick a puzzle at Sudoku Assistant, http://www.stolaf.edu/people/hansonr/sudoku, and just click the numbers on the block that reads

Code:
1 2 3
4 5 6
7 8 9


Then these will pop right out at you. Essentially, every pattern of 1s or 2s or 3s forms a square mxm grid. In some cases, this grid can be dissected into two complementary perpendicular (intersecting, we hope!) sets, one X-like and the other Y-like. Thus, if you find a row-based X-Wing in a 5x5 grid, there is also there, "hiding" in the grid a column-based swordfish. One is 2x5, the other is 5x3. Together they form a 5x5 grid.

It's the same as naked and hidden.

Nothing more than was said above, just clarifying.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron