Suset Jelly in nrc Space


Here we work through an advanced supersymmetry example from The Hidden Logic of Sudoku, without the symmetries.  The humanly practical tools of Sysudoku are entirely adequate to the task. The theme of this review is that the burdensome emulation SudoRules, Berthier’s seeming emulation of human solving, is just unnecessary.

17-1007-basic-tr

The basic solving trace of Royle 17-1007 shows a stingy bypass. I take it to the first highlight, a naked quad. Or did you note it as a hidden pair c8hp17?

Did you notice that 5 and 9 nquad candidates are entirely within the SE box?  One 5 and one 9 must be true.

17-1007-nquad-1Then, on the first 7f: coming up, on r1, a naked quad 1789, or perhaps the hidden triple 246 soon to emerge.

 

 

 

 

 

 

17-1007-nquad-3

This trims the free cells back to four, and we eventually get a third naked quad in r3, with two numbers confined to the NW box.

17-1007-finish-trThe finishing basic trace shows the second and third nquads plus a hidden pair in between, and only one line left for the close.

 

 

 

 

17-1007-urFollowing the Sysudoku Order of Battle into advanced, one of the aligned pairs leads to unique rectangle removals. Either 9 forces 7r3c3, and a deadly rectangle.

Next post is a review of  Berthier’s position on unique rectangles and multiple solutions. In THLS,  UR is in the last, “miscellaneous” chapter and must be applied after regular fish.

On the homework assignment, you were to skip the bv scan methods and go directly to X-panels. I have a particular one for you.

17-1007-9-panelLet’s say you wanted to find every regular fish  on the rows. Suset enumeration does it. Start with a list of Susets, the row number/9 positions along the row. Then build larger susets by taking the union of numbers with the union of positions of every pair of susets. Since there are two blank rows, there is no need to go any further than four positions. Three rows and three positions define a swordfish; four of each, a jellyfish.

For the full story on limits on regular fish, go to What Regular Fish to Fish For (3/27/12).

17-1007-susets

See if you can discern the systematic sequence, that skips no possibilities, here:

The jelly suset is 1247/2469. Get it?

Less systematically, and less comprehensively, you get there faster making combinations of the lines with the least positions and the most overlap in positions.

Of course, none of this is usually necessary. We can find most fish readily with a blank line tally on the panel. For row fish, mark (-) a set of lines on a blank column in the same direction. Then on a blank line, mark(+) the covered positions(columns). This is done on the left panel below. On the right panel is the blank line tally for the complementary swordfish along columns, that has to be there.

17-1007-jellysword

The jelly and swordfish have the same victims. In fact they are subsets of a different form, different views of the same thing, like the complementary naked and hidden subsets of a unit. That is why susets apply equally to both subsets and fish. Regular fish are subsets.

17-1007-xy-chainAfter these removals, the puzzle is finished quickly by an XY wing, extending to a long XY chain wiping out every other 7 and confirming every 9 along the chain.

 

 

 

 

 

 

17-1007-xy-railAlthough Berthier rates every chain link as an added level of logical complexity, XY chains are extended to such length effortlessly. In fact, it pays to extend XY rails as far as possible, because multiple chains can be systematically whacked out of a common rail curve. Here is the rail underlying the two adjoined chains above.

 

17-1007-nice-loopNow I must confess to the reason for my request that  you skip the bv scan in the Royle 17-1007 in your homework. It is this XY nice loop, found on the same bv map before the SOB calls for X-panels. It removes the same candidates, and destroys the fish, and along with them, the illustration of supersymmetry for which it was chosen.

 

 

When I first took up XY chains in Sysudoku, I disputed Denis’ statement that “XY loops are useless”.  Of course this position completely overlooks nice loops like this one, but it comes from the fact that a long chain with a loop can be broken up into shorter chains with the same victims. To Berthier,  longer chains, being of higher logical complexity, are therefore useless.

In the sense of his words, Berthier is right, even here.  The above loop is a series of two XY chains.  But to those not adhering to his unusual definitions of those words, some of his proclamations are ridiculous. More on AIC loops later.

