The New Sudoku Players' Forum

[Graeme]

I've posted this on another forum without a clear answer. I'm trying to find out if the technique has been previously documented, and already has a name.

I call it Error Chains, and the logic is:

If placement of a candidate value removes all candidates from another cell, that candidate value can be removed.

Here are two examples of my Error Chain technique:



If the candidate value in blue is set, then all candidates are removed from the cell shaded blue. So we can remove the {6} and {4} candidates in the cells shaded yellow.

The first example (with pair candidates only) works like forcing chains in reverse, but this is not the case with more cell candidates, as in the second example.

[Carcul]

Hi Graeme.

What you call "Error Chains" is already known, at least to me, as double implication chains (your first example above), triple implication chains (your second example), tetra implication chains, forcing nets, and certain types of single implication chains.

Regards, Carcul

[vidarino]

Unless I'm mistaken, the first example is the good, old (and fairly well known) XY-Wing technique.

It's more commonly approached from the other end, though;
- if R4C2 = 2, then R3C2 = 6, then R1C1 <> 6
- if R4C2 = 4, then R4C1 = 6, then R1C1 <> 6

See here for a longer description.

More generally, both are, as Carcul says, known as implication forcing chains.

[Graeme]

Thanks for the quick replies.

What I've read about forcing chains has not much in common with Error Chains.

Forcing chains use candidates in a test cell and look for a forced result in another cell (a set value, or removal of one or more candidates). If that condition is true, then that change is made in the forced cell. In addition, every candidate must be checked in the test cell before that condition can be tested.

Error Chains use a single candidate test to look for removal of all candidates in aonther cell. If the condition is met, that candidate is removed in the test cell, not the affected cell like Forcing Chains.

I haven't see it listed in the usual technique lists, and I find it very effective in my own solver. In some ways I agree it works like forcing chains in reverse, but the second example above shows that no useful information is gathered by setting {6} in the blue cell.

[Jeff]

I've posted this on another forum without a clear answer. I'm trying to find out if the technique has been previously documented, and already has a name.

Hi Graeme, This technique was first introduced to this forum by DanO here and is referred to as "Empty Cell Contradiction".

It is basically a reverse process of a poly-implication forcing chain. The number of candidates in the cell to be emptied equals to the number of implication streams in a forcing chain. Thus, your first example can be expressed as a double implication chain with 2 implication streams and your second example can be expressed as a triple implication chain with 3 implication streams.

[tarek]

It also sounds very close to a second level of the Nishio technique

Tarek

[Myth Jellies]

It is just a trial and error counterpart to an xy-wing up top, and an ALS xz-rule on bottom. You can either find these reductions using the patterns mentioned, or you can guess a candidate and see if it causes a crash by exhausting all of the options in another cell. The pattern methods require no assumptions of whether a particular candidate is true. The guess & check method obviously does.

[tso]

They have nothing to do with Nishio. Nishio considers a single candidate.

Your two examples are forcing chains. They fact that you've described them from another angle doesn't change the logical connections between the cells. It doesn't matter if the blind man grabs the tail or the tusk, -- it is still an elephant.


Example one:


r4c2=2 -> r3c2=6 -> r1c1<>6
r4c2=4 -> r4c1=6 -> r1c1<>6
Therefore, r1c1<>6

This is an xy-wing, the smallest possible forcing chain.


Example two:

r8c6=3 -> r5c6=4 -> r5c5<>4
r8c6=7 -> r7c5=4 -> r5c5<>4
r8c6=6 -> r9c5<>6 -> r79c5=[47][47](a naked pair) -> r5c5<>4
Therefore, r5c5<>4

This is a forcing chain in which one of the links is the 'quantum cell' r79c5.

In both cases, all possibilities in one cell lead to a singular result in another. This is the way of the forcing chain.

[Jeff]

I've posted this on another forum without a clear answer. I'm trying to find out if the technique has been previously documented, and already has a name.

Hi Graeme, I just remember that your deductions are also generally referred to as "Single Implication Networks", which is defined as:

