New technique: Open chain of Sudo

Advanced methods and approaches for solving Sudoku puzzles

New technique: Open chain of Sudo

Postby George » Wed Jul 20, 2005 2:16 pm

Guys

My experience with sudoku is only 2 weeks old. Here is an example of this technique.

The candidates of the unknown cells are:

Code: Select all
 *-----------------------------------------------------------*
 | 9     478   478   | 5     148   17    | 3     6     2     |
 | 2     5     3     | 9     46    67    | 8     1     47    |
 | 6     478   1     | 2     48    3     | 9     5     47    |
 |-------------------+-------------------+-------------------|
 | 47    6     9     | 17    3     2     | 14    8     5     |
 | 1     247   2457  | 6     57    8     | 24    3     9     |
 | 3     28    258   | 4     9     15    | 12    7     6     |
 |-------------------+-------------------+-------------------|
 | 5     3     27    | 17    127   4     | 6     9     8     |
 | 8     9     26    | 3     256   56    | 7     4     1     |
 | 47    1     467   | 8     67    9     | 5     2     3     |
 *-----------------------------------------------------------*

Applying this technique, I am able to identify 2 open chains of sudo "7". Sudo "7" means that we are propagating with the candidate "7" along the chain links.

Chain 1: (9,1)(4,1)(4,4)(7,4), these are all conjugate links, ie.
when (9,1)=7, (4,1)<>7, (4,4)=7 and (7,4)<>7, or
when (9,1)<>7, (4,1)=7, (4,4)<>7 and (7,4)=7
Either way, the open ends of the chain (9,1) & (7,4) has a conjugate relationship; therefore it is also a conjugate link.

Chain 2: (9,1)(4,1)(4,4)(5,5), these are all conjugate links, ie.
when (9,1)=7, (4,1)<>7, (4,4)=7, (5,5)<>7, or
when (9,1)<>7, (4,1)=7, (4,4)<>7, (5,5)=7
Either way, the open ends of the chain (9,1) & (4,5) has a conjugate relationship; therefore it is also a conjugate link.

In the conjugate link, one of the 2 cells must hold a "7". Any other possibilities of "7" that lie on the intersection (connected by a row, column or box) of this conjugate link must be false and can be safely excluded.

With chain 1, (7,3) lies on the intersection of the chain link (9,1)(7,4). 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".

With chain 2, (9,5) lies on the intersection of the chain link (9,1)(5,5). 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".

From here, I would like to introduce the idea of like link. Contrary to conjugate link, the 2 cells in a like link has a like relationship where both cells must be x or both cells must not be x.

In this grid, one more open chain of sudo "7", can be identified with a like link. Although no elimination of "7" can be resulted from this chain, it is listed below for observation purposes:

Chain 3: (9,1)(4,1)(4,4)(1,6)(2,6)(2,9)(3,9), where all of links are conjugate links except for (4,4)(1,6) which is a like link, ie.
when (9,1)=7, (4,1)<>7, (4,4)=7, (1,6)=7, (2,6)<>7, (2,9)=7, (3,9)<>7, or
when (9,1)<>7, (4,1)=7, (4,4)<>7, (1,6)<>7, (2,6)=7, (2,9)<>7, (3,9)=7.
Either way, the open ends of the chain (9,1)(3,9) has a conjugate relationship; therefore it is also a conjugate link. From here, any possibilities of "7" that lie on the intersection of this conjugate link must be a false and can be safely excluded.

Without this like link, it is impossible to form the conjugate link (9,1)(2,9) at the open ends of the chain. Like link is not easy to spot. However, the location of its 2 cells can be anywhere in the 9x9 grid.

Cheers
George
Last edited by George on Fri Dec 09, 2005 2:31 am, edited 1 time in total.
George
 
Posts: 20
Joined: 20 July 2005

Postby Nick70 » Wed Jul 20, 2005 3:27 pm

In the example there is a Turbot Fish in the 7's in (4,4) (4,1) (9,1) (9,5) (5,5).

There is also a xy-wing (8,6) <-- (9,5) --> (5,5) that allows to place a number in (6,6).
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby George » Thu Jul 21, 2005 12:22 am

Nick

Thank you for your response.

The cells that you listed on Turbot Fish are same as my chain 2. Can you tell me in which cell and what number can be eliminated as a result of this Turbot Fish.

Can you please explain the principle of the XY-Wing or point me to the right direction as I am an eight year old.

Cheers
George
George
 
Posts: 20
Joined: 20 July 2005

Postby Wolfgang » Thu Jul 21, 2005 10:09 am

Nick70 wrote:In the example there is a Turbot Fish in the 7's in (4,4) (4,1) (9,1) (9,5) (5,5).

