Suset Enumeration on Sue de Coq


This post demonstrates a systematic  enumeration of subsets in the line marking of the Sue de Coq debut puzzle.  More difficult units are resolved by the scratchpad suset algorithm introduced in the previous post of October 25, 2011.

To checkpoint the sudocue first example subset list:

As we begin listing the single number susets, reaching 7,

1/2378, 2/245, 3/6789, 4/235, 6/245, 7/45, …

we notice that the cells containing 2 also contain 6 and 7.  The combined suset 267/245 describes a locked triple. It is a hidden triple, leading to four removals.

sudocue ht 267

I’ve been using the puzzle SdC 1, from Sue de Coq’s  famous  post, to illustrate various aspects of basic solving.  Now we can go back and include checking for locked sets as defined by my last post, as well as other follow up actions. It’s a sysudokie review confirming that locked set removals do not compromise this historic example. The review also shows the level of effort that systematic subset detection involves in a typical case, and how the suset algorithm concludes when a subset is not found.

SdC Cc5 ntHidden subsets can occur in box marking, but very rarely, because only slinks and aligned triples are marked. Naked triples are more common.  Two naked triples appeared in SdC 1.  The first, a nt128 in Cc5 had its effects (N1, C8) pre-empted in the sysudokie depth-first marking.  Looking at the column again, how was the naked triple identified? For one thing, the box slinks guarantee that no other 1, 2 or 8 candidates can appear in the other C cells in line marking.  The naked triple also preempts the C cells from c5, but the individual slinks do that.  The 8-clue and the np12 leave only three free cells to C and three to c5.

 

 

The second naked triple occurred when Er5 was filled with a 4 slink and aligned triples 2 and 8.  Its effect was the reduction of E to two free cells, which could be immediately filled.

SdC Er5nt

 

 

 

I think it’s clear that the time to recognize these locked sets is when they are formed.  The same is true for the naked and hidden subsets created in line marking. The line marking trace reads

3f: r9, c9  4f: r1, r3, r8  5f: r7  6f: r2. Closure: c1, c2, c3=>hp14, c7, c8.

As line marking begins with lines of few free cells, little attention needs to be paid to subsets.  A hidden subset must have a naked counterpart.  Singles are obvious. Just look for two numbers in two cells with three to five free cells, and that or three numbers in three cells with 6 or 7 free cells. Beyond that, suset it or ignore it.

SdC r7 SW fillFollowing the line marking trace, r9’s 5 and 9 pairs reach 3 cells; so do c9’s 2 and 5 pairs. In the 4f: list r1’s 5, 8 and 9 pairs don’t match cells. In r3, there’s only one pair. In r8, one pair again.

On the 5f: list,  r7 has five free cells. Its 4, 6 and 8 pairs don’t match.  All subset checking so far is easily done as we add line marks in follow up.  But r7 also completes the fill of the South boxes.

We throw the SW box into the suset grinder.  The cell size limit is 8/2 = 4.

Can we drop the eligible singles susets into our list increasing cell size order?  Not hard for me, I’m typing. The eligible singles list is

4/23, 6/12, 7/56, 9/78, 3/456, 5/467, 2/2356.

From there we generate

46/123, 47/2356, 49/2378, 24/2356, 67/1256, 69/1278, 79/5678, 37/456, 57/4567, 59/4678, 357/4567.

No subsets under four cells, so no subsets.

By the way, every suset of n cells with n-1 numbers is an Almost Locked Set, an ALS, which I delve into later.  The suset locked set app can be used to enumerate them.

SdC LMNow on the line marking trace, we’re up to  r2, and the North boxes.  We’ll check for locked sets with the final  marking diagram repeated here.

Line r2, with 6 free cells, completes the candidates, and covers the North boxes.  In r2, we can have up to a dirty triple, but our ordered singles list is

1/12, 5/19,

because the other numbers are in 4 or more cells.

In the NW box, we there are also 6 free cells, and we have 3 box slinks that qualify.  I just checked that no two  slinks  fit into two cells, a hidden pair, or three into three cells.

