The New Sudoku Players' Forum

[Nick70]

However, the chain that you mentioned (4,4)(4,1)(9,1)(9,5)(5,5) is not a turbot fish as decribed in your other thread, because in row 9, there are 3 cells with a candidate of "7", and same as in column 7. Your turbot fish requires each side to have only 2 cells containing the candidate.

On the contrary. A Turbot Fish CANNOT have only 2 cells on EVERY side. It would be a contradiction.
There can be four, three or even only two "strong" sides. This is all explained in the above link.

By the way, My "OPEN CHAIN OF SUDO" technique looks for not only conjugate link, but also like links. (Refer my example). Each Like link consists of 2 cells which will both have the same candidate or both NOT have the same candidate. This allows you to propogate further along the grid.

This is what focing chains do. I've posted several examples of forcing chains with alternating conjugate and like links in the past days.

For example, the "X-Wing" and "Swordfish" are subsets of "CLOSE CHAIN OF SUDO". Subset, because the "X-Wing" and "Swordfish" only consider rows and columns, but not boxes.

X-Wing and Swordfish don't consider boxes not because they can't, but because it would be useless.

Consider a X-Wing where the conjugate cells are in boxes 1 and 4, and they also are in columns 1 and 3. The X-Wing would allow you to remove candidates from box 7 in columns 1 and 3.
But you don't need a X-Wing to do that, you just need the "single sector candidate" rule. Since the cells are conjugate in boxes 1 and 4, it means that the number is nowhere else in those boxes, so it isn't in column 2. Therefore in box 7 the number must be in column 2 so candidates can be removed from the rest of box 7.

[Nick70]

BTW, everything can be replaced by forcing chains. All "rules" we have are special cases of forcing chains which we classify and assign a name to.

Also a 9-cell swordfish ? Do you need "double forcing chains" for that (i dont know, what that is) ?

You are right, a 9-cell swordfish wouldn't be identified by forcing chains.

[angusj]

I accept your advise as an 8 year old so I won't get offended.

Firstly, I've reread my post to you in the light of a little sleep and apologise for being somewhat condecending.

I've also had another look at your "simple chain of sudo" (no shouting capslock please ) and compared it closely with existing algorithms (see links below). I now humbly concede that while not strickly 'new', I think it does add helpfully to the solving mesh. (However, I certainly don't want to come across as an arbitor of what's 'valid' and what's not - it really is up to the individual as to what they find helpful and what they don't. So, I'm simply expressing what *I* find helpful.)

Here's a very incomplete list of posts which I've found which explore some advanced solving techniques:

Doug: Implication Trees
MadOverlord: Forcing Chains
http://www.setbb.com/phpbb/viewtopic.php?t=40&highlight=forcing+chains&mforum=sudoku

Rubylips: Nishio
http://www.setbb.com/phpbb/viewtopic.php?t=11&mforum=sudoku

AMcK: The colouring method
http://www.setbb.com/phpbb/viewtopic.php?t=12&postdays=0&postorder=asc&start=15&mforum=sudoku#63

AMcK: The multi-colouring method
http://www.setbb.com/phpbb/viewtopic.php?t=83&mforum=sudoku

Nick70: Advanced coloring
http://www.setbb.com/phpbb/viewtopic.php?t=77&mforum=sudoku

Angus, I admire what you have done but please don't carry any negative thoughts.

No, I certainly don't carry any negative thoughts, just some feelings of regret for the way I expressed my previous post.

Angus

[George]

Augus, thank you for your understanding and pointing me to the useful links.

[George]

Message cancelled

[Nick70]

Although it was derived from "Colour", I felt the need to give this technique a more meaningful name such that the idea would be easily grasped by others as I try to share it.

This is somewhat contradictory. In other porsts you say that you don't like "guessing" and want "pure logic" and then you propose a technique that requires you to "guess" which chains to use, considering it better than the simple coloring technique which requires no guessing at all (apart from the choice of the number to color, of course).

With the simple coloring techinque, once you have chosen a number, you color the whole grid, giving conjugate colors to conjugate placements for the number.