In my opinion, it is completely unnecessary to look for turbot fishs. Every sample you can solve with it, can be done just in the way George did, by applying simple 4-nodes-chains. You can check that, if you go through the samples in the turbot fish link above. The last sample is enough for all of them (and it is the same as Angus' sample for simple chains):
1. A-B and C-D => remove E, number must be in D
2. B-C and A-E => remove D, number must be in C
3. A-B and C-D => remove E
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby Wolfgang » Thu Jul 21, 2005 10:47 am

Wolfgang wrote:(and it is the same as Angus' sample for simple chains)

Not really - in Angus' sample the second side B-C is conjugated, but it also my be a "weak" connection, what makes it a lot more general.
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby Nick70 » Thu Jul 21, 2005 11:36 am

Wolfgang wrote:In my opinion, it is completely unnecessary to look for turbot fishs. Every sample you can solve with it, can be done just in the way George did, by applying simple 4-nodes-chains.


Yes, that's right.
X-Wing is unnecessary as well, since it can be solved in the same way.

It is a common pattern however, easy to visualize, and with its 5 cells it fills the gap between X-Wing (4 cells) and Swordfish (6 to 9 cells).

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.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby Wolfgang » Thu Jul 21, 2005 12:15 pm

Nick70"][quote="Wolfgang wrote: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) ?
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby George » Thu Jul 21, 2005 1:27 pm

Nick70 wrote: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.


Guys

What is the forcing chain that you are talking about and how to apply it.

Regards
George
George
 
Posts: 20
Joined: 20 July 2005

Postby MadOverlord » Thu Jul 21, 2005 2:04 pm

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
 
Posts: 81
Joined: 10 June 2005

Postby George » Thu Jul 21, 2005 2:25 pm

Nick70 wrote:In the example there is a Turbot Fish in the 7's in (4,4) (4,1) (9,1) (9,5) (5,5).

Nick, I have done some study on Turbot fish and found that one of the Turbot fishes is just another example of "open chain of sudo".

Wolfgang, my chain looks different to the Turbot fish chain mentioned by Nick. It was (9,1)(4,1)(4,4)(5,5) and, I have eliminated a "7" from (9,5) So, the open chain looks more like Angus' "solve by colour" technique.

By the way, the "open chain of sudo" technique looks for not only conjugate links, but also like links. Each like link consists of 2 cells which will both have the same candidate or both NOT have the same candidate. This allows the chain to propagate further along the grid.

The "Solve by Colour" technique shared by Angus considers conjugate links only, and therefore is a subset of the "Open chain of sudo" where like lins are also considered.

Cheers
George
Last edited by George on Fri Dec 09, 2005 2:52 am, edited 1 time in total.
George
 
Posts: 20
Joined: 20 July 2005

Postby George » Thu Jul 21, 2005 2:33 pm

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


Thank you for your clarification.:D

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.

I like to learn more about the technique that you have developed, so could you please point me to the right direction.

Cheers
George
George
 
Posts: 20
Joined: 20 July 2005

Postby Wolfgang » Thu Jul 21, 2005 2:53 pm

George wrote:Wolfgang, ... So, the open chain is definitely not a turbot fish. It is more an extension of Angus' "solve by colour".

I dont know, if Nick70 defines it as a kind of turbot fish. What i sayd is that the simple chain A-B-C-D with a weak or like link B-C solves all the turbot fishes, your sample, xwing and Angus' chain sample (but not a swordfish with more than 6 nodes or other forced chain situations like xy wing). So please tell me, what more OPEN CHAIN OF SUDO can solve, if it does.
Of course all those techniques above have there sense, simply because you are faster with them, but what i'm really interested are (easy) new techniques, which help you solve more puzzles.
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby angusj » Thu Jul 21, 2005 2:54 pm

George,

Firstly, just to clarify - I'm not the person who 'discovered' colours, I simply documented it in my sudoku hints page. If I had to say who was first to use it in sudoku solving it was probably Andrew McK who posted in the Programmer's forum. Andrew probably got the idea from somone else who got the idea from someone else ...

As to 'your' Open Chain of Sudo - it seems to me to be simply another way of describing conjugate relationships on which 'colours', 'forcing chains' etc are built. I'm getting the impression that you're trying to convince others that your method is something new and/or more powerful. I really don't believe that either is the case. I don't want to take the wind out of your sails, but just encourage you to ease up a bit in your enthusiasm.

If you really are eight (as you claimed somewhere else) then you're obviously extremely gifted and articulate, but just remember just about all great ideas are just extensions of someone else's great ideas.
angusj
 
Posts: 306
Joined: 12 June 2005

Postby George » Thu Jul 21, 2005 3:18 pm

angusj wrote:I'm getting the impression that you're trying to convince others that your method is something new and/or more powerful. I really don't believe that either is the case. I don't want to take the wind out of your sails, but just encourage you to ease up a bit in your enthusiasm.


Angus

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

Firstly, let me clarify that I developed my open chain of sudo through inspiration by your "X-wing, Swordfish,Colours" and Bernard's "Suck and Blow". It is not a totally new invention, but rather a generalisation of techniques that I have learnt from other kind people who shared these ideas in the first place.

You must have been upset by me saying that the "Colour" was a subset of the "open chain od sudo". I am merely saying that because I have extended the idea to cover "like links" as well as "conjugate links". Can you see some merits in this as it help the chain to propogate further, thus more elimination can be acheived.

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

Cheer up
George
Last edited by George on Fri Dec 09, 2005 2:53 am, edited 1 time in total.
George
 
Posts: 20
Joined: 20 July 2005

Postby George » Thu Jul 21, 2005 4:33 pm

Wolfgang wrote:So please tell me, what more 'Open chain of Sudo' can solve, if it does.

Wolfgang, I am a newcomer of this forum and still have a lot to learn from what people have developed and shared with others here. From my reply to Angus, I think you would have understood that the 'open chain of sudo' was extended from Colour but added with like links. It is not intended to improve speed to solve puzzles, but rather try to introduce or share another technique which will help to solve puzzles by pure logic.

I overheard the discussion between you and Nick about Turbot fish, XY-wing and forcing chain. All these terms are new to me, so I was eager to find out what they are. Now, I know that the conjugate links in the 'Open chain of Sudo' is just same as Angus' 'Solve by colours'.

As I said, in 'Open chain of Sudo' , I introduced like links into the chain to make it propagate further such that more candidates can be eliminated. Is this a new feature, or something that already exist in the forum? Please let me know if this is so.

Cheers
George
Last edited by George on Fri Dec 09, 2005 2:59 am, edited 1 time in total.
George
 
Posts: 20
Joined: 20 July 2005

Next

Return to Advanced solving techniques