Sysudoku Advanced

This is a menu page for on advanced solving methods. “Advanced” is used here for logical methods exploiting relationships between remaining candidates. It doesn’t imply a level of difficulty. Some very advanced methods are very easy to do, with template tools. Advanced comes after Basic supplies the candidates, and requires knowledge of relevant candidate relationships, but not advanced logic skills.

To be humanly practical, a method opportunity must be recognized without extensive searching.  Often a timely construction leads to the recognition.  The Sysudoku approach on advanced methods is to replace extensive searching by human vision, enhanced by indicated logical constructions and visual tools. The Advanced pages identify the recognition clues, the construction,  the result, and why it is the result, with general schematics and real examples.

This page describes the advanced candidate relationships used in Sysudoku, and ends with an outline of the order of the solving methods using them.

The Weak Link

Sysudoku Basic uses and records strong links between candidates, the slinks. Aligned slinks are essential in sweeps, but all slinks were helpful in forming subsets. Sweeps and subsets restrict placements, leading to clues and more sweeps and subsets.

A slink is a logical entity. Logically, at least one of the slink partners must be true, that is to say, a placement in the solution. That means if one of them is proved false, the other is true. It also means that, if any candidate seeing both partners is false.

“Sees”? Yes, one candidate seeing another is a pervasive concept in Sudoku, and carries the name of the weak link. The logical meaning is, if the seeing candidate is true, the seen candidate is false. The analogy with vision makes sense. If A sees B, then B sees A. All candidates in a cell see each other. Candidates of the same number in a box or line see each other. But in advance Sudoku, candidates see each other, forming a weak link, in other ways..

Candidates that see each other are said to be weakly linked. We picture it as link between them. Since the logical action of seeing implies less than a strong link, it is known as a weak link, or for short, a wink. In Sysudoku Basic, winks are so pervasive that there was no need to talk about them and distinguish them from slinks.

But that changes in Sysudoku Advanced.  Many advanced methods are based on the more general idea of a set of candidates known to include the true one. I call them toxic sets, because  any candidate that sees all members of the set must be false. A slink is a simple toxic set of two candidates, because at least one of the slink partners must be true. Other forms of toxic sets are created by combinations of slinks and winks. This is the essence of many advanced methods.

On Sysudoku grids, slinks are solid curves, and winks are dashed ones. A candidate seeing both partners of a slink could look like this. The three X’s signify  three candidates of the same number. The diamond is the Sysudoku marker for a false value and a removal, or elimination, from the grid.

Toxic Sets

Many advanced methods are based on the more general idea of a set of candidates known to include the true one. In such a case, any candidate that sees all members of the set must be false. The Sysudoku name for it is the toxic set. Slink partners are a toxic set. Weak links are essential in creating many kinds of toxic sets, and in seeing all of the members of a toxic set.

Alternating Inference Chains

Another essential role of winks is to make, Alternating Inference Chains or AIC. Here, in Alary review puzzle Very Extreme 104, 6r3c2 and 6r1c7 are at opposite ends of a 6-chain of alternating slinks and winks. When the links at both ends are slinks, then the end candidates are slink partners. The chain is a slink. The end candidates are a toxic set. Any candidate seeing both must be false. That means 6r1c3 and 6r3c7 can be removed.

It is easy to prove that to your skeptical friends. Start by going down the chain, if 6r3c2 is false, 6r6c2 is true, so 6r5c3 is false so . . . and arrive at . . . so 6r1c7 is true. However, if 6r1c7 is false, then . . . going back to arrive at . . . then 6r3c2 is true. One or both end candidates are true.

So a candidate can be removed for what it sees.  Could it see a candidate of a toxic set by means of an AIC? Is there an AIC wink? Sure.  Just knock off the end slinks in the 6-chain above. Then 6r6c2 and 6r8c7 see each other, via the 6-chain.

The chain can be considered to be two slinks, connected by an AIC wink.

The AIC in the above example is an X-chain by type, involving only a single number X. There are many types of AIC, and these types can be mixed along the chain.

A somewhat overlooked fact outside of Sysudoku is that AIC winks can be used for any wink in a the construction of a method. This makes for what I call irregular versions of standard advanced methods. Irregular methods widen the possibilities for removing false candidates, but that very fact dictates that advanced solving is done more efficiently and enjoyably by constructing formations like wings, chains, loops and fish, rather than searching for them. That’s a theme of Sysudoku Advanced.

 Alternating Inference Loops

Now mentally substitute a slink chain for the slink in the previous diagram. It makes a loop that is almost alternating, except for the winks representing the victim seeing the end candidates, the toxic set.  In honor of my Sudoku mentor Andrew Stuart, I call that an almost  nice loop, an ANL. It’s loop “a” in this comparison of three X-loops. The Alary 6-chain above forms two ANL, one for each victim.

Loop b shows what happens when the ends of an AIC are the same candidate. That candidate is true. If you assume it is false and follow the chain around, you find if it’s false, it’s true. Yeah. I sometimes refer to it as a confirming ANL. To confirm is to promote the candidate to clue.