A network that has one implication stream that starts with a candidate selected in one node and propagates with or without multiple inferences until a contradiction is revealed (eg. empty cell, one digit appears 2 times in a unit or no place for a digit in a unit), thus concluding the candidate selected at the start is invalid.

You can find this term described here.

[Graeme]

Thanks Jeff - first person to answer my question! And I really like your proposal to standardise terminology - nice work indeed. Maybe something like "Contradiction Net" is a better term for error chains?

I really think the process involved for this is very different than forcing chains, for both human solvers and programmed algorithms, but no doubt some will disagree.

Anyway, see my next reply to tso.

Thanks again!

[Graeme]

Hi again, tso

I understand your point, but allow me to recap for the benefit of other readers. This is my view of why I see the 2 techniques as almost opposite things:

tso wrote: They have nothing to do with Nishio. Nishio considers a single candidate.

Agree it's not much like Nishio, but it does consider a single candidate like Nishio, and it removes that candidate from the test cell like Nishio, if the technique condition is met. Forcing Chains do neither.

I do see your view that you can work these backwards, in conjunction with other techniques to make them work like a forcing chain.

In the simple examples above, one required just naked singles to allow it to work in reverse, while the other required naked pairs as well. I expect real-world examples require several other techniques as well.

My opinion is that most human solvers only look at naked singles (and removing candidates affected by setting those values) when testing the implications of techniques like Nishio and Forcing Chains.

Certainly, that's how I've programmed my solver, in my quest to make it human-like to report the solve techniques required. Consequently, my Error Chains find additional puzzle simplifications after Forcing Chains have finsihed.

I would conceed that highly talented human solvers might use additional techniques in implication testing, but I really wonder how far they take it. Forcing Chains require you to remember, or note down implications of every test candidate, then compare every result before you can make any decision about what condidtions are met.

Error Chains are certainly much easier than that. I like your analogy with the elephant. IMHO, it's sometimes easier to grab it by the tail and call it a tail.

[tso]

I understand your point, but allow me to recap for the benefit of other readers. This is my view of why I see the 2 techniques as almost

opposite things:

The tail: (aka forcing chains)

Code: Select all

  .    .    .  |  .    .    .  |  .    .    .
  .    12   .  |  .    .    .  |  .    13   . 
  .    .    .  |  .    .    .  |  .    .    . 
  -------------+---------------+-------------
  .    .    .  |  .    .    .  |  .    .    . 
  .    .    .  |  .    .    .  |  .    .    . 
  .    .    .  |  .    .    .  |  .    .    . 
  -------------+---------------+-------------
  .    .    .  |  .    .    .  |  .    .    . 
  .    23   .  |  .    .    .  |  .   345   . 
  .    .    .  |  .    .    .  |  .    .    .

r2c2=1 -> r2c8=3 -> r8c8<>3
r2c2=2 -> r8c2=3 -> r8c8<>3
Therefore, r8c8<>3


The tusk: (aka proof by contradiction or error chains)

Code: Select all

  .    .    .  |  .    .    .  |  .    .    .
  .    12   .  |  .    .    .  |  .    13   . 
  .    .    .  |  .    .    .  |  .    .    . 
  -------------+---------------+-------------
  .    .    .  |  .    .    .  |  .    .    . 
  .    .    .  |  .    .    .  |  .    .    . 
  .    .    .  |  .    .    .  |  .    .    . 
  -------------+---------------+-------------
  .    .    .  |  .    .    .  |  .    .    . 
  .    23   .  |  .    .    .  |  .   345   . 
  .    .    .  |  .    .    .  |  .    .    .

r8c8=3 -> r2c8=1 -> r2c2=2
r8c8=3 -> r8c2=2 -> r2c2=1
This is a contradiction, therefore r8c8<>3

OR

r8c8=3 -> r2c8=1 -> r2c2<>1
r8c8=3 -> r8c2=2 -> r2c2<>2
Nothing left to go in r2c2, therefore r8c8<>3


The elephant: (labeled edges and a nice loop)