royle-17-692Next we examine the unique rectangle methods Berthier recommends, and his conclusion that they should only be employed as a last resort, because they assume uniqueness. Do you believe that?  Here is Royle 17-692, a puzzle that demonstrates that this conclusion comes with a cost. Maybe you’d like to fill in the candidates, and see what you would do with it, beforehand.

Posted in Advanced Solving, Berthier, Expert Reviews, Sudoku Toolware | Tagged , , , , , , | Leave a comment

Fishing in Lake Supersymmetry


This post reveals that the symmetries and supersymmetries of THLS, as applied to subsets and fish, are identical to a Sysudoku tool that reduces these Sudoku entities to numerical input for a well-known algorithm.  This shows conclusively that maintaining extra grids for symmetry transformations is not a practical way to detect these entities.

First, the homework on the hidden triples of Royle 17-32227. The basic trace to the point of collapse reveals only naked triples,

17-32227-trand the grid at the second one, in line marking, reveals the reason.

17-32227-nt-gridWithout the candidates uselessly introduced before solving even begins, the hidden triples are replaced by naked triples.

Is THLS symmetry  more of a problem than a solution? The required number scanning  and symmetric grid surveillance are a BIG problem for human solvers.

 

 

Now we can turn to the super hidden transformations of THLS, and Berthier’s suggestion that they belong in every solver’s tackle box. We start with the super hidden pair, the regular fish we have been stubbornly referring to as an X-wing.

In Royle 17-6973, Denis Berthier shows us the puzzle in in nrc space and in rcn space. We get to see it, after the LI_0 elaboration, when most of the number scanned candidates have been removed, and when SudoRule rules are reported to have revealed a 5-wing. You can find the wing in Figure 8, page 105 in my THLS edition, and  the naked triple transformed hidden triple on the Figure 9 grid, page 106. You’ll know just where to look after reading a little farther.

17-6073-5-wing-gridHere is the same 5-wing, as it appeared in our almost completed line marking.  I was on r1, when I realized that I was adding the last and second 5 in c7 and the slink matches the 5’s in c1, creating the 5-wing.

Spotting X-wings is that easy in the follow up to every marked line.

 

Now to look at it through supersymmetric glasses, let’s go to the X-panel, where we look for higher order fish, among other phenomena. There, at least we have all basic candidates and can see the 5’s alone.

17-6073-5-wing-panelsAt left is the 5-panel with blank line markers for the column fish (|) and the removal rows(+). Is the 5-wing harder to see than a naked pair? Not much.

 

At right is the corresponding naked pair in r5. Row 5 represents the distributions of 5’s in all columns.  In fact, the row is the starting suset list for generating all column wise 5-fish.  Of course the full rnc grid would have the mapped other numbers into into all columns. Besides the 5-wing, all column-wise regular fish of 5-candidates are represented in these numbers.

Yes, I was into supersymmetric fishing in 2012, and didn’t know it. It was long before encountering THLS. In Casting for Regular Fish, you’ll see a suset list I used before discovering the much easier blank line tally. I left that in for tough cases, and later, applied suset enumeration to the finned, kraken and mutant fish that are missing from THLS.

When you interchange number and row for supersymmetry transformation, you are recording the column positions for true candidates of the panel number. Interchange number and column for a suset list of row fish. And by the way, we do this mapping only on the candidates remaining after basic, and bv scan. And only when the fish are a lot less evident than here.

17-6073-5-sword-panelsAnd speaking of row fish, it so happens Royle 7-6973 provides an example, undisclosed by THLS. On the 5-panel is a row oriented swordfish. For row regular fish, the supersymmetric mapping is to interchange number and column. Can you spot the 3 numbers in only 3 lines that mark the swordfish, without looking at the left panel? If so, you just did a suset enumeration, pilgrim.

For row or column fish, the supersymmetries list the positions along the line, the very resource the lines are competing for in a regular fish. When there are n lines needing n positions, no other lines can have one of the n positions. That is how fish should be explained.

But as shown many times in these posts, the THLS symmetries and supersymmetries are totally unnecessary for regular fish. If the blank line tally on the X-panel leaves any doubt, list the line positions as susets, and do the enumeration, starting with the sparser lines, of course.