This leaves us with the closure lines.  The W box is divided into naked pair and triple already. The subset check of closure lines goes well with the check for slinks. The line c1 has 5 free cells, and no locked pair. But c2, with 8 free cells is another job for the subset app. The cell limit is 4, and our list goes:

4/67, 6/57, 7/58, 8/12, 1/2679, 2/2378, 9/1239, 46/567, 47/5678, 48/1267, 67/578, 68/1257, 467/5678, 78/1258, 89/1239. No subset

Line c3 is tested with the removal done and the resulting naked pair n place.  This leaves four free cells in the remainder of c3, and no more locked pairs, so further subsets.  As for c7, with 4 free cells, its two pairs don’t cooperate.

Finally, we get to c8 as line marking is finished.  Six free cells, four slinks and a triple, why not?

 

The list is  1/79, 3/23, 4/35, 5/89, 8/257, 15/789, 34/235

and we don’t get there.

Now we know that “Sue de Coq” missed no locked sets in her announcement of the technique named for her.  That’s comforting.  As for our scratchpad app for locked sets, you definitely would use it on a puzzle or solution you were publishing.  On day to day solving, or just looking for something important, maybe not.

On hidden subsets, the harder kind, watching the confinements of scarcer numbers catches many.  Then you can turn to counting free cells and imposing the subset size limit.  That leaves a reasonable number of toughies to suset or ignore.

Congrats, readers.  You have waded through my blog treatise on basic solving – that is, what you do to get the candidates.  Now the blog turns to advanced solving, what you do with those candidates.  Although you can smash almost all newspaper and magazine puzzles and most book collections with what you know now, there’s a lot more to it.  Just keep reading, OK?

 

 

 

 

Advertisements

About Sudent

My real name is John Welch. I'm a happily married, retired professor (computer engineering), timeshare traveling, marathon running father of 3 wonderful daughters and granddad to 7 fabulous grandchildren. The blog is about Sudoku solving. It covers how to start, basic solving to find candidates efficiently, and advanced solving methods in an efficient order of battle. It is about human solving methods, not computer solving.
This entry was posted in Basic Solving Procedures, Sudoku Toolware and tagged , , , , , . Bookmark the permalink.