Once you have done that, you look at the grid and look for:
1/ two cells in the same unit colored with the same color: this is an immediate contradiction, so the color is false and its conjugate is true.
2/ two cells with conjugate color placed in the same unit. Since one of them must be true, all other cells in the unit can be cleared from the number.
2a/ (generalization of the above) two intersecting units that contain two cells with conjugate color. Since one of them must be true, all the other cells in the intersection can be cleared from the number.

2a is a generalization of 2 because every unit intersects itself.

Simple coloring is equivalent to the "open chain of sudo" (2a/) and "closed chain of sudo" (1/) you have described.

Furthermore, when "like" links are included in the technique, "Colour" and "Turbot Fish" naturally became a subset. I think Wolfgang has pointed out the same in his discussion with Nick.

I have to reiterate that this is no news. I actually defined that pattern while looking at the simplest problems that could be solved with double forcing chains.
The reason to give it a name and formal description was that it's so comon. I have 2500 problems that can be solved using Turbot, vs. only 100 that can be solved with X-Wing. I don't see why the X-Wing should have a name and the Turbot, which is 25 times more common, shouldn't.

I was doing some "extreme" sudokus generated by Simple Sudoku yesterday, looking for Turbots in them. With Simple Sudoku's filtering, I find fishing for turbots to be quite effective.
Hint: look for the "fin" first (the diagonal link). When you have chosen the diagonal side, it's a blink of an eye to draw perpendicular lines from its vertices in the 4 possible ways and see if they intersect on a fifth cell containing the number. If they do, it's another blink of an eye to check if at least two of the sides are strong. If they are, you have found a turbot.

This certainly is quicker than using coloring, especially if the turbot has only two or three non consecutive strong sides.

[Wolfgang]

Here's a very incomplete list of posts which I've found which explore some advanced solving techniques:

None of the links worked for me now, though i believe that i have been there already, maybe the server is down in the moment ?

[Wolfgang]

..the server is down in the moment ?

yes it was, works again ;)

[George]

Message deleted.

[tso]

Yes George, we all know how busy an 8 year old's life can be, what with their internet lecturing duties. Hey, after you get through renaming everything that everyone here was heading towards a consensus on -- maybe you could have your mommy filter out the condescension? That might give you time to read at least a portion of what has been previously posted here, maybe adopt the vernacular and conventions in use rather than forcing us to adopt yours while your in the process of making it up?Chain of "sudo"? You've decided that "sudo" is a word? Is no one else getting annoyed? You actually got angusj to appoligize to YOU, though he clearly had nothing to appoligize for.

Uh, Georgie -- play with my nice, shiny keys while I talk to the big people.

(Seems like everyone else wants to avoid starting an argument, but being nice to Georgie Porgie is tacitly condoning and encouraging his arrogance. Oh, and I can't make heads nor tails of 3/4 of what he's posted -- is he passing it through Babblefish prior to posting? Really, I'm not completely sure he isn't just putting us all on. "Chain of *Sudo*"? Everyone knows it's called the "links of death." Der.)

I'm back Georgie. If anything I've said comes of a little strident -- what can you expect from a 6 year old?

[Roger Scriven]

George (and Nick70)

I have read and followed your Suduko “open chain” technique with interest. And managed to follow it through. I also followed the xy wings and this also allowed the puzzle in question to be solved.

I have a puzzle, which looks like it could be helped by the use of open chain but where to start and where to finish?
Puzzle is:

*4* *** 3**
79* *43 *6*
386 5*1 *4*

*1* 432 ***
**3 *5* 12*
*5* 1*6 *3*

5*9 **8 417
*2* 9*5 683
*** **4 259


Candidates for empty squares as follows:

(1,1)=12,(1,3)=125,(1,4)=(1,5)=268,(1,6)=(1,8)=79,(1,9)=158
(2,3)=125,(2,4)=28,(2,7)=58,(2,9)=158
(3,5)=(3,7)=79
(4,1)=689,(4,3)=78,(4,7)=5789,(4,8)=79,(4,9)=568
(5,1)=4689,(5,2)=67,(5,4)=78,(5,6)=79,(5,9)=468
(6,1)=2489,(6,3)=2478,(6,5)=(6,7)=789,(6,9)=48
(7,2)=36,(7,4)=236,(7,5)=26
(8,1)=14,(8,3)=147,(8,5)=17
(9,1)=168),(9,2)=367,(9,3)=178,(9,4)=367,(9,5)=167

