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

Difference between revisions of "Sudoku/Methods/Advanced/Simultaneous Bivalue Nishio"

From CFC
Jump to: navigation, search
[checked revision][checked revision]
(With coloring)
Line 35: Line 35:
 
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.
 
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. BSN takes a sudoku and makes two 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 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 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 it is marked, with each mark, one will scan for interactions. The most obvious interaction, and a good 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.
 
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 it is marked, with each mark, one will scan for interactions. The most obvious interaction, and a good 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.
Line 45: Line 45:
 
==Choosing a productive seed==
 
==Choosing a productive seed==
  
Before exhausting pre-BSN strategies, one may do a candidate/box study. There is [[Sudoku/Methods/Advanced/Simultaneous_Bivalue_Nishio/Reddit/2019_08_03|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"?
+
Before exhausting pre-SBN strategies, one may do a candidate/box study. There is [[Sudoku/Methods/Advanced/Simultaneous_Bivalue_Nishio/Reddit/2019_08_03|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.
 
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.

Revision as of 03:10, 11 October 2019

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

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 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 start to see the patterns.

Identifying a pair to begin

"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 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 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, if the other leg is sterile.

Working with the seed consequences

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 unconfusing choice of different seeds.

The starting cell 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 side creates a contradiction, one may eliminate all occurrences of candidates in that branch. 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 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 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 it is marked, with each mark, one will scan for interactions. The most obvious interaction, and a good 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.

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.

Choosing a productive seed

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"?

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?

With coloring

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

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