A Way to Do Sudokus You Can't Do Otherwise

Everything about Sudoku that doesn't fit in one of the other sections

A Way to Do Sudokus You Can't Do Otherwise

Postby weastman » Sun Sep 14, 2008 7:38 pm

Trial and error is rightly frowned upon by sudoku cognoscenti. But what constitutes unacceptable T & E compared to acceptable checking out of different logic chains is always subject to debate. Some devotees swear by “nishio,” in which you look for possible contradictions in your head, without writing anything down beyond your pencil marked list of candidates, while others swear at it as a Japanese euphemism for T & E. I have my own “maybe T & E maybe not” technique, which allows me to do puzzles in an hour or so that are rated as five or six-hour brain-crackers for experts and that would otherwise take me at least as long as that to do. It has similar though less dramatic effects for me in cracking less extreme puzzles. I call it “converging chains,” and it's easily explained.

You start with the converging chain technique when you've gone as far as you can in paring down your pencil-marks with your other techniques. You then pick a square with two candidates that looks critical to the puzzle, in that either answer will allow you to determine a fair number of other squares. You then assume one answer to the square, and follow the chain forward. After doing that for a while—not until you arrive at a contradiction, just long enough to have a number of answers, preferably in different parts of the puzzle—you stop working on that chain and start following the complementary chain that is based on assuming that the other answer to the first square is right. If a step in that second chain produces the same answer for any square as the first chain does, voila! That answer must be right, and you write it in. Then you go back to solving the puzzle with your other techniques.

To keep track of the two chains, I use dots above the numbers for the first chain and dots below for the second chain. There are plenty of possible refinements--if you want to be a purist, you can do the two chains in your head without dots, and if you're eager for a faster solution you should use chains not just with squares with only two candidates but also with boxes, rows, and columns in which a given number can only be put in two places (or you can go further on the chains and find multiple converging squares rather than stopping when you get the first one).

Is converging chains kosher? I don't have an absolute answer, but I think it's worth using when you've gone as far as you can otherwise, and I pass it on for what's it's worth.
weastman
 
Posts: 3
Joined: 14 September 2008

Postby Mike Barker » Fri Sep 19, 2008 10:34 am

This sounds like the same technique described here. It has also similar to Red-Green Transport. I don't think anyone will complain about using the technique for manual solving, but don't expect any kudos for using the technique unless you can provide a good reason for choosing the starting cell.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby weastman » Tue Sep 23, 2008 9:33 am

I agree with Mike's comments, and want to thank him for posting the links.

The "good reason" for picking the starting square boils down to an intuition that either candidate for the square will crack the puzzle. That means that a good starting point for converging chains/forcing chains/red-green transport is also a good starting point for a pure T & E approach of seeing whether a guess produces a contradiction or solves the puzzle. In doing converging chains/forcing chains/RGT, I find myself coming up with a T & E contradiction before I get a convergence maybe 10-20% of the time. That means the method is not as distinct from T & E as it should be, though I still like it as a way to solve puzzles manually that are otherwise too time-consuming.
weastman
 
Posts: 3
Joined: 14 September 2008

Postby 999_Springs » Sun Sep 28, 2008 12:43 pm

I solved this puzzle recently:
Code: Select all
#14 from the top95
     3      5      6 ||    18      7     18 ||     2      9      4
    29     79    279 ||    36      4     36 ||     8      5      1
     8      4      1 ||     9      5      2 ||     7      3      6
=====================||=====================||====================
    26      1     23 ||     4     36      5 ||     9     78     78
     7     39      4 ||   138    139   1389 ||     6      2      5
   569    689    589 ||     2     69      7 ||     4      1      3
=====================||=====================||====================
   169      2   3789 ||  1367    139   1369 ||     5      4    789
 14569    679    579 ||   167      8   1469 ||     3     67      2
   469  36789   3789 ||     5      2   3469 ||     1    678    789


It might look like, at first glance, it would be solvable solely by means of your "converging chains", but I can't find a way to do so. Is it possible?
(I start with r4c1 as the starting cell and that gives r6c2r789c1<>6, r5c56<>3... and then I find nothing.)
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby Draco » Sun Sep 28, 2008 1:58 pm

999_Springs wrote:I solved this puzzle recently:
Code: Select all
#14 from the top95
     3      5      6 ||    18      7     18 ||     2      9      4
    29     79    279 ||    36      4     36 ||     8      5      1
     8      4      1 ||     9      5      2 ||     7      3      6