But perhaps you’re unconvinced because we only saw the X-wing and swordfish in Royle 17-6973?

royle-17-1007In that case, let’s spend one more post on it, and take up a very challenging THLS example, the super hidden quad or jellyfish example, Royle 17-1007. Follow the SOB. You’ll find three naked quads on your way through line marking, and may encounter a unique rectangle, and a twisted Sue de Coq. Skip the rest of the bv scan and go directly to the X-panel for the jelly, and come back afterwards for the finish. We’ll blank line tally the jelly, and do a full suset enumeration on it, just to show off the sysudokie tackle box

Posted in Advanced Solving, Berthier, Expert Reviews | Tagged , , , | Leave a comment

Hidden Logic Box/Line Interactions


This post looks at the brief and very late THLS treatment of box/line interactions in rc space. I say late, because box/lines (1/31/12) are essential in basic marking of candidates. But in The Hidden Logic of Sudoku,  box/lines are introduced after the application of symmetries to regular fish. Fish require a full set of candidates, being the expression of competition among candidates for positions in the solution.  This means Berthier has to use box/lines in THLS elaborations before explaining what they are.

Checkpoints for Akron Sudoku 16 participants are at the end of this post, along with a blog feature announcement.

17-13727-marked-htBefore we talk box/lines, however, let’s checkpoint the three hidden subsets which, after the mysteriously appearing 8r3c3, devastate 17-13727.  SudoRules first finds the hidden pair NWhp56, which you found in the bypass, and removes 3, 4 and 7 candidates.  Then it finds the hidden pair r2hp56, removing candidates 4, 7, 8, and 9 from r2c9. Without this help, it would still find the hidden triple NEht569.

As is usual, you probably saw the naked quad NE3478 first, but that would be a higher level of logical complexity for SudoRules. More normally, you would be reviewing boxes for subsets immediately after the third crossing line is marked. This example illustrates how they can jump out earlier. Either way, it’s much easier to deal with them when only the relevant candidates are present.

Now let’s turn to box/line interactions, and what THLS says about them.  On the positive side, Berthier covers the basics in Chapter IX with four rules, two for rows and two identical ones for columns.  I can best explain them with a chute schematic.

boxline-schematic I call the intersection of a box and line a chute, and the remaining cells of each unit outside the chute, remainders. There is a line remainder and a box remainder for every chute.

SudoRules first two box/line rules RiB and CiB (Row and Column) state that if there are no candidates of a number in a line remainder, then candidates of the number can be removed from the box remainder. It’s obvious why, but we can miss this by failing to spot the empty line remainder. The follow up process of line marking catches this mistake, as we look for line slinks to mark.

The other two box/line rules BiR and BiC state the opposite. If there are no candidates of a number in the box remainder, then candidates of the number can be removed from the line remainder.  In Sysudoku basic, it is box marking where this kind of box/line is detected. We find the aligned slinks and triples that are only possibilities for candidates missing from the box remainder, and use them to sweep neighboring boxes along the line.

Reading through a SudoRules trace, we see this kind of step frequently:

boxline-bic-quote

On the Sysudoku grid, we see the 3-slink or aligned triple, and know that the elimination took place.

Clearly, what we mark as a box/line in a trace (bxl) is an instance where the last candidate of a number is removed from one of the remainders. This little comparison of traces reveals a serious deficiency in the wordy SudoRules trace of THLS. The pictured step is followed by others, but we have no idea which of the later steps are dependent on this one.

Just so you know, when these four box/line  interaction rules are added, rule set L1-0 becomes L1.

rib-to-rnBerthier suggests one of his hidden symmetries “for detecting” conditions for each of his four box/line rules. For example, for the RiB box/line, in which the absence of a line remainder candidate removes candidates in the box, he suggests rn-space.

The chute contains a true candidate, in a slink or an aligned triple. In rn-space all candidates of a number will map into a single column. Cells of that column list the row locations of those candidates. In the chute row, the cell of the number column will contain only the numbers of columns crossing the box.  Although box divisions are preserved in a limited way, I don’t agree that scanning down a column looking for the exclusive presence of the “right”  range of numbers is anything like as easy as spotting the mandatory slink or aligned triple above in standard rc -space.

