The New Sudoku Players' Forum

[fdh319]

After some basics with this puzzle, I arrived to the next position. It is easily solved with an XY Wing, but I decided to see if I can finish it with a forcing chain.

Code: Select all

*-----------*
 |...|.1.|435|
 |...|..4|.1.|
 |..9|5..|7..|
 |---+---+---|
 |63.|...|...|
 |54.|...|.98|
 |...|...|6.4|
 |---+---+---|
 |9.2|.3.|...|
 |...|7..|..2|
 |...|..8|.5.|
 *-----------*
[code] *-----------*
 |826|917|435|
 |375|..4|219|
 |419|523|786|
 |---+---+---|
 |63.|..9|521|
 |54.|..2|398|
 |29.|3..|674|
 |---+---+---|
 |952|.3.|8.7|
 |183|7..|9.2|
 |764|298|153|
 *-----------*
 [code]*--------------------------------------------------*
 | 8    2    6    | 9    1    7    | 4    3    5    |
 | 3    7    5    | 68   68   4    | 2    1    9    |
 | 4    1    9    | 5    2    3    | 7    8    6    |
 |----------------+----------------+----------------|
 | 6    3    78   | 48   478  9    | 5    2    1    |
 | 5    4    17   | 16   67   2    | 3    9    8    |
 | 2    9    18   | 3    58   15   | 6    7    4    |
 |----------------+----------------+----------------|
 | 9    5    2    | 14   3    16   | 8    46   7    |
 | 1    8    3    | 7    45   56   | 9    46   2    |
 | 7    6    4    | 2    9    8    | 1    5    3    |
 *--------------------------------------------------*


First Chain: 6r2c4 - 8r2c5 - 5r6c5 - 4r8c5 - 1r7c4 - 6r5c4 - 8r2c4 Contradiction. Chain implies r2c4 = 8
Second Chain: 8r2c4 - 6r2c5 - 7r5c5 - 1r5c3 - 6r5c4 - 8r2c4 Consistent result. r2c4 = 8
So far, so good. But next I tried a third path and came up with r2c4 = 6!
Third Chain: 6r2c4 - 1r5c4 - 7r5c3 - 6r5c5 - 8r2c5 - 6r2c4. Why? Where have I gone wrong?

[SpAce]

After some basics with this puzzle, I arrived to the next position. It is easily solved with an XY Wing, but I decided to see if I can finish it with a forcing chain.
First Chain: 6r2c4 - 8r2c5 - 5r6c5 - 4r8c5 - 1r7c4 - 6r5c4 - 8r2c4 Contradiction. Chain implies r2c4 = 8
Second Chain: 8r2c4 - 6r2c5 - 7r5c5 - 1r5c3 - 6r5c4 - 8r2c4 Consistent result. r2c4 = 8
So far, so good. But next I tried a third path and came up with r2c4 = 6!
Third Chain: 6r2c4 - 1r5c4 - 7r5c3 - 6r5c5 - 8r2c5 - 6r2c4. Why? Where have I gone wrong?

You haven't gone wrong anywhere except with your weird notation (instead of '-' you should use '->' or '=>' to mean implication). It's perfectly normal to get two different results with a candidate if that candidate is false (as 6r2c4 is). True candidates can never lead into false results (so their results are never inconsistent), but false candidates lead into both kinds. That's one way to recognize false candidates via contradiction and eliminate them.

Btw, have you heard of BUG+1? It's the most obvious solution to your puzzle.

[Leren]

To explain the BUG+1 move, r4c5 must be 8. If it wasn't, every unsolved cell would have exactly 2 digits and every candidate would appear exactly twice in its row, column and box.

In these circumstances the puzzle would have either 0 or 2 solutions, its a kind of giant UR. You can read about the BUG+1 principle here.

Leren

[fdh319]

Hi Space,
I didn't know that a chain may sometimes be misleading. So my next question is; Suppose a chain which confirms the contradiction chain isn't possible (2nd chain in my post), whom are you going to believe? And suppose the contradiction chain (first chain in my post) isn't possible, how are you going to decide which chain is true and the other is false? I know that the false candidate will finally result in a conflict, but this is not the case.

