## Identification of forcing chains

Advanced methods and approaches for solving Sudoku puzzles
Maria45 wrote:Last trick: dont start at cells like e12 in the example. These are "end points", the roads usually run dead from there, that is: you don't find a forcing chain there, because the "force" runs out, not enough mutually exclusive cells/values from there.

I don't agree with this: see, for example, here the solution that I have provided using precisely this type of cells. Also, there is always the possibility of using these cells in AURs (or Almost Almost Unique Rectangles).

Regards, Carcul
Carcul

Posts: 724
Joined: 04 November 2005

Sure, Carcul. You solved the puzzle by contradiction. I try to avoid contradiction as it works only sometimes and somehow feels awkward. Possibly that feelings originates from my old mathematician heritage that constructive proofs are always superior to proofs by contradiction.

In complex puzzles you usually cannot apply contradictions, because the puzzle is not reduced enough (too many candidates for one cell). Exceptions exist, of course. Like your puzzle which I solved with 36 forcing chains and 3 contradictions. I was somehow tired looking for substitutions for the 3 contradictions. It would have been much easier if I used uniqueness, too. Lastly, this are only considerations of style. As I solved all puzzles I worked with, I got somehow "snobby" and discontinued the use of some tactics. In other words, the fact I used contradictions at all was an implicit admittance to the hardness of the puzzle...

Let my cite the puzzle you mentioned in my notation:

Code: Select all
`-----------------------+-------------------+-------------------|   | 1      2      3    | 4     5      6    | 7      8      9   |-----------------------+-------------------+-------------------|  a| 6      8      2    | 3     5      7    | 4      9      1   |  b| 1      4      3    | 8     6      9    | 5      2      7   |  c| 5      7      9    | 2     14     14   | 68     68     3   | -----------------------+-------------------+-------------------|  d| 3      9      78   | 6     78     5    | 2      1      4   |  e| 78     2      6    | 14    3      14   | 9      57     58  |  f| 4      5      1    | 79    789    2    | 78     3      6   | -----------------------+-------------------+-------------------|  g| 278    6      5    | 479   2479   3    | 1      47     89  |  h| 27     3      4    | 179   1279   8    | 67     567    59  |  k| 9      1      78   | 5     47     6    | 3      478    2   | -----------------------+-------------------+-------------------|`

I think the xyz-wing Vidarino mentioned is more elegant or written as a sweet short forcing chain (yeah, I love it...):

h8!=5, h78=67 or h8=5, e8=7 > gk79!=7 and that solves it.

Kind regards, Maria
maria45

Posts: 54
Joined: 23 October 2005

Hi Maria45.

Maria45 wrote:You solved the puzzle by contradiction. I try to avoid contradiction as it works only sometimes and somehow feels awkward.

What you call "contradiction" is just a special case of what in known as "nice loops". And it don't work only sometimes: you just have to know how to spot that proofs.

Maria45 wrote:Possibly that feelings originates from my old mathematician heritage that constructive proofs are always superior to proofs by contradiction.

That is only a personal opinion of yours, because obviously any logical deduction is good. Also, I (we?) don't make any distinction between constructive and by contradiction proofs (terms that I have never heard of).

Maria45 wrote:In complex puzzles you usually cannot apply contradictions, because the puzzle is not reduced enough (too many candidates for one cell).

Perhaps that is because you are restricting yourself to bivalue cells: I could present you a dozen examples of "contradictions" in poli-valued cells.

Maria45 wrote:I think the xyz-wing Vidarino mentioned is more elegant

Yes, elegance is a personal question: I find my solution more elegant because it immediatly solves the puzzle without the need for the X-Wing, whereas the XYZ-Wing can only solve the puzzle after the X-Wing.

Regards, Carcul
Carcul

Posts: 724
Joined: 04 November 2005

maria45 wrote:I try to avoid contradiction as it works only sometimes and somehow feels awkward. Possibly that feelings originates from my old mathematician heritage that constructive proofs are always superior to proofs by contradiction.

Dont agree in general. You wouldnt even be able to prove constructively that prime numbers are infinite, but the proof by contradiction is simple, short and elegant.
Wolfgang

Posts: 208
Joined: 22 June 2005

Hi Carcul,
Carcul wrote:I find my solution more elegant because it immediatly solves the puzzle without the need for the X-Wing, whereas the XYZ-Wing can only solve the puzzle after the X-Wing.

This seems to be way tooo sophisticated for me. Your contradiction just prooves that c7!=6. The solution (c7=8 etc.) follows. The X-Wing prooves that gk8!= 7. The solution (g8=4, k8=8, c8=6, c7=8 etc. identical to that which must follow in your solution) follows. These are just two different tactics applied at different cells leading (of course) to the same solution, in my eyes.

Or could you illuminate my understanding of the fine distinction you drew???

Hi Wolfgang,
yes, why did I know that this example would show up? Regarding the infinity of primes, ok. But regarding another, somehow more attractive point: a constructive proof of the compositeness of a number (i.e. giving the factors) is just a lot more useful than the knowledge that it is no prime..., or: more back to topic: the proof by contradiction that a sudoku has exactly one solution doesnt quite appeal to me as fascinating as the solution itself...

Kind regards, Maria
maria45

Posts: 54
Joined: 23 October 2005

Concerning Crazy's puzzle i think we all agree that my solution was the first but worst I like both Vidar's and Carcul's.
Maria, for solving sudokus proof by contradiction *is* constructive, you can eliminate a concrete candidate. So let me call a deduction that directly leads to a number or elimination "positive" and one which needs proof by contradiction "negative". This reflects the fact that the vast majority (including my friend) prefers the first one. I accept that, because i can understand it psychologically.
But no one seems to have a problem with using techniques like x-wing or UR. How would i explain, why they can be used? I would say, "if you put x there, you get a contradiction to the rule that the number must be only once in the row" or "if you dont put x there, you get a contradiction to the assumption that the puzzle is unique". Are there "positive" explanations? If not, using the techniques is just a hidden form of using proof by contradiction.
[Edit:]
Ok, you can say "you already do have a number for this row, so you can eliminate the other candidates", this sounds positively, though its the same in other words. Same for pairs, coloring, locked candidates etc. So most techniques are "positive".
Fact is that the harder puzzles are, the less you can apply positive techniques. So we have positive and negative puzzles
And: As you said, normally also you would apply a UR instead of a lot of forcing chains. In this case (and there are many others) the negative method is far more elegant.
Wolfgang

Posts: 208
Joined: 22 June 2005

Well, some time has passed since I wrote the earlier comments. I would like to add:

In the hardest puzzles like #0089, some eliminations by contradiction seem to be necessary.

And, yes, Carcul, I concede that there are some nice contradictions possible with still a huge net of possibilities.

so long, Maria
maria45

Posts: 54
Joined: 23 October 2005

I am not sure if my technique has much to do with forcing chains, but the results are similar to them (and to nice loops etc.).

I always look for cells containing three candidates (abc) and try to look for the results if I elimate one candidate ("c"; leaving "a" and "b"). Best choice are eliminations which lead to AURs.

If this elimination leads to (only) "a" or (only) "b" in the "starting cell" (I like Maria's terminology), then I can safely eliminate "b" or "a" in this starting cell. (If the right candidate of the starting cell is "c", "a" and "b" are wrong anyway.)

However, if this elimination leads to the elimination of "c" in a cell which is seen by the starting cell (goal cell) I can eliminate "c" in the goal cell (if "c" is correct in the starting cell, "c" cannot be right in the goal cell)
Neunmalneun

Posts: 52
Joined: 22 December 2005

Previous