I have the identical objection to using rn-space for spotting CiB box/lines. And use of bn-space for spotting BiR and BiC box/lines, the deployment of slinks and aligned triples, is even more of a stretch.

With his box/line interaction rules, Berthier completes his coverage of the elements of Sysudoku basic solving, but without any reference to strong links, weak links, or bi-values cells.  He has leaped ahead into advanced solving with regular fish, in a hidden logic manner I review in the next post.  This blurring of any distinction between basic and advanced solving goes right along with the joyless practice of number scanning candidates before any logic is applied. From the human engineering point of view, a very bad idea.

royle-17-132227Before taking leave of THLS basic solving, I would like for you to see what actually happens to many a hidden subset facing the systematic basic solving offered here. The interaction chapter traces two solutions of Royle 17-32227, one with and one without, box/line interaction. The sysudokie way is better than either.

See if you can get there first.

 

 

titles-page-alertPlease notice the following announcement:

 

 

Now for the final bulletin from the Akron Sudoku Tournament of 2016:

Here is the grid of Akron Champion 2016 as the collapse is beginning. Line marking has reached the last line, row 4, where a naked triple 178 wipes out five candidates, and supplies candidates r178r5c5 for another naked triple in column 5, taking out three more. The solution follows immediately.

akron-16-line-markedfinal-16-nt-trThe line marking sequence by increasing free cells, and the beginning collapse, can be read from this trace:

Did our stage performers solve this puzzle?  Most likely, it was a matter of having the most cells right, but the Akron-Summit County Library will never tell.

FYI, the Round 3 puzzle is solved by the Sysudoku bypass as follows:

akron-rnd-3-tr

It takes a quick brain, and a quick hand, to do it in 20 minutes.  It could be very instructive to follow the above to a solution without a single guess. You just have to be willing to dig out the reason for each step. No excuses, please. Its all on the Traces page.  Enjoy!

Happy Thanksgiving!

 

Posted in Basic Solving Procedures, Shortz | Tagged , , , , , | Leave a comment

Hidden Candidates of Hidden Logic


This post calls out the useless reporting scheme in place throughout The Hidden Logic of Sudoku, with a checkpointed hidden triple example that sysudokies have solved as homework. The Akron Tournament final checkpoint is at the end of this report.

Royle 17-13727 is chosen in THLS as “the one with the shortest resolution paths (apart from NS and HS) among those requiring HT.”  Denis is referring to naked and hidden singles and the hidden triple, with “hidden” having its usual meaning, not involving “hidden logic”.

My readers who have not seen a copy of THLS might be thinking the grids and traces in this book are somewhat like those they are seeing in Sysudoku checkpoints, and generating in sysudokie homework. At this time in the review, they might expect to see a hidden triple in nrc space and its counterpart naked triple in a symmetry grid. In fairness, subsets would be shown embedded in the number scanned and transformed sea of candidates that normally inhabit grids in the basic stage of solving.

Readers of THLS know that none of this is available. Unless readers generate it for themselves.

For every example puzzle THLS gives three grids, all in nrc space:  the initial givens, the final solution, and a middle grid, the elaboration, representing the product of rules of logical complexity up to, but not including, the method being illustrated.  The incredible thing, if you haven’t seen it, is that no candidates appear in the elaboration, only clues.

17-13727-l2-elabFor your Royle 17-13727, Berthier reports the SudoRules L2 elaboration shown here. L2 includes hidden singles and pairs in both senses of hidden, with symmetries and supersymmetries.  We’ll get to it shortly, but just so you know, L2 includes X-wings through THLS supersymmetry. Beneath the three grid,  you are told in text, where the hidden triple is, and what it removes.

 

 

17-13727-bm-trYou don’t get to see the hidden triple in any context. My question is, without candidates, how does a THLS reader make any evaluation of any example results without doing their own basic solving?   You deserve better. After bypass and box marking, my box marked grid shows two additional resolutions to be made in line marking, namely 8r3c3 and its effect, 2r4c3.

17-13727-nquadMy scan, for fewest free cells and shortest line fill strings, portends a miserable line marking. But I get a break on the second line:

A naked quad 3478 jumps out in NE, leaving only three cells for 5, 6 and 9. This hidden triple exists only when the number scan clutter is added. The box/line removes other 7’s in r1.

The collapse goes on from there, with no need to fill any more lines, and without the 8-clue missing above. It results from a cause held in reserve, at the very end. So I’d really like to know where it came from in the THLS elaboration. Can you help me out there? Yes, I looked for a possible 8-wing from supersymmetry in L2

17-13727-final-tr

17-13727-ht-gridTo resolve my mystery, I number scanned the candidates around Berthier’s elaboration clues. That explained nothing, but it does show the state of the grid, as Berthier reports the post L2 trace to his hidden triple resolution. SudoRules finds the two naked pair eliminations in E, the two hidden pairs, and the hidden triple as a naked triple by symmetry.

The triple would be L3, you know. The naked quad, L4. Does any sysudokie care?

For homework, find these in the sea of candidates here, and imagine the amount of searching it takes to find all of them on a cluttered grid such as this.  I’ll mark them on the grid next time. The next post will also review the THLS treatment of box/line interaction and its relationship to slink marking. Note on your trace or mine how Sysudoku basic finds all of the hidden subsets, without grid transformations and with searching limited to one unit at a time, and with suset backup for diabolical cases. Think about it.

akron-16-bypass-gridNow for the Akron 2016 checkpoint This is the grid after the slink marking bypass. Translation: Slinks are strong links. In the bypass, you use them, but don’t write them down. The only pencil marks are for conjugate pairs or other subsets.

 

 

final-16-bypass-trYou can read this trace! Boxes are denoted by compass notation, C being the center box. Lower case r, c are row and column. Naked pairs are “np” and the two digits. The reader supplies the reason. The order is left to right and down each ramp before the next cause. Effects are indented under causes. Lists of effects are read left to right.

Some steps may not be apparent if you’re not used to doing this. These hints might help you catch on to what is going on:   S2m => N2, SE3m & SW3m => SE3, S5m => N5.

final-16-boxm-trNow we continue with the box marking, in which we mark the slinks and aligned triples in the corners and sides of cells. Any time only two candidates of a number remain in a unit, these two are strong link partners. The “m” denotes a box slink (marks).

In Sysudoku, strong and weak links, slinks and winks, are between candidates and not between cells, as many writers suggest. It’s amazing how much confusion this mistaken concept has caused.

final-16-boxm-gridHere is the result, ready for the final step of finding all candidates, the line marking. If the puzzle gets this far, it’s worthy  of the stage at the Akron tournament. Much farther, and it’s too difficult for that.

For line marking, find all the cells with only two candidates. Mark them. These are bi-value cells, very important for advanced methods. I call them bv.

Now go down rows and then left to right, looking for  the first line with the fewest free cells. Its row 2(r2) here. If we hadn’t found the naked pair 2,4 in the bypass r1 would start the 3f: list, because the bv 17 cells are not free. They are reserved for 1 and 7.

For r2, I have three free cells to start the 3f: list.  Now you make up a string of numbers that can possibly be added to the free cells. I call it the fill string. My fill string for r2 is 14. I don’t have to include 9, because no 9 candidates can be added. With this much to go on, see how much line marking you can do, and tune in next week’s post for the checkpoint on the fate of the final puzzle. If you want to look at more line marking examples, browse around. Look at the Find It page. Any basic solving posts will do, including the Dave Green Labor Day weekend posts you can scroll back to.

akron-rnd-3I will also have a bypass trace on that round 3 puzzle.  Build your own trace to match. The experience with the championship puzzle bypass will help. For those not fortunate enough to be in Akron November 5, here is a copy of the Round 3 puzzle.

 

 

 

Posted in Basic Solving Procedures, Berthier, Expert Reviews | Tagged , , , , , | Leave a comment

Hidden Logic Symmetries of THLS


This post explains SudoRules’ complementary grid transformations that, as The Hidden Logic of Sudoku demonstrates in many Royle 17 examples,  converts hidden line subsets into naked line subsets, and box subsets into line subsets. Of possibly more interest to sysudokies, these transformations also convert between bv and line slinks.

