The New Sudoku Players' Forum

[vidarino]

If any of the four cells contains a given, a clue, the set is an "unavoidable set". If none of the four cells contains a given, it follows that the "unavoidable set" is avoidable. IOW, if none of the four cells contains a given, the set is an "avoidable set".

Unavoidable Sets are usually identified in the solution-grid, typically used in the quest for a puzzle with a minimal number of clues.

Here's a randomly generated solution:

Code: Select all

+-------+-------+-------+
|*5*3*8 | 4 7 2 | 1 6 9 |
| 1 7 9 | 3 8 6 | 5 4 2 |
| 6 2 4 | 9 5 1 | 3 7 8 |
+-------+-------+-------+
|*3*5*7 | 2 4 8 | 6 9 1 |
| 8 4 6 | 1 9 5 | 2 3 7 |
| 9 1 2 | 6 3 7 | 8 5 4 |
+-------+-------+-------+
| 2 9 5 | 7 1 3 | 4 8 6 |
| 7 8 1 | 5 6 4 | 9 2 3 |
| 4 6 3 | 8 2 9 | 7 1 5 |
+-------+-------+-------+

Note the 35-pair in R14C12.

A pattern such as that one is an Unavoidable Set, which literally means that when making a puzzle out of the grid, e.g. by erasing numbers one at a time, you can't avoid leaving an initial clue in at least one of these cells. If you didn't, the puzzle wouldn't have a unique solution.

And this is precisely what makes AUS-eliminations work. If an AUS has an unsolved corner, and none of the solved corners were initial clues, you can remove the "deadly" candidate from the remaining corner.

Vidar

(Edit: Added the sample solution.)

[Neunmalneun]

Code: Select all

 
 
 *-----------------------------------------------------------*
 | 3     6     14    | 14    7     29    | 29    8     5     |
 | 7     29    8     | 3     24    5     | 2469  46    1     |
 | 49    129   5     | 8     6     129   | 2479  3     479   |
 |-------------------+-------------------+-------------------|
 | 28    5     9     | 147   3     246   | 18    467   478   |
 | 28    4     67    | 5     129   126   | 3     167   789   |
 | 1     3     67    | 47    49    8     | 4679  5     2     |
 |-------------------+-------------------+-------------------|
 | 6     7     14    | 9     5     3     | 18    2     48    |
 | 49    19    2     | 6     8     47    | 5     147   3     |
 | 5     8     3     | 2     14    147   | 47    9     6     |
 *-----------------------------------------------------------*
The next step with the same technique would be found in the AUR R1C67 / R3C67. If R3C7 was 29 R3C6 had to be 1 causing a contradiction in row 3. So R3C7 = 47 leading to a naked pair of 47 in C7


[vidarino]

The next step with the same technique would be found in the AUR R1C67 / R3C67. If R3C7 was 29 R3C6 had to be 1 causing a contradiction in row 3.

Hmm, I can't say I see any immediate contradictions in row 3 alone;

Code: Select all

Row3:
 | 49    129   5     | 8     6     129   | 2479  3     479   |

Now, setting R3C7=29 and R3C6=1:
 | 49     29   5     | 8     6       1   | 29    3     479   |

We get a naked pair of 29s, leaving;
 |  4     29   5     | 8     6       1   | 29    3       7   |

Vidar

[ronk]

A pattern such as that one is an Unavoidable Set, which literally means that when making a puzzle out of the grid, e.g. by erasing numbers one at a time, you can't avoid leaving an initial clue in at least one of these cells. If you didn't, the puzzle wouldn't have a unique solution.

The "un" of "Unavoidable" makes sense then from the POV of a puzzle generator. I'm suggesting it doesn't makes sense from the POV of a solver.

Ron

[Neunmalneun]

Sorry, Vidar. The contradiction is in box 2. If R3R7 = 2, R1C7 = 9 and R1C6 = 2. But now R2C78 form a naked pair (46) forcing cell R2C5 to be 2 as well. (I admit this deduction has nothing to do with the UR rule)

[Carcul]

Hi Vidarino.

...an AUR can often be used in several ways, and most of the times one of them solve the puzzle in a not very complicated way.