Code: Select all

  .    .    .  |  .    .    .  |  .    .    .
  .    12-------------[1]--------------13   . 
  .    |    .  |  .    .    .  |  .    |    . 
  -----|-------+---------------+-------|-----
  .    |    .  |  .    .    .  |  .    |    . 
  .   [2]   .  |  .    .    .  |  .   [3]   . 
  .    |    .  |  .    .    .  |  .    |    . 
  -----|-------+---------------+-------|-----
  .    |    .  |  .    .    .  |  .    |    . 
  .    23-------------[3]-------------345   . 
  .    .    .  |  .    .    .  |  .    .    .

[r8c8]-3-[r8c2]-2-[r2c2]-1-[r2c8]-3-[r8c8]

The elephant is the underlying stucture that allows the one and only deduction. We can describe it as a forcing chain starting from r2c2, r2c8 or r8c8, OR as a proof by contradiction starting from r8c8=3.

If one thinks of these as a series of chronologically ordered implications, then there is a subjective difference between the various descriptions. But the temporal nature is an illusion.

If you more accurately think of the structure *as a whole*, existing at once -- like a real-world chain -- then forwards versus backwards is artificial.

As a *method* to *find* these deductions, proof by contradiction is perfectly valid but not new to sudoku. Some solver's (I'm not among them.) don't like it because they feel that it is too much like trial and error -- a number is placed in a cell (Why place the 3 not the 4?), tested to see if it works (What if it *does* work?) and backtrack if it doesn't. As a human solver, if I can see it, it counts, it is fair.

I think the problem arises when one tries to make software "solve by human methods". I can mentally place a number then follow along only so deeply, making mental eliminations equivalent to singles, maybe pairs, maybe intersections, etc. The limit is *my* personal limit. The software has no such personal limit and must be artificially capped -- otherwise it will be able to do an "error chain" elimination from the opening grid from nearly every cell. It's one thing to restrict it to finding naked pairs, swordfish, simple xy-type forcing chains of any length -- but unrestricted error chains (or unrestricted complex forcing chains as well) would be equivalent to brute force or recursive solving -- which of course, some humans *do* use to solve!


The discussion of human solving techniques always seems to assume that humans have only three levels of expertise -- novice, beginner and the rest. There seems to be no room for various levels of expert. Everyone seems to accept that Judit Polgar or Garry Kasparov can see many moves further in advance than a typical club player -- who would in fact trounce me though I've played for years. (In fact, the tendency in popular fiction is to imbue top chess players with ridiculous depth of search ability.) No one would or ever has claimed that what top players are actually doing is trial and error or guessing -- they are caclulating. But we don't seem to allow that one sudoku solver might be able to see past several virtual eliminations or recognize large burried patterns in order to make a deduction that appear to be magic to another.

tso wrote: They have nothing to do with Nishio. Nishio considers a single candidate.

Agree it's not much like Nishio, but it does consider a single candidate like Nishio, and it removes that candidate from the test cell like Nishio, if the technique condition is met. Forcing Chains do neither. ... My opinion is that most human solvers only look at naked singles (and removing candidates affected by setting those values) when testing the implications of techniques like Nishio and Forcing Chains.

This is quite untrue for Nishio. Nishio considers the placement of ALL of one candidate, ignoring ALL of the other 72 digits. Nishio uses locked candidates as often as singles. These tactics are simply easy or obvious because Nishio is working on a sub-puzzle that has only 9 digits to place -- small enough to see all the way to the end of the game (like Judit Polgar). With forcing chains -- your milage may vary. More than once I only realized that I've included locked candidates or naked pairs as part of a forcing chain when I tried to write it down for posting.

In the simple examples above, one required just naked singles to allow it to work in reverse, while the other required naked pairs as well. ... Forcing Chains require you to remember, or note down implications of every test candidate, then compare every result before you can make any decision about what condidtions are met.

The level of complexity of the deduction remains unchanged regardless of which way the deductions are read. You're overlooking all the deductions you actually make because they are "obvious" -- what's obvious to you may not be to me. Error chains requires me to either note down, remember or note down exactly as much information -- unless I go ahead and erase candidates as I go along -- which would *strongly* risk getting into a postion from which I would be unable to backtrack -- how will I remember which candidates to put back in?