For special friends attending the Akron Sudoku Tournament 2016 in particular, I also have a sidelines report on the two hardest puzzles, in the next two posts. The championship puzzle is at the end of this post, for everyone that missed it. As usual, I didn’t come close to getting on the stage.

In Chapter 1 of THLS, Denis Berthier introduces the concept of the Sudoku symmetry, by this definition:

thls-symmetry-definition

Here are the grids for the three”hidden” symmetries that THLS advocates, applied to Royle 17-3 given clues, along with this definition:

17-3-four-grid-spacesAt the upper left is the grid of given clues, in what Berthier calls row-column, or rc space. For purpose of explanation, let’s label it nrc space. Upper right is the representation of the same puzzle in row-number, or THLS rn space, our crn space. The transformation is the interchange of a clue’s number with its column.  For example, 2r1c9 becomes 9r1c2. To make this transformation, move across each row, using the number for placement of the column as number.

At lower left is the grid of 17-3 in number-column, or nc (rnc)space. The transformation here is to move down columns, interchanging each clue’s number with its row, 3r2c5 becoming 2r3c5. Trying this out across the grid, I’m sure you couldn’t help but notice that, contrary to the definition above, nc space is not a valid Sudoku grid. Although it is not immediately revealed, neither is 17-3 crn space. These two transformations do not preserve the Sudoku requirement that a solution box contain exactly one of every number!  They do preserve the grid as a Latin square, but not as a valid Sudoku.

There are two primary reasons for Berthier’s introduction of the rn and nc symmetries.  One is to simplify the recognition of subsets in lines. Denis shows that they convert hidden singles to naked singles, hidden pairs in lines to naked pairs, hidden triples in lines to naked triples, etc.  In back passages THLS admits this is burdensome and unnecessary.  For hidden subsets, look for n numbers confined to n cells in the unit. This is effective for lines and boxes, and there is the scratchpad suset algorithm (10/25/11) for cases difficult to verify.  And besides, to apply these symmetries, you must transform, not just the clues, but every candidate, into at least two grids.

The other primary reason for the crn and rnc spaces is to define “hidden” chains. In later posts of this review, I will show that the necessity for such chains is not demonstrated in THLS, but as a matter of interest, these transformations interchange bv and line slinks in one direction.  Sysudoku advanced techinques and forcing chain“seeing”, missing in THLS, appear to compensate fully for any lack of hidden chains, and at a more practical computational complexity level for human solving.

If you don’t have a copy of THLS, I won’t ask you to generate and convert all candidates to duplicate Figures 2 and 3 on pages 37 and 38.  Just realize that in the crn and rnc spaces, you cannot use a box clue to eliminate candidates of the same number from cells of a crossing line. Nor can you trust a box to contain every number. That makes it tough to get eliminations and confirmations in these spaces to transform back into standard nrc space.

I haven’t described the bottom right symmetry above, the representation of 17-3 in box-square, or nbs space. Here, each row lists the contents of a box, with the boxes numbered in keypad order. The position of the number along the row signifies its cell position within the box. Each column shows the numbers in cell position.  THLS refers to a cell positions as a “square”. This representation plays a very small role in THLS. It allows certain “Sudorules” about lines to be restated for boxes “by analogy”.  The numbering of squares, and the location of candidates by squares permits the suset algorithm to spot subsets in boxes.

If you lost any hair reading its THLS version, the panel above corrects three nbs grid typo’s in my copy of the First Edition.

royle-17-13727Next, regular sysudokies can work a very hard on an interesting puzzle, that reveals how hidden subsets are actually uncovered in Sysudoku basic. I will use it to call out THLS for its obscure reporting. It is Royle 17-13727, with the SudoRule solution and Berthier’s report on pages 120-1. If line marking is as tough as it looks, you’re missing hidden subsets.

 

 

akron-final-2016If you care to imagine yourself completing a puzzle with a big chart board and a big black marker in front of an audience of Sudoku fanatics, here is the 2016 championship puzzle of the Akron tournament. To compare with my checkpoint trace in the next post, start with the bypass, which is all clues except for naked (conjugate) pairs, while tracking strong links in your head, and trying to resolve units of three free cells or less. In the second stage (box marking), write in the strong links, adding clues they resolve. In the third, fill in candidates in lines in order of increasing free cells (line marking). That’s as far as you have to go.