An AIC loop of an even number of candidates, like loop c above, is a nice loop.  We don’t pet it on the head and rub its ears.  We like it because every other candidate in a nice loop is true. Pick the candidate at 6 o’clock. If it is false, every other candidate counterclockwise is true, and the remaining candidates are all false.  If it is true, go clockwise and every other candidate is true and remaining candidates are false. You don’t know which direction is right, but you do know something very useful: Every pair of adjacent candidates along the loop is a toxic set.

In the loop diagrams, the loop chain is depicted as an X-chain, in which all nodes are a single candidate of the same number X.  But ANL and nice loops work the same for all types of AIC.

Fishy Relationships Among Candidates

Perhaps the most widely known methods, by name at least, are regular fish, the X-wing, and the Swordfish. Regular fish extend further, and then there are finned and kraken and sashimi variations. Boxes can be taken on the fishing trip, the mixed Mutant or Franken fish.

Fish are constraints on placements that insure that, in the competition among rows, and among columns, each line gets a true candidate of each number.

Here in a review, Ardson Very Hard v.2 #78, a swordfish on rows 1, 2 and 3 reserves columns 2, 4 and 8 for the three true 6’s they must have. Why do they have to have ‘em? Right! And that means 6r4c2 must go.

The bonus 4-chain ANL just came with the grid.

Many methods juggle multiple numbers, but fish are single number constraints. In Sysudoku, that means fish are explored on X-panels, grids showing only the candidates of a single number, along with the X-chains mentioned above.

Competition for placements along lines is mathematically the same as competition for free cells among missing numbers. The Suset scratchpad algorithm applied to subsets in Sysudoku Basic also applies to regular, sashimi and kraken fish, and to finned and mutant fish.

Bv and ALS

X-chains and fish illustrated above seem to involve only candidates of a single number. Sudoku methods go beyond this, by means of bv and AIC. A bi-value cell creates an internal slink between candidates of two different numbers. XY-chains, a form of AIC, interchanges numbers all along its path.

Bi-value cells, the bv,  were introduced in Sysudoku Basic as the only cells pencil marked in the bypass. In line marking, and later as they are formed, bv are marked on our grids by green borders. In review tables, we measure the degree of difficulty at the beginning of advanced solving by the number of bv on the grid at that point.

Bv partner candidates are slink partners. If one is false, the other is true. On Sysudoku grids, the internal bv slink is implicit until the bv is included in a chain, then it is drawn in to show how the bv completes the chain curve.

The clue has a multi-cell counterpart, the locked set. A clue reserves one cell within a unit, a box or a line, for its number. The  unit itself, and any subset, is a locked set, meaning it reserves n cells for n numbers, restricting placements for other numbers. Finding a subset is a leap forward in solving, though, we don’t know which candidate of a number within the locked set is the true candidate. By definition, a clue is a locked set.

A similar counterpart exists for the bv. It is the almost locked set, or ALS, a set of n cells within a unit containing candidates of exactly n+1 numbers. When a placement of one of those n+1 numbers is found outside of the ALS, the ALS  gives up candidates of that number and becomes a locked set. The bv is an ALS with n = 1.

The ALS is a fundamental element of Sudoku logic. Toxic sets and chains are constructed, based on the fact that an ALS can give up only one of its numbers. This property even allows an ALS to function as a node on a chain. As the locked sets of a box or line are enumerated with Susets, all of ALS of the unit are also enumerated. All of these mysteries are explained in these pages.

The Coloring Network

The logical meaning of the slink and the wink are clearly fundamental in advanced methods. There is an even more powerful link between candidates, associated with a human solving practice called coloring. We’ll call it the coloring link. When two candidates are coloring partners, then if the first one is false, the second one is true, but also if the first is true, the second is false.

That’s stronger than the strong link. In fact, it is the strong link and the weak link combined. The slink pair has at least one true candidate. The coloring pair has exactly one true candidate. This means that along a chain of color linked candidates, true and false candidates alternate, because each of the overlapping color linked pairs along any chain has only one true candidate.

The direct benefit in coloring is that, in a network of coloring linked candidates, called a cluster, if you color alternating candidates in two alternating colors, candidates of one color are true and candidates of the other color are false. Therefore, if you can show any candidate of one color is false, all candidates of that color are false. It’s called a wrap.  If the coloring has two candidates of the same color and number in the same line or box, they see each other, and all candidates of the other color are true. And toxic sets abound. Any candidate seeing candidates of both colors is false. That’s a trap.

Slinks based on exactly two candidate of a number in a unit are color linked. So are the slinks inside bv cells. Sysudoku coloring is generally known as Medusa coloring, because the bv create coloring partners of different numbers (values), so clusters have multiple numbers.

Here, a blue/green cluster has grown larger than the original one. The diamond marks a coloring trap. 2r7c3 sees red and orange 2’s. Also, two red candidates colored into the same cell identifies red as false. Orange then confirms green. The example is from Frank Longo’s Absolute Nastiest, #662.

Pattern Analysis