Sorry for going off topic again, but I noted something interesting. Let's consider again your first puzzle,

Code: Select all

+-------+-------+-------+
| 3 6 . | . 7 . | . 8 . |
| 7 . . | . . . | . . 1 |
| . . 5 | . 6 . | . 3 . |
+-------+-------+-------+
| . . 9 | . 3 . | . . . |
| . 4 . | . . . | . . . |
| . . . | . . 8 | . 5 2 |
+-------+-------+-------+
| 6 7 . | 9 5 . | . . . |
| . . 2 | 6 . . | . . 3 |
| 5 . . | 2 . . | . 9 6 |
+-------+-------+-------+

After the basic steps we get:

Code: Select all

  3   6    14   | 14   7    29   | 29     8     5     
  7   289  48   | 3    249  5    | 2469   246   1     
  49  129  5    | 8    6    1249 | 2479   3     479   
 ---------------+----------------+------------------
  28  5    9    | 147  3    1246 | 14678  1467  478   
  28  4    67   | 5    129  1269 | 3      167   789   
  1   3    67   | 47   49   8    | 4679   5     2     
 ---------------+----------------+------------------
  6   7    1348 | 9    5    134  | 1248   124   48     
  49  189  2    | 6    148  147  | 5      147   3     
  5   18   1348 | 2    148  1347 | 1478   9     6     


I have noted that we don't even "need" to advance the puzzle to the state that you have posted in order to use the AUR. This because we have

[r8c2]=9|4=[r8c5|r9c5](-4-[r2c5])-4-[r6c5](-9-[r5c5])-9-[r2c5](-2-[r5c5])-2-[r2c2]=2=[r3c2]=1=[r1c3]-1-[r1c4]=1=[r4c4]-1-[r5c5].

As before, this means that, if r8c2 is not "9" then r5c5 turns out to be an empty cell - contradiction. So, we must have r8c2=9 which solve the puzzle.

Regards, Carcul

[Myth Jellies]

I have noted that we don't even "need" to advance the puzzle to the state that you have posted in order to use the AUR. This because we have

[r8c2]=9|4=[r8c5|r9c5](-4-[r2c5])-4-[r6c5](-9-[r5c5])-9-[r2c5](-2-[r5c5])-2-[r2c2]=2=[r3c2]=1=[r1c3]-1-[r1c4]=1=[r4c4]-1-[r5c5].

...well maybe some of us do. I don't see how you can distinguish this type of a chain from a bifurcation that results in a crash. This looks to be quite different from a nice loop where a deduction can be made without assuming any particular candidate is true or false.

[Carcul]

Hi Myth Jellies.

...well maybe some of us do.

That's why I have written the word need between "".

I don't see how you can distinguish this type of a chain from a bifurcation that results in a crash.

And what is your definition of bifurcation? For me, this is just the construction of implications from a recognizable pattern. Btw, a nice loop also results in a crash, otherwise it would be of no use.

This looks to be quite different from a nice loop where a deduction can be made without assuming any particular candidate is true or false.

Of course it looks different, because it is a single implication network! But, a nice loop is a graphical way of representing the assumption that a candidate is true (discontinuous nice loop with two weak links with the same label in a node), false (discontinuous nice loop with two strong links with the same label in a node), or the two cases true and false at the same time (discontinuous nice loop with a strong link and a weak link with different labels in a node). Continuous nice loops can be viewed as representing the implications if a candidate different from the labels in a node of the loop is true.
With single implication networks (SINs) we have similar "rules" for identifying contradictions:

- if a SIN "ends" in one cell we have a contradiction when: (a) there are two strong links with different labels that end in that cell; (b) if the cell is populated by candidates "x", "y", "z", ..., and there are weak links with labels "x", "y", "z", ... that end in that cell (this is the empty cell contradiction argument); (c) there are two links, one strong and the other weak, with equal labels that end in that cell.
- if a SIN "ends" in different cells of the same unit we have a contradiction when: (a) there are two strong links with equal labels that end in two cells of that unit; (b) there are two weak links with the same label "x" that end in the only two possible cells of the unit for candidate "x".