The puzzle is by Will Shortz, who kindly provides all puzzles for the tournament, on condition that they not be identified by publication or number. So if you happen to find out, keep it quiet. OK?

Posted in Basic Solving Procedures, Berthier, Expert Reviews | Tagged , , , , , | Leave a comment

Naked Singles in SudoRules


This post reveals how naked singles are produced, in Berthier’s rule hierarchy of increasing logical complexity,  by single rule that is a member of the set of rules for every resolution method. This explains why number scanning candidates, and maintaining multiple grid spaces, clearly impractical in human solving, is justified in The Hidden Logic of Sudoku as logically elegant and computationally feasible.

royle-17-3-numscanHere is the number scanned version of the grid, immediately after the 25 hidden single steps of Denis Berthier’s trace on p. 85 of THLS. This was much less work than number scanning the original puzzle. Now imagine the condition of your paper puzzle at this point, after erasing all the candidates removed for the sin of seeing the  hidden single clues added so far.

On this grid, another hidden single c6hs1 is available, but the first naked single to emerge, SEns9 has precedence.

royle-17-3-naked-s-trWith your number scanned grid, you can now follow the sequence of naked singles, as each one removes candidates to produce one or more new naked singles, as traced at left. The run ends when the naked singles are use up, and a box hidden single is retrieved from the reserve list.

royle-17-3-after-ns-runAfter this run, the grid is much clearer and your paper puzzle, more tattered.

 

 

 

 

 

But now, Berthier’s trace in 2-D descends sharply into collapse:

royle-17-3-final-singles-trNaked singles are detected by the simplest ECP rule, applied with every candidate elimination. The rule promotes a candidate to a clue when it is the only one one left in the cell  That makes ECP 1 a member of every set of rules. It always overrides all other rules.

Berthier labels the ECP rules, plus the hidden singles rules, as L1_0.

 

THLS introduces the hidden logic grids next, to show how they transform hidden singles in lines to naked singles in lines. These transformations multiply the data the computer solver carries along, to be updated with every new clue. In THLS, addition of all this work is not considered to increase the logical complexity of a set of rules.

After the homework, you have very different opinion of the added computational complexity, I’m sure. But number scanning is a small part of it.

 

Posted in Basic Solving Procedures, Berthier, Expert Reviews | Tagged , , , | Leave a comment

SudoRules’ Hidden Singles Reverse Engineered


Here, Denis Berthier’s trace of a SudoRules basic level puzzle in his The Hidden Logic of Sudoku is reverse engineered to show how it finds hidden singles. Although the method is related to line marking, it is not a practical model for human solving.

Before the heavy lifting, let’s checkpoint the homework with a sysudokie trace of the bypass plowing under Royle 17-3:

royle-17-3-tr

In case you missed any of these:

N1m dublex xhatch dublex SW1m => NW1, SE1 is a 6f:c7 hidden single(hs) , S5m xh NE5m => SE5,

N wall => N2, SW2 is a 3f: r8 hs, W3 is a 4f: c2hs, C7 is a 4f:r6hs, the SW square => SW3,

NW6 is a 4f:r1hs, NE5 is a 3f: r1hs.

In THLS every technique is called a resolution method, and is a set of rules of a given level of logical complexity, added to all simpler rules. Royle 17-3 is the first puzzle introduced in THLS, because it is solved with singles, hidden and naked, the least logically complex set of rules. All SudoRules consist of a condition to be met, and an action to be taken, either the removal or confirmation of candidates.

Rules are stated this way, because solving begins with each cell containing candidates of all values. From there, SudoRules starts with the first four rules, Denis Berthier’s Elementary Constraint Propagation rules. The very first ECP rule removes all but the given clue from the clue cells. The next three remove candidates of the given clue number from the three containing units, the row, column and box. This is appropriate computer coding for number scanning.