I would conceed that highly talented human solvers might use additional techniques in implication testing, but I really wonder how far they take it. Forcing Chains require you to remember, or note down implications of every test candidate, then compare every result before you can make any decision about what condidtions are met.

Error Chains are certainly much easier than that. I like your analogy with the elephant. IMHO, it's sometimes easier to grab it by the tail and call it a tail.

I disagree -- error chains is just as likely in a given situation to require much information to be recorded one way or another. It's purely subjective to state that error chains are easier. To demonstrate, here's your first example:

Code: Select all

  .    .    56 |  35   .    .  |  .    .    . 
 678   .    69 |  .   2369  236|  .    .    . 
  .    .    .  |  .    .    .  |  .    .    . 

Error Chains:


A) If r2c1=6 -> (r1c3=5 AND r2c3=9 AND r2c5<>6 AND r2c6<>6)
B) If r1c3=5 (from A) -> r1c4=3 -> (r2c5<>3 AND r2c6<>3)
C) If r2c3=9 (from A) -> r2c5<>9
D) If r2c5<>6 (from A) AND r2c5<>3 (from B) AND r2c5<>9 (from C) -> r2c5=2 -> r2c6<>2.
E) But if r2c6<>6 (from A) AND r2c6<>3 (from B) AND r2c6<>2 (from C), the puzzle cannot be solved.
Therefore, r2c1<>6

Or by (much simpler) complex forcing chains:

r1c4=5 -> r1c3=6 -> r2c1<>6
r1c4=3 -> r2c5<>3 -> r2c356=[269] (naked triple) -> r2c6<>6
Therefore, r2c1<>6

I suppose I could just write in a 6 in r2c1 and solve from there in pencil, but I can *always* do that!

[Graeme]

whew, tso, it might be easier to just agree to disagree, but I'm game if you are ;-) But seriously, many thanks for the robust debate.

Let me start by saying I'm merely showing a technique I use as a human solver and programmer, that's not listed in common lists of popular solving techniques. Jeff pointed me to earlier references on this technique. It's just a technique that delivers results.

I think our difference of opinion is that I see Error Chains as a technique that humans can apply in the opposite way to Forcing Chains, easier in the *right* circumstances, and unhelpful in other circumstances. I think your view is that you see them as a class of Forcing Chain, because mathematically, they work like Forcing Chains in reverse. Please correct me if this is not your position (I know you will ;-)

tso wrote: (pair example, followed by ...) If you more accurately think of the structure *as a whole*, existing at once -- like a real-world chain -- then forwards versus backwards is artificial.

Already said I agree with you on this for the the pair example in my previous post:

my quote: ... you can work these backwards, ... to make them work like a forcing chain. In the simple examples above, one required just naked singles to allow it to work in reverse

tso wrote:I think the problem arises when one tries to make software "solve by human methods". I can mentally place a number then follow along only so deeply, making mental eliminations equivalent to singles, maybe pairs, maybe intersections, etc. The limit is *my* personal limit.

Yes, I agree entirely. I described my efforts to do this as a quest, and I've had to make some design decisions, such as "implication testing uses naked singles only", which is central to our different views on Error Chains.

tso wrote: The discussion of human solving techniques always seems to assume that humans have only three levels of expertise -- novice, beginner and the rest. There seems to be no room for various levels of expert.

That sounds like an assupmtion in itself, but I accept that as your experience.

... the tendency in popular fiction is to imbue top chess players with ridiculous depth of search ability

What I've read on this states very much the opposite, and I think that is your point.

I wrote: Agree (error chains are) not much like Nishio, but it does consider a single candidate like Nishio, and it removes that candidate from the test cell like Nishio, if the technique condition is met. Forcing Chains do neither. ... My opinion is that most human solvers only look at naked singles (and removing candidates affected by setting those values) when testing the implications of techniques like Nishio and Forcing Chains.
---------------------------------------
tso wrote: This is quite untrue for Nishio. Nishio considers the placement of ALL of one candidate, ignoring ALL of the other 72 digits. Nishio uses locked candidates as often as singles. These tactics are simply easy or obvious because Nishio is working on a sub-puzzle that has only 9 digits to place -- small enough to see all the way to the end of the game (like Judit Polgar). With forcing chains -- your milage may vary. More than once I only realized that I've included locked candidates or naked pairs as part of a forcing chain when I tried to write it down for posting