Now, if a SIN begins with a weak link labeled "x" in cell A we are assuming that "x" is in A; if it begins with a strong link labeled "x" in cell A, then we are assuming that "x" is not in A and so "x" (or another candidate) is in a "conjugate" node; finally, if a SIN begins with a notation like "-x-[r7c7]" then we are assuming that "x" is not in r7c7, but in this case there is no "conjugate" node.
So, as you can see, with these "rules" we (or I, as seems to be more exact) can also make deductions with SINs without, as you say, "assuming any particular candidate is true or false.". As with nice loops, we just have to know how to interpret the combinations of strong and weak links.

Regards, Carcul

[ronk]

I don't see how you can distinguish this type of a chain from a bifurcation that results in a crash.

And what is your definition of bifurcation? For me, this is just the construction of implications from a recognizable pattern.

I interpreted Myth Jellies' comment to mean that a deduction based on multiple inference paths is more difficult to understand than a simple nice loop. For example, for your deduction ...

[r8c2]=9|4=[r8c5|r9c5](-4-[r2c5])-4-[r6c5](-9-[r5c5])-9-[r2c5](-2-[r5c5])-2-[r2c2]=2=[r3c2]=1=[r1c3]-1-[r1c4]=1=[r4c4]-1-[r5c5]

... we can draw a "implication flow" diagram ...

Code: Select all

                         > > > > > r6c5-9-r5c5 > > > > > > > > >
                       ^                                        V
                      > > > > > > r6c5-9-r2c5-2-r5c5 > > > > > > > 
                    ^                                             V
r8c2=9|4=r89c5-4-r6c5-9-r2c5-2-r2c2=2=r3c2=1=r1c3-1-r1c4=1=r4c4-1-r5c5
          v              ^
           > > r89c5-4-r2c5

[edit: shrunk a bit for reduced line wrap]

... which diverges at two locations and converges at two locations ... for a total of four distinct paths. That clearly is more difficult to understand than a diagram with just one path such as ...

Code: Select all

r8c2=9|4=[r8c5|r9c5]-4-r6c5-9-r2c5-2-r2c2=2=r3c2=1=r1c3-1-r1c4=1=r4c4-1-r5c5

[For illustration only, and not meant as a valid implication stream.]

And I further contend that multiple inferences using "(" and ")" in "nice loop" expression terms are even more difficult to understand than my flow chart above.

Regards, Ron

[Carcul]

Hi Ronk.

I interpreted Myth Jellies' comment to mean that a deduction based on multiple inference paths is more difficult to understand than a simple nice loop.

I agree with that, but, where is the problem? "Difficulty" is a subjective issue: typically, when I find something difficult I make an effort in order to understand it or turn it less difficult. Why don't you try?

And I further contend that multiple inferences using "(" and ")" in "nice loop" expression terms are even more difficult to understand than my flow chart above.

Ronk, instead of keeping criticizing my posts why don't you suggest a way of turning the notation more easily understandable? As far as I can see, you have not only understood the SIN but also made that good looking flow chart, so I don't know where is the problem.

Regards, Carcul

[ravel]

Once again: The hard it might be to find chains like Carcul's, the easy it is to follow them (without knowing what bifurcation, strong inference or SIN means). If you dont want to do it in your head, just print the candidate list and mark the forced and eliminated candidates from left to right (grouped nodes get a special mark). You can see easy then, what is not noted directly in the chain (eg that a cell must be this number, therefore it cannot be the other).
You can also read the chain backwards to get a triple forcing chain, eeh net:
r5c5=1 => r4c4<>1 => r1c4=1(=>r2c5<>1) => r1c3<>1 => r3c2=1 => r2c2=2 => r2c5<>2 => r2c5=4 => r89c5<>4 => r8c2=9
r5c5=2 => r2c5<>2 => r26c5=49 => r89c5<>4 => r8c2=9
r5c5=9 => r6c5<>9 => r6c5=4 => r89c5<>4 => r8c2=9

To get back to topic: The AUS seems to be a very rare thing, i never found one since i have been looking for it. I suppose that normally you will only get one after using advanced techniques.

[vidarino]