With all those 79s I feel sure I should be able to make a logical decision to be able to proceed.
Can I safely say that as (4,8) which is 79 and part of a conjugate pair with (1,8) also79 then (4,3) which is 78 cannot be 7 as it cannot be allowed to influence the value of (4,8)????
Or have I to identify chains and work from there.
Any advice is welcome.
Roger

[tso]

Maybe I was unfair as I wasn't specific:

Guys

We're not all "guys", thank you very much.

Here is an example that got everyone stuck for a few weeks.

Who is "everyone"? "A few weeks?" What are you talking about? This is an easy one.

9XX/5XX/362
253/9XX/81X
6X1/2X3/95X

X69/X32/X85
1XX/6X8/X39
3XX/49X/X76

53X/XX4/698
89X/3XX/741
X1X/8X9/523

George sweetie, wouldn't you rather try to make sense of a diagram that looks like this? It's easier for us 6 year olds to make sense of:

Code: Select all

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


Applying the "OPEN CHAIN OF SUDO" technique, I am able to identify 2 open chains of sudo "7". Don't forget we are propogating along "7".

How could I forget? I don't know what your talking about. How many undefined terms can you put in a floramate snofflebit before it beclorinates from yal'nrk and cannot be parsed? It's probably me -- my memory isn't that great at 6.

These chains are:

Chain 1: (9,1)(4,1)(4,4)(7,4), these are all conjugate links and (9,1)(7,4) are the open ends which are also conjugates.

Chain 2: (9,1)(4,1)(4,4)(5,5), these are all conjugate links and (9,1)(5,5) are the open ends which are also conjugates.

Since "conjugates" means that one of them must be a true condidate of "7", it follows that other "7" cells that lies on the intersection of the conjugate links or open conjugate ends must be a false condidate of "7" and can be safely excluded.

From chain 1, it can be seen that (7,3) lies on the intersection of the chain ends (9,1) connected by a box and (7,4) connected by a row. Therefore, (7,3) must not be "7" because either (9,1) or (7,4) must be "7". It follows that (7,3) must be "2".

Likewise, (9,5) lies on the intersection of the chain ends (9,1) connected by a row and (5,5) connected by a cloumn. Therefore, (9,5) must not be "7" because either(9,1) or (5,5) must be "7". It follows that (9,5) must be "6".

Although one more open chain of sudo "7", can be identified, no other "7" cells can be eliminated. This chain is listed below for observation purposes:

(9,1)(4,1)(4,4)(1,6)(2,6)(2,9)(3,9), where all of these are conjugate links except for (4,4)and(1,6) which is a like link.

Don't forget, conjugate link must be unique on a row, a column or a box, whereas like link could be anywhere in the 9x9 grid.

This has been described half a dozen times or more in this forum -- though I had to read your post half a dozen times to realize this, as you've invented your own language and assume we know it. Honestly, I only know what you are trying to say because I KNOW what you are trying to show. "Propagating along "7"? Row 7? Candidate 7? False condidate (sic) of 7?

Setting aside my obnixious way of expressing this, you might want to use a diagram -- maybe call row 5 column 3 "r5c3 instead of the ambiguous (5,3) or (3,5). (If you click on QUOTE, you can examine the way diagrams are bracketed by [ c o d e ] and [ / c o d e ] for legibility.) One of many simpler solutions to this puzzle is:

A diagram is much easier for me to understand -- of course, us 6 year olds are easily distracted, so I've removed the extraneous information:

Code: Select all

 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
-------+-------+------
47 . . |17 . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
-------+-------+------
 . . . |17 . . | . . .
 . . . | . . . | . . .
47 . . | .67 . | . . .


Could anything be easier?

1) r4c1=4 => r9c1=7 => r9c5=6
2) r4c1=7 => r4c4=1 => r7c4=7 => r9c5=6
Therefore, r9c5=6, and the rest solves quickly.