SpAce wrote:

Btw, have you heard of BUG+1? It's the most obvious solution to your puzzle.

Concerning the BUG+1. Of course I have heard about it, but haven't yet mastered it.
Thanks a lot SpAce

Leren wrote:

In these circumstances the puzzle would have either 0 or 2 solutions, its a kind of giant UR. You can read about the BUG+1 principle here.

Hi Leren,
Right now I'm exploring the possibilities of chains and less interested in a puzzle's solution, but certainly I'll take your good advice into consideration.
Thanks a lot Leren

[SpAce]

I didn't know that a chain may sometimes be misleading. So my next question is; Suppose a chain which confirms the contradiction chain isn't possible (2nd chain in my post), whom are you going to believe? And suppose the contradiction chain (first chain in my post) isn't possible, how are you going to decide which chain is true and the other is false? I know that the false candidate will finally result in a conflict, but this is not the case.

Hi fdh319. There are two ways to see and use forcing chains. One is to pick a binary condition (e.g. a certain candidate must be either true or false but not both or neither) and assume it one way. If you find two contradicting chains (or any other contradiction) for a single assumption, you know it must be false and its binary opposite true. If you don't find a contradiction, then you can't conclude anything. True candidates can't lie but false ones can, so basically you're trying to catch a liar.

The other way is to pick a group of candidates (or more generally boolean conditions) where you know that at least one of them must be true, and then find chains for each of them such that they all agree on a result. In that case you're proving the agreed result instead of anything about the assumptions themselves, which makes it "non-assumptive" (considered more elegant by most solvers). Why does it work? For the same reason as the other one. True candidates can't lie, and since our choice of a tested group must include at least one true candidate the only way to make everyone agree is on a true result. False candidates can be swayed either way but true ones are single-minded so they could never agree on a false result (as long as you don't make mistakes with your chains).

Both methods, especially the latter, are discussed in this thread, though it also happens to deal with BUGs. In a BUG+n situation you know that at least one of the +n candidates must be true to prevent the illegal BUG pattern, so if you find agreeing chains for every one of them, then you know the agreed result must be true. The same principle works for any group of candidates if at least one of them has to be true (e.g. all candidates in a cell, all instances of a digit in a house). Important: with this method you're not trying to find out which of those tested candidates are true or false -- just a result they agree on, which is called a verity (as opposed to a contradiction). More on both contradiction and verity types of forcing chains here. In most cases contradiction and verity types of forcing chains are just two ways to see the same thing, so they can be easily converted into each other (often just by reversing the chains).

Concerning the BUG+1. Of course I have heard about it, but haven't yet mastered it.

I highly recommend you look into BUGs. They're quite common and fun ways to solve a puzzle. Besides, they teach you about the principles laid out above. BUG+1 is the simplest case where there's only one extra candidate which must be true. In any other BUG+n situation you have to find an agreed result for every extra candidate.

Right now I'm exploring the possibilities of chains and less interested in a puzzle's solution

That's the right attitude if you really want to learn!

[SpAce]

In these circumstances the puzzle would have either 0 or 2 solutions, its a kind of giant UR.

When would it be 0 solutions? Isn't it always exactly two solutions if you have a true BUG+0 situation? I've understood that uniqueness deadly patterns (URs, BUGs, BUG-Lites, MUGs...) would always cause multiple solutions while non-uniqueness DPs (such as Oddagons, deadly fishes, etc) would result in zero solutions. So, using one or the other type of DP for deductions is based on a different assumption about the puzzle: uniqueness DPs rely on the assumption that there's no more than one solution while the other kind depends on having at least one solution. If you know you have a valid puzzle (exactly one solution) then you can safely use both, but I don't think there's overlap between the two kinds.

[Added: Of course you could have a smaller uniqueness DP (with multiple solutions locally) and still have zero solutions for the whole grid, but that's caused by something external to the uniqueness DP. BUGs shouldn't have that possibility at all because they cover the whole grid.]

[Leren]

SpAce wrote :When would it be 0 solutions? Isn't it always exactly two solutions if you have a true BUG+0 situation? I've understood that uniqueness deadly patterns (URs, BUGs, BUG-Lites, MUGs...) would always cause multiple solutions.

Time to get on the soapbox. For many years I believed exactly what you say, because of the way uniqueness moves are described on various websites. They say words to the effect that if one half of the fully exposed DP is a solution, then the other half is also a solution. This is not strictly true and misleading. The correct description should be words to the effect that the solution state of one half of the DP is the same as the other half. In short, if the DP is fully exposed, the number of solutions is 0 or 2, ie it is not 1 !

Now in published puzzles which of the two cases is used for the fully exposed DP. Well, by mutual agreement, it's the 0 solution state ! That's right, the case they never talk about is the one they always use. Incredible but true.

The reason is to ensure that the puzzle has a unique solution with at least one of the guard candidates in the DP cells being true in the solution.

Think about what you are saying about this puzzle. If the exposed BUG cells resulted in 2 solutions then the puzzle would have 3 solutions, with all 3 candidates in r4c5 being true in one of the 3 solutions. A 3 solution puzzle is regarded by most puzzle makers and solvers as unfair, although this was not mentioned in the original descriptions of Sudoku puzzles, hence the well known Uniqueness Controversy, which you can read about here.

Try putting 4 or 7 into r4c5 of this puzzle and I'm pretty sure that you will end up with a contradiction. I tried it and I did.

Leren

<edit>

Just picked up these words from the Hodoku site here:

A situation like this is invalid, because the candidates in the cells could be exchanged, thus resulting in two different solutions that both satisfy the sudoku rule (see below). If the sudoku has only one solution, any situation that could lead to a Unique Rectangle must be avoided.

This would certainly lead you to believe that DP's "normally" have 2 solutions. In fact, the solution grid they show does have two solutions, but a puzzle leading to this grid would never be published unless it had a clue in one of the DP cells.

[SpAce]

Thanks for explaining, Leren! You're absolutely right, of course. There are exactly two solutions only if the BUG+0 cells are considered in isolation, but in the context of the whole grid (of a valid puzzle) neither would work with the givens so it's actually zero solutions. That's a much more accurate perspective. Thanks for that!

In fact, doesn't that piece of enlightenment kind of unify all DPs, uniqueness or not, since in a valid puzzle they would all lead into zero solutions? The whole multiple-solution threat seems to work only in isolation but not on the grid level.

[Leren]

Hi SpAce,

I fully sympathise with your original miss-understanding. You have been misled by inaccurate descriptions of the whole business of Uniqueness moves on many web sites, like I was for many years.

An interesting corollary of of the 0 solution state of DP's is that you can have UR moves with missing candidates, Which Hodoku describes here.

Because the exposed UR is invalid, it's sometimes possible to disprove one of the UR candidates by some move that has nothing to do with uniqueness. But curiously, the UR move doesn't go away. In other words, you can still play a UR move even though one half of the UR pattern has already been disproved. You can mentally "put back" the eliminated UR candidate and play the UR move. But this only works because both halves of the UR are invalid. So, having misled us with their basic description of how UR moves work, they then have a whole section that depends crucially on the 0 solution state of a fully exposed UR. Go figure !

Maybe we should start a gripe thread on victims of misleading descriptions of Uniqueness moves on many web sites

Leren

[SpAce]

I fully sympathise with your original miss-understanding. You have been misled by inaccurate descriptions of the whole business of Uniqueness moves on many web sites, like I was for many years.

I'm glad you exposed that misconception. It's actually pretty self-evident if you stop to think about it, which is why your explanation made immediate sense, but I guess I never had.

In this case the misconception doesn't seem to cause actual mistakes or missed opportunities, though, which might explain why it's been able to fly under the radar. For solving purposes it's still quite all right to look at a uniqueness DP as having multiple solutions (in isolation) because it's easier to spot and verify that way. It just should be understood that the multi-solution threat is a local effect only, which is where the common explanations seem to fail. I'll try not to repeat that lie from now on!

An interesting corollary of of the 0 solution state of DP's is that you can have UR moves with missing candidates,

Indeed! It's a better explanation to why it works.

Maybe we should start a gripe thread on victims of misleading descriptions of Uniqueness moves on many web sites

Maybe Then again, it might hard to prove any actual damage those misleading descriptions have caused, as they seem to work for practical purposes. I'd still prefer conceptual accuracy, though, and I thank you for providing that!

[Leren]

SpAce wrote : Indeed! It's a better explanation to why it works.

Actually, its the only explanation of why it works. If the solution state of the DP pattern was 2 you couldn't have (correctly) eliminated the missing candidates in the first place.

Another interesting corollary is that you can sometimes make a puzzle harder by adding a clue ! Sounds crazy but here is why it sometimes works. In the lower clue puzzle it would be very hard except for some crucial uniqueness move, which simplifies the puzzle solution. If you add a clue in one of the UR cells, you lose the information that the remaining UR digits arrangement can't work, thereby possibly making the puzzle harder. I can't remember an example of this in
Sudoku but it's come up a few times on Andrew Stewart's Str8ts forum.

Leren

[SpAce]

Another interesting corollary is that you can sometimes make a puzzle harder by adding a clue ! ... I can't remember an example of this in Sudoku

The only example I've seen is this but I guess it's quite possible in general.

[StrmCkr]

I'll dig for the links for that leren, me and a few others posted examples of making puzzles rating harder by adding clues way back in the day.
http://forum.enjoysudoku.com/making-a-puzzle-harder-by-adding-a-number-t3907-45.html
Another intresting read is on reverse bug and reverse bug light by RW
http://sudopedia.enjoysudoku.com/Reverse_BUG.html
http://forum.enjoysudoku.com/the-reverse-bug-t4431.html

I think the best explination expands off the ur1. 1
http://forum.enjoysudoku.com/post63659.html#p63659

[fdh319]

Irrelevant question, removed by author.

[SpAce]

Can I therefore say that no matter what, the result of a contradiction chain is always true and assign that result to the cell safely?

No one stops you from saying that but it makes no sense A successful contradiction chain proves the initial assumption (whatever it is) false, and that's it. For example, if the assumption is "Candidate A is true" and that results in a contradiction, then you can safely conclude that "Candidate A is not true" and eliminate that candidate (which may or may not result in a placement of another candidate). In other words you're typically assuming a placement and if you find a contradiction it turns into an elimination instead (but if you don't find a contradiction it doesn't mean you can place that candidate -- it works one-way only!)

You get to place the tested candidate only if your initial assumption is "Candidate A is false" and then find a contradiction for that assumption (because then you have a double-false, hence Candidate A must be true). You get to do that only if your tested candidate is in a bivalue cell or has a bilocation or other strongly linked partner. However, normally we just assume a candidate to be true and then eliminate that possibility if a contradiction is found. That's why it's a good idea to primarily test strongly linked candidates, because then you get an immediate placement after the elimination (but it's a side effect).

The opposite of a contradiction is a verity which proves something true by finding an agreement for all possible cases of some group that is known to have at least one truth. Unlike a contradiction, it doesn't normally prove anything about the cases themselves but something external to them. Also, even though it by definition proves something true (if successful) it doesn't mean it necessarily proves a placement to be true. In fact, usually we're proving that an elimination must be true (which is really the same as proving a placement false with a contradiction chain) -- thus whether you can place something depends on the same circumstances as with the contradiction chain.

True and False are just boolean values which can be attached to any statement, so by themselves they mean nothing. Contradictions prove falsehoods and Verities prove truths, but both can be used to prove the same eliminations or placements. They're just two sides of the same coin, and usually easily converted into each other -- but they shouldn't be confused with each other.