To get back to topic: The AUS seems to be a very rare thing, i never found one since i have been looking for it. I suppose that normally you will only get one after using advanced techniques.

Indeed they are. I have a collection of some 4000 puzzles that have some kind of uniqueness pattern in them, and I have found only a couple where any kind of AUS elimination can be done (type 1 and 2). And absolutely no hits for a type 3 yet - that is, I've found a few that match the pattern (extra candidates + neighbor tuple), but without any eliminations. So it's definitely not the most useful of patterns.

However, for me, the most interesting part was the realization that the strong inferences implied by the underlying uniqueness pattern live on, even after some the cells have been solved. In hindsight it sounds pretty obvious, though.

Hmm, and for a computer solver it's probably a lot easier to store the inferences for later, rather than trying to analyze the mix of candidate lists and solved cells. I think I'll have to try adding that to mine...

Vidar

[Myth Jellies]

Carcul, difficulty is not the issue at all.

Bifurcation: one example which most people would agree on is to assume one of the candidates in a cell is true. You can then fill in other candidates based on links to the cells you have filled in. If there is a crash, then you know the assumption was incorrect.

Single Implication Network: You examine the links between cells that would be applicable if you assumed one of the candidates is true, and if those links indicate a crash, then you know the assumption would be incorrect.

Well, since you fill in digits based on these links, I see no difference between these two. A Single Implication Network looks just like a virtual bifurcation. You may not have actually filled in the numbers as you went along, but you might as well have.

Contrast this with a double implication chain. Here all you are trying to find is a chain of candidates that are connected by alternating strong and weak links. Once you end up with the same digit you started with, you can look around and see if a deduction can be made. The candidates that you eliminate do not have to be part of the pattern you are searching for at all. This operates just as all other simpler forms of candidate reduction do.

[Carcul]

Hi Myth Jellies.

I have a question and a remark.

Question: Why are you so worried about the SIN, comparing it to bifurcation and bringing the question of " fill in digits"? In God's name Myth Jellies, if you don't like a deduction or don't want to see anything useful in it then simply ignore it.

Remark: It seems that bifurcation begins in a randomly selected cell. Well, this is not the case with the deductions that I post, as I always begin with a cell that has some kind of relation with a recognized pattern (a simplified b/b plot, an UR, an AUR, an AAUR, others AU patterns, ALS's), which eliminates a possible comparision with pure random T&E, so I don't see again where is the problem of that.

Contrast this with a double implication chain. Here all you are trying to find is (...) just as all other simpler forms of candidate reduction do.

Yes, I know, don't forget that I am a Nice Guy. This description is very nice, but, how do you use that in solving the hardest puzzles, where finding such a nice loop would be a miracle? All I am trying to do is to develop some kind of methodology (that looks good to me) that can be used in solving the hardest puzzles, and for that I decided to extend the concepts involved in nice loop construction and combine them with some recognizable patterns. A SIN is one of such combination, that has the great advantage over nice loops that it don't have a cyclic implication stream. You are looking at a SIN as just a kind of "virtual bifurcation" where, contrary to nice loops, is supposed to "fill in digits" (which to you looks like a real sin). I see a SIN as a way of combining patterns in order to make powerfull deductions.

Just a final comment: I have already seen in this forum some complex deductions that certainly must have involved "fill in digits" but, contrary to SINs, they where not criticized in this way. Why? Isn't it a matter of "taste"?

Regards, Carcul

[Myth Jellies]

Why are you so worried about the SIN, comparing it to bifurcation and bringing the question of " fill in digits"?....if you don't like a deduction or don't want to see anything useful in it then simply ignore it.

I probably would have ignored this post, just as I had ignored the dozen or so similar posts that you made preceding this one, if you hadn't indicated there was no "need" for an alternate method of advancing the puzzle. I am probably not the only one that did not know how to interpret your quotation marks.

I think that SIN is merely a virtual bifurcation because it always uses precisely the same number of steps, in fact the very same steps, that bifurcation can use to come up with a deduction. If you can prove me wrong, then great. But I see no reason why I should be forced to censor what seems to me to be a valid observation about SIN.

If you feel I have been unfairly harsh here, then my apologies in advance.