Flagged Revisions installed. Unapproved pages display a Red unchecked notice under the title. Trolls attack here by creating and archiving pages with offensive content. To verify an archived page, check the original URL. Questions about administration? Contact User talk:Abd. Limited privacy on this site, see CFC:Limited privacy

Sudoku/Methods/Advanced/Simultaneous Bivalue Nishio

From CFC
Jump to: navigation, search

Simultaneous Bivalue Nishio (SBN) has been partly described in many places, but often with crucial features missing and with some level of misunderstanding of when and how it is useful. It is related to Bowman's Bingo, for example, but no physical "bingo chips" are needed. It is Coloring, but it may be done in ink on paper without colors. It is Alternate Interference Chains, but descriptions of that do not much mention "simultaneous" and tend to look only at chain endpoints. It is Nice Loops, without necessarily seeing the loop initially. Or ever, for that matter, except that eventually one will come back to the starting cell. Noticing loops, however, is part of how to start SBN. Arnold Synder almost got there with his Impossible Force, but not quite.

Description[edit]

Standard condition: full candidate lists, in-cell, for all unresolved candidates. It is recommended that positional notation be used within the cell, with standard positions (matching many programs). This is, for each cell:

1 2 3
4 5 6
7 8 9

Dots, which are clearest in ink, may be used in those positions, which are then easily readable -- with a little practice --, and then a candidate is removed, not by erasure, but by writing X over it. (and if a candidate list with numbers is printed in ink, it may be modified in the same way, by X-ing out the candidate. Experience creates familiarity such that what is seen in a cell is what is missing, the spaces, and then the small numbers, or the dots. The Xs are readily ignored.

X's are generally not added unless one wishes to document an elimination without fully dotting the the region. Blotting out, inside the puzzle, is not recommended.

Preparing sudoku by following the "Snyder" practice of only marking candidates when there are two possible in a box (and not marking other regions, per se, until later) keeps the number of candidate marks down, and is highly recommended.

Sometimes people imagine that "full candidate list" means marking all non-eliminated candidates, which can create unnecessary confusion if done prematurely. And then, avoiding full candidate lists, these people spend hours staring at puzzles, missing the needle in the haystack, quite understandably. They are not feeding their eyes with organized data.

A bunch of blanks may seem simpler, but is simply concealing actual complexity. Actual complexity is simply reality, at that point. When we drop the "too complicated" emotional reaction, we may start to see the patterns.

Identifying a pair to begin[edit]

"Bivalue" indicates that SBN starts with an identified pair of mutually exclusive possibilities. Mostly we might start with a naked pair, because these are easiest to see, but any exclusive pair of locations in a region may also be used. How to identify a productive SBN pair, called a "seed," is not described by most authors.

Seeds have two "legs," that is, two strongly linked alternate possibilities. A productive seed will ideally have many visible proposed resolutions in both legs. Sometimes a seed might be chosen based on attractive proposed resolutions in one leg, ignoring the other. With difficult sudoku, unless the leg results in full puzzle resolution or contradiction, this can be unproductive, or "punk." Punk is really a description of the limitations of the solver, because every seed choice reduces the complexity of the puzzle, and most bring it within range of standard basic strategies, i.e., singles, pairs, doubles and triples. But advanced strategies may be used within a leg, if they are seen. If not:

The "harm" of choosing a "punk" seed is that one gains no mutual results, and it may be more efficient to recognize this quickly and move on to the next seed.

Working with the seed consequences[edit]

When one starts actually marking candidates, and in Hoduku or other program allowing candidate coloring, two colors will be used. A standard practice would be "green" and "red." These are arbitrary. They create chains of proposed resolutions that are formed through strong and weak links from the original choices, so the chains may be called Green and Red. Call the starting pair a "seed."

In ink on paper, candidates are marked distinctively. Dots may be circled. Basic rule of ink marking: confine the mark to the specific candidate space within positional notation, keep it tight, to keep it clearly identifiable and visible. Pencil may be used, and with extremely difficult sudoku, might even be necessary, because ink will not allow easily unconfusing choice of different seeds (but it usually is adequate to color off of only one seed).

The starting cell(s) must be identified, because SBN works with both strong and weak links. It is not, then, always bidirectional. This makes 3D Medusa a special case. With 3D Medusa, all links are strong and so all are bidirectional, and so if any leg creates a contradiction, one may eliminate all occurrences of candidates in that leg. With SBN, only the starting position may be eliminated. It does naturally follow that any candidates strongly linked from that starting position can be eliminated, so SBN automatically handles 3D Medusa, it is unnecessary to test for it.

It is not necessary to track or document strong v. weak links. It is not necessary to create arrows showing how the process proceeded, and these can create massive confusion, because fully documented process with SBN is quite complex, but seeing it all at once is unnecessary. Rather, one looks only at one step or interaction at a time.

One is free to use advanced strategies within the two chains, but, in practice it is generally unnecessary. Ordinarily, basic strategies suffice. SBN takes a sudoku and makes two subpuzzles out of it, one "valid," one not. It is useful to be able to work with either kind of sudoku, to be able to find contradictions, so labelling no-solution sudoku (or multiple solution sudoku) as "invalid," as if somehow Bad and unworthy, is disempowering.

One may proceed in any order. A common way of working could be to run a chain out as far as is obvious, then start with the opposite chain. As the second chain is marked, with each mark, one will watch for interactions. The most obvious interaction, and a great result, is that both chains lead to a cell with a single candidate that is a member of both chains. This cell is resolved, that choice being logically proven. The next most obvious interaction is that a cell ends up with two opposite-colored candidates. All other candidates may be eliminated from that cell.

Then any cell candidate that sees the same number colored differently in two cells anywhere in the puzzle may be eliminated.

Another simple interaction is that a naked pair in one chain may eliminate a candidate in another cell that also contains a candidate from the other chain. And more complex interactions might be seen, but, again, are not usually necessary.

These interactions keep simplifying the sudoku, and make completion of the chains (in full resolution or contradiction) proceed, even if each chain, alone, would lead to impasse.

Eventually, normally, one of the chains will link back to the seed, confirming the other choice, so the seed is resolved. If that is not enough to crack the puzzle, then it may be most efficient to choose another seed. With extremely difficult sudoku, several choices might be necessary, with each on either producing no results or perhaps elimination(s) and common resolution(s) with these still not being enough. Each time one chooses a new seed it is working on a simpler puzzle. In fact, a seed that failed initially might work after other seeds have done their work.

This is not a standard "strategy." It is an approach, a strategy in that sense. It is useful as a replacement for staring at puzzles for hours or days. If one of the "tough" or "diabolical" or "extreme" strategies has not been found, after a search according to one's skill level, it is still possible to crack the sudoku with this method. It bypasses most of the complex strategies by directly using the logic that is underneath most of them.

Choosing a productive seed[edit]

Before exhausting pre-SBN strategies, one may do a candidate/box study. There is an example from Reddit studied here. That study revealed cycles, and specifically cycles for two candidates involving only two boxes, with pairs that could light up both legs. Hence one of those was chosen. Was that the "correct" choice. Was this a "lucky guess"?

In fact, what that page shows is that *any pair* in that region was functional, and what was originally chosen was not the "best," there were others that more quickly found contradiction and the confirmation of "green" as valid and "red" as invalid. However, study to find the ideal choice, in advance, could have been wasted time. Not necessary.

Rather, simply avoid pairs where one leg is unproductive, if possible. If a sudoku is very difficult, it may be necessary to choose based on production from one leg only. These sudoku might require recursion to find a solution and prove uniqueness. Recursion is a step beyond SBN, it is really SMN, Simultaneous Multivalue Nishio. (which may still be bivalue in each recursion level, which keeps it simple and relatively easy to follow). However, Abd has never seen a sudoku that was absent bivalue choices. Has anyone? (This is a reminder that this is a public wiki, anonymous comments are allowed -- but will reveal IP. Ask for an account if one wants to be more anonymous, though we actually prefer real-name accounts. A valid email address, which will not be published, will be required.

Always mark the seed cell so that it can later be found. SBN, at least initially, often only proves that one of the seed cell choices is "invalid." It says little about the rest of the contradicting chain, because of weak links.

What is "productive"?[edit]

With ink on paper, Abd may be satisfied with as few as three proposed resolutions from a single leg, if there are more with the other, but he would continue looking for something better. If he can't find it in a reasonable time, he'll go ahead.

What does it look like?[edit]

With coloring[edit]

Hodoku image saves. Seed cells are colored light orange.

On the left:

Green resolves the puzzle, red contradiction has not yet been expanded for full proof of uniqueness.

On the right:

Green resolves, red leads to contradiction shown in light blue. Cells marked in pink are confirmed as the only marked candidate, plus the seed cell is confirmed as green. This is full uniqueness proof.

Using Hodoku, marking is fast and may be cleared with a single button push. So it's very practical to try different seed pairs. As well, savepoints are supported so that recursion is also possible if needed.

In ink on paper[edit]

The seed cell is marked on the outside. Full solution is shown by candidates triangled with a small check mark, because the first triangles led to a contradiction while the circles were still at an impasse. So the triangles were "recycled." (With a new seed cell, marked on the outside with a triangle with the number.) A better choice of seed pair may have been possible. (With a better choice, secondary study like this is rarely necessary.)

Other examples[edit]

See also[edit]