Patterns form a relationship among candidates, based on the box and line structure of Sudoku. A pattern is a selection of candidates of the same number from the remaining candidates, which provides a placement to each box and line missing a placement of that number. Of course, some of the selected candidates supply the number to more than one unit. As competition between numbers for placements continues, possible patterns decrease, until there is only of true pattern for each number.  Interest in patterns grew out of their use in a computer solver algorithm called the Pattern Overlay Method, or POM.

Andrew Stuart, in The Logic of Sudoku, pointed out two modes of analysis of patterns which become humanly practical when limited to a competition for placements between a few numbers that have few patterns. Sysudoku explored both, pattern lettering and freeform analysis,  as tactics, naming this approach Limited Pattern Overlay, or LPO, to distinguish it from the already well known POM. Like many computer solving methods, POM generally requires searching through hundreds to millions of combinations to find the effective one.

Andrew Stuart, in his The Logic of Sudoku, pointed out two modes of analysis of patterns which become humanly practical when limited to a competition for placements between a few numbers that have few patterns. Sysudoku explored both, pattern lettering and freeform analysis,  as tactics, naming this approach Limited Pattern Overlay, or LPO, to distinguish it from the already well known POM.

As a stand-alone method, the blog adopted the freeform method, primarily because of its visual appeal and ease of execution on the X-panel templates. In this method, each pattern is represented as a broken line path from one side of the grid to the opposite side. In the lettering method, each possible pattern is represented by a distinct letter, and the 81 grid cells are filled with letter/number combinations, identifying the patterns the cell belongs to. Both methods isolate orphans, candidates belonging to no pattern, cells belonging to only one pattern, and conflicts between patterns. When a pattern of one number conflicts with possible patterns of all other numbers, it is discarded.

Here is a freeform analysis example that illustrates the nature of patterns. From the review of Xaq Pitkow’s Sudoku Vol. 3, GM 95, the 6-panel reveals a heavy load of 6-candidates, but also there are few ways to draw freeforms from East to West. As you add segments to the freeform, you have to touch every column, and every box containing a 6. At the end, every line has to be touched once. It’s a game within a Sudoku solving. Want to play? Copy the 6-panel and try it before examining the results here.

Choosing blue and green for the starting candidates, draw blue freeforms from 6r5c9 first, using different forms of dashed line to distinguish them. All three run out of options before reaching column 1. That means there are no blue patterns, and the two candidates that are the only way to start a blue pattern are orphans.

Drawing all the green patterns is tough, but the 6-pattern is green, and candidates in the same line as candidates in all green patterns are orphans. They are marked with an x in the green freeforms panel.

Sysudoku exploits a relationship of patterns to coloring for the formulation of trials, which is the defining technique of Sysudoku Extreme. The true pattern of every number has a single color, and patterns of a number have conflicts over grid colorings. Thus coloring wraps eliminate patterns, and pattern eliminations can establish colorings.

The Advanced Order of Battle

A logical “on the average” ordering of advanced methods is followed in reviewing puzzle collections in Sysudoku. It is recommended, on the basis of least effort, assuming the use of the visual tools available on the MS  ©PowerPoint and ©Word templates free by request on the Tools page. The paging menu’s follow this order of battle. Exceptions are warranted occasionally, and of course, every new clue, subset, and elimination shifts us back into basic mode for follow up.

Unique rectangle methods are the first group, based on the fact that they are best spotted by means of already highlighted naked pairs on the grid.

The next major method group, the bv scan, is centered around the bv, and its occasional stand-in, the ALS, as fundamental entities. The line marked grid is scanned once over for Sue de Coq, APE, and BARN, all having distinctive configurations of bv/ALS  and hinge cells. The bv scan also begins a lookout for pairs of ALS with restricted commons, a feature required for toxic sets.

Then we construct a map of the bv, and from that, an XYZ form. On the XYZ form  we place possible hinges for XYZ-wings, WXYZ-wings, and Death Blossoms. On the bv map, we then draw and XY-chain railway, and find XY ANL.

Next we place all candidates of the same number on a grid, the X-panel. Our free ©Word template has  9 panels and 3 spares. For each mumber, we populate an X-panel, and scan it immediately for X-chains and fish. Grouped X-chains are included.  Regular, finned, and kraken fish are marked on the X-panels. Limited forms of pattern analysis for promising panels.

Coloring is next at its latest, but is often applied much earlier when the bv field warrants, because the Sysudoku coloring technique on the ©PowerPoint template does not interfere with other grid methods.

Next we add AIC hinges to the grid. These are in-cell winks between slinks entering the cell, which are building blocks for AIC chains. Mixing chains of every type, with ALS nodes, we do anything to keep the chain going.

The Suset algorithm may be applied to mutant fish and multiple finned fish here.

Last comes pattern analysis based on the logic of pattern conflicts.

Beyond Advanced

If there are no promising advanced methods, we can turn to an appropriate trial as a last resort. We reserve the label “extreme” for puzzles that can only be solved by trials. See the Sysudoku Trials page for an overview and links for trials.

One other category to be aware of, the monsters. In Sysudoku, we reserve the term monster for those puzzles whose givens are so ineffective, and candidates so numerous, that basic and advanced methods seem impossible.  It takes an extraordinary effort to solve them, but in several cases, Sysudoku has documented solutions.

 

 

Advertisements