It may be hard to believe, after the bypass homework and checkpoint, that Royle 17-3 can be solved by singles only, but if we understand this, we will better understand what experts are talking about when they dismiss a puzzle by saying “only singles from here”.  For one thing, a cross hatch clue can be interpreted as a hidden single in the box under attack. And a clue we attribute to a dublex is also a hidden single in the line. In the checkpoint trace above, the wall and the square are just names we apply to restrictive patterns of clues that make the cross hatch or dublex work. Puzzles collapsed by the bypass without higher order subsets, we can consider to be solved by singles, although our bypass is much more interesting.

Fortunately THLS gives us a trace of the SudoRules solving of Royle 17-3, on pages 84-85. I’ve reproduced part of the trace here, with each step identified as a hidden single in the right column. For hidden singles in lines, the number of free cells are displayed.

royle-17-3-singles-trLet’s use this trace to reverse engineer the sequence of basic operations of SudoRules. Fill a copy of the puzzle, as you read down the table and the comments below on each step. That way, you have the state of the grid on each comment. 

royle-17-3-singles-remarks

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

After posting the 25 steps, your Royle 17-3 grid should look like this:

royle-17-3-after-25-hsI’m sure you noticed that in spite of having all candidates available, many solving opportunities are missed. That is due to the restriction to singles, ignoring all higher order subsets, slinks and aligned triples.  I think you can agree that adding rules to cover basic and advanced solving, even if all known techniques are covered, will not create a manual for human solvers.

 

 

Actually, by putting all of the “depends on” observations together, we can see how SudoRules sequences through its hidden singles. To make that easy, I’ve added step numbers in the 2-D dependence tree:

royle-17-3-hs-2-d-tr

It’s clear that SudoRules doesn’t start over after posting each hidden single. It mimics our 2-D trace in several ways. The hidden single rules are applied to each of the containing units, for all incomplete numbers, but only one is followed up on the grid at a time, the rest being held for later. In the lists for posting, singles of the same number are followed up first. Although a box was chosen over a line at first, boxes are not taken ahead of lines in later lists, so it appears that grid location of the single may be a tie breaker.

So how is the SudoRules manner of finding hidden singles so different from ours?

A hidden single occurs when there is only one cell left in a unit for a missing number. We scan the grid, seizing on patterns that point to such an occurrence.  The human solver does best with a variety of visual tools and less data to process at one time. To us, data not being applied is distracting clutter. We hate boring tasks like number scanning and use line marking only as much as we have to. Computer solvers start with number scanning. As we saw, SudoRules uses the same code for hidden singles for lines, from 2f: to 9f. The fact that it takes us a very large amount of unproductive scanning to do this, just doesn’t matter.

Computer code embodies both a sequence of operations, and the data supporting these operations. Tracking the numbers left for each cell makes the appearance of a naked single when adding a clue immediately known. The setup for that is to number scan candidates before beginning.

The detection of hidden singles can be made as simple, with unproductive scanning drastically reduced,  with the right data.  Just track, within each box and line, the number of cells left for each number.  As the grid is updated for a new clue, reduce these counts. Hidden singles in the containing units announce themselves. Track the location of candidates, or search for the single after it announces, it makes millisecond difference.

Read that paragraph again. It reveals that what we have been interpreting as number scanning, and eliminating cells in boxes and lines to reveal hidden singles, is actually simpler. It is a routine performed for every given clue, and then for every new clue as it is discovered. Update the count of the number in all three containing units, as each candidate is eliminated, making a list of units reaching 1. Then locate and promote the single in the list.  Making this happen by interpreting a set of rules is more computationally complex, but not enough to matter.

On the other hand, what does the code and supporting data for the detection of dublexes and cross hatches, squares and walls look like?  Not anything like that simple. SudoRules, although driven by sets of rules, another form of data, works like conventional computer code, and not like any human solver.

We learn something surprising about naked singles in the next post, where we will continue the Royle 17-3 trace into naked single territory. To watch it happen, we have to number scan the grid above, to recapture what candidates remain from the original number scan of the givens that SudoRules did, and made little use of, to this point. If you need to find out what this is like, that’s your homework assignment. At least its less burdensome that doing the number scan, then the ECP eliminations, yourself.

 

 

 

Posted in Basic Solving Procedures, Berthier, Expert Reviews | Tagged , , , , | 6 Comments