5 Responses to Suset Enumeration on Sue de Coq

  1. richardgoodrich says:

    John,
    The following uses my trace scheme. When I marked it with slinks on a first try I could see NOT much progress would be made that way. Using the Hoduko player I entered the puzzle and printed it out both with blank squares for the unsolved and showing the candidates in a 2nd print. Now, my approach was to use candidate coloring, Originally I tried a value for the BV cell in r1c9 and quickly became obvious there was not much progress in that direction. So I looked for a BV cell where choosing a particular candidate would cause a chain of many eliminations. Perhaps, I just got lucky, but when I chose r1c5=39=3 (which is my way of saying it was 39, but I chose 3) then the puzzle just came unraveled with singletons. Perhaps I just found a “backdoor”. However, my point is that I did this with candidate coloring, but I also did it with backtracking (save & restore if you are wrong) and REALLY, while the coloring lets you see all the candidates, I really saw little difference between what I learned structure wise with coloring vs rT&E (recursive trial and error). Maybe it is the engineer in me (37 yrs), but my bosses never care how I get the job done (it is all magic to them!), I just have to get it done! And I do get satisfaction out of finding the solution – that was why my philosophical comment earlier) My trace follows: (Blessings!)

    Sue de Coq https://sysudoku.com/2011/10/13/line-marking/
    Oct 13, 2011 posting

    4..2.617…67.4…7..851..6259487361…915…8..623597…579..3…1486.9..83627.4

    495236178186794235732851946259487361367915482841623597624579813573148629918362754

    .——————-.———-.—————-.
    | 4 389 35 | 2 39 6 | 1 7 58 |
    | 1359 12389 6 | 7 39 4 | 289 2358 258 |
    | 7 239 23 | 8 5 1 | 249 234 6 |
    :——————-+———-+—————-:
    | 2 5 9 | 4 8 7 | 3 6 1 |
    | 36 3467 347 | 9 1 5 | 248 248 28 |
    | 8 14 14 | 6 2 3 | 5 9 7 |
    :——————-+———-+—————-:
    | 16 1246 124 | 5 7 9 | 28 128 3 |
    | 35 237 2357 | 1 4 8 | 6 25 9 |
    | 159 19 8 | 3 6 2 | 7 15 4 |
    ‘——————-‘———-‘—————-‘

    r1c5=39=3 => (r2c5=9, r1c3=3, r1c9=8, r1c2=9)

    from r1c2=9 => (r9c2=1, r2c239, r3c29)
    from r1c9=8 => (r5c9=2, r2c7808)
    from r1c3=5 => (r2c15, r8c35)
    from r2c5=9 => r2c7=2h(b) => (r2c9=5, r2c2892)
    from r2c9=5 => r2c85 => r2c8=3 =>(r1c213 => r1c1=1 => r2c2=8
    from r3c23=23 => r3c7823 => r3c8=4 => r3c7=9
    from r2c1=1 => (r7c1=6, r9c11) => (r4c1=3, r7c26)
    from r5c1=3 => (r5c233, r8c1=5)
    from r8c1=5 => r9c1=9
    from r9c2=1 => r9c8=5 => r8c8=2 => (r7c782, r7c7=8)
    from r7c7=8 => r7c8=1 => r7c231
    from r8c8=2 => r8c232
    from r5c9=2 => r5c782 => r5c78=48 => r5c234 => r5c3=7 => r5c2=6
    from r9c2=1 => r6c2=4 => r6c3=1
    from r6c2=4 => r7c2=2 => r7c3=4
    from r7c2=2 => r3c2=3 => r3c3=2
    from r3c2=3 => r8c2=7 => r8c3=3
    finally from r3c8=4 (missed much earlier) => r5c8=8 => r5c7=4
    Viola and fine’

    OR simply r1c5=39=3 & Solve all singles!

    • Sudent says:

      Richard

      It’s in the right spirit to be trying out your ideas on Sue de Coq’s puzzle. Your trace notation is clear, but it is bulky. You cannot go back and correct that “missed much earlier”, as you can in my trace. To answer your followup comment, I scan the compass box names and results to quickly find where I was when I missed that marking. Try that in yours. I can insert my correction and usually can amend the following trace accordingly.

      What bothers me is your unsystematic selection of a candidate to try out. You didn’t find a backdoor, you stumbled upon it. When you tell how you solved a hard puzzle, are you going to divulge the trials you made before you “found” the back door? Its not something to share, because it isn’t efficient. Regardless of what the boss understands about it, you’re not going to be as slipshod in your engineering solutions.

      In the blog, I took Sue de Coq’s puzzle, and revealed more about his method with it. When you report that it dissolves by singles when you make r1c5=3, should anybody care?

  2. richardgoodrich says:

    follow-up: the reason I started on the Sue de Coq originally was so I could “play” with your trace scheme vs mine and maybe I could understand better their relative merits. My is ever evolving. So maybe I can get to that next. I guess what bugs me most on yours is the Block Numbering Scheme you use with the map directions. Seems like the most prevalent scheme is to number them B1 to B9 top-down and left to right. Denis Botheir uses the n1r2c3 type scheme which seems very common. I am not sure when to use that or simply r2c3=1? I will take more time to understand my own and right some better rules down while I try to understand yours!
    Shalom

  3. Big says:

    John, You know I finally just got how this works! Really I was not serious about it, until I saw a guy who calls himself a “Sudoku Expert” on YouTube with a series of videos on his mark-up scheme and in every case you had already covered it in a better fashion IMO. I thought his way of finding subsets might be new, then I started looking at yours again and it just made sense. There are some mental tricks I am developing and you may have already mentioned some of them? The idea of dividing the empty places by 2 and realizing that only sets of that length are available and the partitioning of hidden/naked sets. Anyway, I can actually do it. Perhaps I just need training wheels at this point, but I use a “trace” of sorts to do my work with this.

    Great Stuff!

    • Sudent says:

      Thanks, Richard. In practice I don’t seem to need the algorithm now, but working with it sharpens the instincts. Naked subsets seem to pop out. My most effective hidden search rule is to watch for number sets confined in cells and then to confirm ‘candidate’ sets of n numbers are confined to n cells. I need to revise my material to reflect that.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s