I have no problem with your factual description on Nishio solving. And I agree that for most solvers, it's likely to be the simplest of the guessing techniques, because of the focus on a single digit (not for me for some reason; I keep getting distracted with all those other naked singles ;-).

But my point is that Error Chains and Nishio are similar in 2 ways:
(1) they both place a single candidate in the test cell and test the implications of that placement
(2) if the solve condition is met, both Error Chains and Nishio remove the test candidate from the test cell

tso wrote: The level of complexity of the deduction remains unchanged regardless of which way the deductions are read. You're overlooking all the deductions you actually make because they are "obvious" -- what's obvious to you may not be to me.

The deduction I make as a human solver and programmer are equal for implication testing of all guess techniques. I use naked singles only. Plenty of people smarter than me may use additional techniques for implication testing, and see fit to include them in their solve algorithms.

tso wrote: Error chains requires me to either note down, remember or note down exactly as much information -- unless I go ahead and erase candidates as I go along -- which would *strongly* risk getting into a postion from which I would be unable to backtrack -- how will I remember which candidates to put back in?

Note-taking and backtracking are the perils of all guess techniques. I don't much like them as a human solver. But Error Chains are no better or worse than other guess techniques.

I wrote: Forcing Chains require you to remember, or note down implications of every test candidate, then compare every result before you can make any decision about what condidtions are met. Error Chains are certainly much easier than that.
----------------------------
tso wrote: I disagree -- error chains is just as likely in a given situation to require much information to be recorded one way or another. It's purely subjective to state that error chains are easier. To demonstrate, here's your first example ...

My point followed my discussion of the second example, not the first, but I probably wasn't clear on that.

And it's not subjective, it's fact. Error Chains require implication testing only one candidate; Forcing Chains require implication testing of every candidate.

The second example in my original post shows a situation where the implication testing needs to include naked pairs in addition to naked singles to get it to work backwards so you can label it as a Forcing Chain.

[pjaj]

As a newbie, I don't know if this is quite relevant to this particular discussion, but in a recent game I reached the following position with one number

Code: Select all

 ...|...|...
 ...|...|...
 ...|x.x|...
 ---+---+---
 x..|x.x|...
 ..x|.xx|...
 ...|...|...
 ---+---+---
 ..x|x.x|...
 x..|xx.|...
 ...|...|...


Now I admit that I may have overlooked something much simpler, but consider r5c3
r5c3=x > r4c1<>x > r8c1=x
With both r5c3 & r8c1 = x > {r4c1, r5c5, r5c6, r7c3, r8c4, r8c5} <> x
Which leaves 6 cells in c4 & c6 for the 3 remaining xs in r3, r4 & r7.
Clearly impossible, therefore r5c3 (& r8c1) <> x
What have I found here? It doesn't look like colouring or some fishy beast.

[aeb]

As a newbie, I don't know if this is quite relevant to this particular discussion, but in a recent game I reached the following position with one number

Code: Select all

 ...|...|...
 ...|...|...
 ...|x.x|...
 ---+---+---
 x..|x.x|...
 ..x|.xx|...
 ...|...|...
 ---+---+---
 ..x|x.x|...
 x..|xx.|...
 ...|...|...


Now I admit that I may have overlooked something much simpler, but consider r5c3
r5c3=x > r4c1<>x > r8c1=x
With both r5c3 & r8c1 = x > {r4c1, r5c5, r5c6, r7c3, r8c4, r8c5} <> x
Which leaves 6 cells in c4 & c6 for the 3 remaining xs in r3, r4 & r7.
Clearly impossible, therefore r5c3 (& r8c1) <> x
What have I found here? It doesn't look like colouring or some fishy beast.

The usual definition of Nishio is: assume one placement of a digit d and see whether all other digits d can still be placed. If not, then the first choice is ruled out. That is precisely what you do. On the other hand, there is a 5-cycle with edges =-=-=, I suppose that one might term it Turbot Fish,
that would provide a name for this particular instance of Nishio.