=====================||=====================||====================
    26      1     23 ||     4     36      5 ||     9     78     78
     7     39      4 ||   138    139   1389 ||     6      2      5
   569    689    589 ||     2     69      7 ||     4      1      3
=====================||=====================||====================
   169      2   3789 ||  1367    139   1369 ||     5      4    789
 14569    679    579 ||   167      8   1469 ||     3     67      2
   469  36789   3789 ||     5      2   3469 ||     1    678    789


It might look like, at first glance, it would be solvable solely by means of your "converging chains", but I can't find a way to do so. Is it possible?
(I start with r4c1 as the starting cell and that gives r6c2r789c1<>6, r5c56<>3... and then I find nothing.)

If you are willing to allow for networks then weastman's technique works out. Starting from your PMs:
Code: Select all
r8c4=7 r8c8=6
r8c4=7 [r8c2<>7] + r8c8=6 [r8c2<>6] = r8c2=9
r8c4=7 [r8c3<>7] + r8c2=9 [r8c3<>9] = r8c3=5 r6c1=5
r8c2=9 r5c2=3 r4c3=2 r2c1=2
r8c2=9 r2c2=7
r5c2=3 r4c5=3 r6c5=6
[r2c2<>9 + r2c1<>9] = r2c3=9
r8c2=9 [r6c2<>9] + [r6c1<>9 + r6c5<>9] = r6c3=9
Contradiction on c3=9 ==> r8c4<>7

Singleton at r7c4

r4c5=3 r4c1=6 [r7c1<>6] r7c6=6
r4c5=3 [r5c4<>3] r2c4=3 r8c4=6
Contradiction on b8=6 ==> r4c5<>3

Singles to solve

The first network takes 5 steps to reach the contradiction (some of the lines in the first network listing are "simultaneous" due its forking pattern, though I chose not to create a 2D represenation that demonstrates this), the second requries only 2.

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

A Way to Do Sudokus You Can't Do Otherwise

Postby weastman » Tue Oct 07, 2008 12:42 pm

When I applied converging chains starting at r4c1 in the puzzle posted by 999_Springs, I arrived at a T&E contradiction in the chain in which r4c1=6. (Because r9c9=9 and r9c1=4, r9c6=3 or 6--but r2c6 and r7c6 also = 3 or 6, which can't be.) So the method gives a solution, but not a pretty one. Oh well...

I then ignored the T&E in that chain (not sure I would have done that in real-life solving as opposed to a Sudoku forum) and did the other chain with r4c1=2. That led to a convergence of the chains on r9c1=4 and then a straight path to the solution.
weastman
 
Posts: 3
Joined: 14 September 2008

Postby aran » Sat Oct 11, 2008 7:10 am

Mike
This sounds like the same technique described here. It has also similar to Red-Green Transport. I don't think anyone will complain about using the technique for manual solving, but don't expect any kudos for using the technique unless you can provide a good reason for choosing the starting cell.

Long time no speak !
RGT was just about simultaneous with the crash of the other forum, and led a pretty rough short life over there.
Just for the moment set aside the question of the initial strong link.
Thereafter RGT produces useful information : eliminations via discontinuous loops, AICs, multi-implication streams, forcing chains and nets.
Suppose now that one of those discontinuous loop eliminations was found independently.
What in general would be the opinion of the move ?
By and large I think it would be regarded as "acceptable".
However if one applies your "good reason" test, then probably not.
But with that test, what moves become acceptable ?
So far as I can tell only pattern based moves dear to Myth's heart !
There is no denying the beauty of patterns but they don't solve much at the difficult end of the spectrum.
Take as an example these days the regular use of Kraken moves.
(Kraken I think is now synonymous with SIS/at least one truth among several : in other words, the original Kraken fish was just a special case of SIS ie either fish or x and either way eliminate z).
What is the "good reason" for examining a Kraken anything ?
Can the solver say more than "it looks promising" or "it may well lead somewhere" ?
All of that applies to the choice of starting strong link in RGT.
RGT could also very much be considered as simple tagging (two colours).
In what way is it less than any other of the tagging approaches ?

All of that said, I'm not even advocating RGT because it does take care of the vast majority of sudokus too easily.
But it would be good to find a solid reason to dispose of it.
PS "feels like T&E" isn't solid enough !
aran
 
Posts: 334
Joined: 02 March 2007


Return to General