This type of proof has been called "forcing chains" or "dual implication chains" or usefully discriptive titles that can be parsed from context and possibly an English dictionary. (Mine doesn't list "sudo".) It generally isn't written in all caps with quotes and theme music.

This specific pattern of 5 cells, which is a subset of all forcing chains which may have more cells and even more chains, has been recently dubbed "turbot fish" by Nick70 who described it in clear detail here.

To answer my own question, yes, something could be easier:

Code: Select all

 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
-------+-------+------
 . . . | . . . | . . .
 . . . | .57 . | . . .
 . . . | . . 15| . . .
-------+-------+------
 . . . | . . . | . . .
 . . . | . . 56| . . .
 . . . | .67 . | . . .


1)r9c5=6 => r8c6=5 => r6c6=1
1)r9c5=7 => r5c5=5 => r6c6=1
Therefore, r6c6=1 and the rest follows.

This is the simplest possible forcing chain. (It is not an example of an x-wing.)

Now tell me Georgie, honey, wasn't that a lot clearer to you than what you wrote?

A forcing chain is a chain of assumptions about the puzzle. Let's say R1C1 has possibilities 1,2 in some puzzle. Then you can make a chain of implications, ie something like this:

If R1C1=1 then that means R1C9=5 which means R9C9=3... and so on.

It is sometimes possible to find a chain that starts with R1C1=1 and ends with R1C1=2. Since this is impossible, you know that the original guess, R1C1=1, must be false, and it can be eliminated.

This technique can be elaborated, with the chains splitting off from each other, and so on. It gets horribly complicated and, IMHO, except at the simplest levels, is not a practical technique for human solving. It is effectively brute-force recursion.

The real interesting stuff, to me, in Sudoku algorithm research, is coming up with algorithms that are easy for humans to "execute" and take advantage of our skills in pattern recognition. Simple forcing chains is right on the edge of what I think is reasonable.

One approach I am currently working on is recasting some of the more complex algorithms in such a way that they play to human strengths and are reasonably executable; that's how I came up with Bowman Bingo (an extended Nishio) a few weeks back. I've got another in the works that I'll be announcing soon.

MadOverlord's description of "forcing chains" is somewhat inaccurate. No guesses are made, no assumptions are made. Further, he mixes opinion with definition. Any tactic can be complicated in one situation and simple in another. Some of the easiest tactics we take for granted might be beyond an individual's capabilities -- if say, you decided to solve without using pencil marks because the grid in the paper was very small an all you had was a pen -- the underlying concepts do not change from complex to easy and then to beyond human ability. They remain. Forcing chains is a more *general* description that includes many *specific* formations. Some of us would rather learn to cook rather than have to carry around a pile of recipes. The "forcing chains" philosophy is that it's more fun to *think* than it is to *recall", more fun to "invent" than it is to "look-up". I respect his opinion about Sudoku algorithm research and I support it and look forward to new findings. But remember, if someone were to find THE solution, the one tactic that could be used to solve ALL Sudoku's -- and if that tactic was simple enough so that once you knew the secret, you couldn't pretend you didn't -- this would not be a boon for solvers -- it would be the end of Sudoku altogether. Fortunately, this is (out on a limb) not possible. My opinion is there is a big difference between trying to solve an individual Sudoku and trying to solve Sudoku in general. Both are plenty interesting. Of *course* brute force is riduculous to use when trying to solve the general case, but if you can use brute force in your head on the bus with a pen -- you are the MASTER, not the cheater! I bow to you. If you can -- as I do -- find by examination, forcing chains or proofs by contradiction that are 4, 6, 8, 10 cells long, this in no way negates the search for general solutions to Sudoku. General case knowlege improves specific case solving but tells us nothing about the specific case in front of me. (Men are taller than women -- my three sisters are all taller than my brother.)

So, the forcing chain technique is just another form of bifurcation, because it involves guessing a number to propogate and return when a contradiction is identified.

I am not into bifurcation at all. I like to solve all my puzzles by logic which consider bolean, not number branching.

A common myth among 8 year olds -- it is ridiculous on two levels. First, forcing chains are NOT proof by contradiction. There IS no contradiction identified in using a forcing chain. (This in no way disparages Proof by Contradiction, and equally useful tactic.)

Take a look at this diagram. There are two proofs, one above and one below the line of equal signs, both proving that the "34" cells must be "4":

Code: Select all

12 . . |23 .13 | . .34
 . . . | . . . | . . .
 . . . | . . . | . . . 
=======+=======+======
12 . . |13 . . | . . .
 . . . | . . . | . . .
23 . . |34 . . | . . .
-------+-------+------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .


To call one bifurcation and the other logic -- is illogical. We you disagree, please point to or construct a strict general definition that descrimates between these structures. In the lower case, I am no more or less "guessing" what r4c1 is or "bifurcating" it than I am in the upper case "guessing" and "bifurcating" that r1c146 is 1, 2, 3 or 2, 3, 1.

(Also, if you wanted to, you could start your examination by look at the two "34" cells and "guess" they were 4's. In both cases, it would lead to contradiction. If we must toss out PBC as being beneath us, simply renaming the upper structure "triples" doesn't change anything -- it's the same four cells, the same logic from a different vantage point. I can turn ALL proofs in to PBC -- and vice versa.)

If you agree that those two trivial structures are logical, then look below:

Code: Select all

12 . 23|34 .56 |16 .67
 . . . | . . . | . . .
 . . . | . . . | . . . 
=======+=======+======
12 . . | . . . | . . .
 . .13 | . .46 |34 . .
46 . . |67 . . | . . .
-------+-------+------
34 . . | . . . | . . .
 . . . | . . . | . . .
23 . . | . . . | . . .


Again, both above and below the line, on must use the information from ALL the cells, taken together, to prove that the "67" cells must each be 7. There is no guessing, no trial and error, no looking into the future. Either you can recognize the patterns in your head, or you can't. If you can, you've proved it.

The fact that I might coin the word "quints" for the pattern above the line or "quinty fish" for the *exact* configuration below the line, does not magically change they underlying logic. It just changes what the solver does from *thinking* to *recalling*. Computers MUST recall as they cannot think -- yet. It may vary well be more interesting to be able to apply dozens of known tactics and avoid looking free-form for various implications that might never be seen twice -- but it is doing the *latter* that will more likely lead to the discovery of more of the *former*.

[tso]

George (and Nick70)

I have read and followed your Suduko “open chain” technique with interest. And managed to follow it through. I also followed the xy wings and this also allowed the puzzle in question to be solved.

You'll be better of reading Angusj, Nick70 and other longtime posters here than the posts by newbies.

I have a puzzle, which looks like it could be helped by the use of open chain but where to start and where to finish?

With all those 79s I feel sure I should be able to make a logical decision to be able to proceed.
Can I safely say that as (4,8) which is 79 and part of a conjugate pair with (1,8) also79 then (4,3) which is 78 cannot be 7 as it cannot be allowed to influence the value of (4,8)????

No!

In forcing chains, you're looking for a cell for which ALL possibilites lead to the SAME result in any OTHER cell. In the example you gave, there's nothing obvious about the r14c8 pair that tell you anything about r4c3 -- yet. I'm not saying there *isn't* a forcing chain -- in fact:

I found this longish forcing chain, which uses your "79s":

Code: Select all

1) r8c5=1 => r8c1=4 => r8c3=7 => r4c3=8
2) r8c5=7 => r3c5=9 => r3c7=7 => r1c8=9 => r4c8=7 => r4c3=8
Therefore  r4c3=8


However, this doesn't move the puzzle forward very far. You could probably keep finding forcing chains and use no other tactic and solve the puzzle the rest of the way -- but it looks like that would be the hard way around.

One *generally*, but not always, puts off looking for forcing chains when all other methods have been exhausted. Unfortunately, this means that for the vast majority of even the hardest puzzles (including 100% of Pappocom's), one will never even need it. (Puzzle's that require even the simplest forcing chains are usually called "invalid" by Pappocom's software.) Finding a forcing chain gets easier to find the more cells you have that have only 2 candidates and the less there is of anything else.

The puzzle you've posted, reformated for my tiny little eyes:

Code: Select all

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


... requires nothing beyond an X-wing.

First, you can put a 2 in r3c9 as no other digit can go there without having two in a row, column or box.

Look at columns 2 and 4. Each has exactly two places for a 7, both of which are in the same two rows. This is an x-wing -- this eliminates all candidate 7's from rows 5 and 9 -- which in turn makes r5c6=9 -- which then flips all the 79s you've been eyeing.

After this there are a couple of easy deductions and then the dominos fall.

[George]

Post cancelled.

[Roger Scriven]

For tso
Thank you. There was a 2 in c3r9 I missed it in error and I also failed to see the x-wing in 7s.