Your methods of solving an "extreme" sudoku puzzle

Advanced methods and approaches for solving Sudoku puzzles

Postby Max Beran » Fri Oct 05, 2007 9:28 pm

I thought you were looking for recipes on how to apply techniques, in particular how to recognize the patterns that go under these glorious inventive names that the theoreticians coin for their methods. I am often reminded of the proofs by induction that we were taught at school where we were given a formula (eg sum of a series) and told to prove it by induction. What I could not get out my head was what a useless method this is as it tells you nothing about how the inventor of the formula came up with it in the fist place. Likewise, in Sudoku, we are presented with grids with nodes highlighted and links drawn in, and you are invited to think, what an amazing method, but you haven't got a clue how they came up with that particular example from the background of millions of possible links and nodes.

Back to techniques and when to use them.

One very elementary issue which is encountered right at the beginning of the puzzle is what candidates to mark up. My rule is to be extremely parsimonious and only to mark up those candidates in cells where there is the potential for an inference such as it would exclude that candidate elsewhere. I am sure that means I have less work to do in the long run, compared with filling in all the candidates from the start. Only after I've exhausted the possibilities that way do I fill in the rest of the candidates (and perhaps find a few more triples etc).

But where to go next?

I sense that you have arranged your procedures in order of complexity, but is it really the order you apply them in practice? Personally, I haven't got into uniqueness methods or any of the "almosts" but have the impression that they are unlikely to be productive at a middle stage, ie with most unsolved cells containg multiple candidates. At least that is my experience with the type of puzzle I like doing, Mepham's weekly extreme and Ruuds nightmare.

Also, perhaps it hardly needs saying, but your group A techniques are not limited to the start of the puzzle; I'm keeping my eyes open for them at every stage, whenever I make an exclusion by another method. And of course, they are always the main tool at the very end of the solution.

I was surprised at you leaving empty rectangles to a stage when you had a lot of bivalues. My own experience is that they are productive quite early on; maybe not providing a killer exclusion, but at least leading to a small reduction in the number of candidates and perhaps creating a new locked row or column or a new bilocation that will be useful for loopfinding.

After the initial pass through and completing the full candidated grid, I use a filter to find x-wings, swordfish etc but not with much hope as there are too many cells with most candidates.

This means that with the puzzles I like doing, I almost always need to use nice loops to reduce the number of candidates to a sensible level where the "middle ranking" techniques like xy-chains can take over. So I reckon in practice, you can almost reverse the order of your groups B and C - first the advanced methods, then the middle ranking ones.

By the way, I think the circumstance where a swordfish becomes expressible in the form of a nice loop is where the candidates appear as bilocals in each of the three rows (or columns).

I use my patent method using a network diagram here for identifying simple loops.I've never been successful in finding a grouped nice loop that did anything. Have you? What is your technique?

Also, what use are AIC's? As far as I can see they are not relevant to the manual solver as it seems (to me) to be a theoretical concept that applies at the level of chains of candidates. But, with nice loops, our propagation rules apply at the cell level. So we can link two strongs (of a different label) through a bilocation, and two weak's (of a different label) through a bivalue. Also we can draw an inference from the discontinuity all of which are in violation of alternating inferences between strong and weak. I would be glad of an explanation (or directed to where I can get an explanation) that would demonstrate the relevance to the manual solver focused on cell patterns.
Max Beran
 
Posts: 57
Joined: 17 August 2005

Postby andre43 » Sat Oct 06, 2007 9:16 am

Max Beran, I read your message with great interest! At first, I have to say that what I’m interested for in this thread, is not to discuss the theory of sudoku with mathematical terms (unfortunately, I’m not a “mathematic” mind!), but to find the most effective way to solve a sudoku puzzle in the real world conditions!!!
Then, some points on your remarks:
Personally, I haven't got into uniqueness methods or any of the "almosts" but have the impression that they are unlikely to be productive at a middle stage, ie with most unsolved cells containg multiple candidates.

You are right, if the cells contain multiple (that is, over 4) candidates. Otherwise, the unique rectangles very often contribute to the solving of the puzzle.I am stressing again the use of the Hidden Unique Rectangles, an excellent method using the “almost” UR, by Andrew Stuart. It’s not a theoretical theme-you will use it often!
Also, perhaps it hardly needs saying, but your group A techniques are not limited to the start of the puzzle;

You are absolutely right! I simply start the solving with these techniques, because, as you know, they provide nearly always a quite enough number of eliminations, which will permit us to go further with more…hopes.
I was surprised at you leaving empty rectangles to a stage when you had a lot of bivalues. My own experience is that they are productive quite early on;

Of course! I don’t think that I leave them, as you say, in a stage with many bivalues! At the B stage we are still in the middle of the puzzle. The only way for the ER to work is to have an adequate number of strong links in the grid-not to have many bivalue cells. I simply say that I apply the ER once again in a later stage of the puzzle, when we’ll have more strong links, that is, more chances to have further eliminations.
This means that with the puzzles I like doing, I almost always need to use nice loops to reduce the number of candidates to a sensible level where the "middle ranking" techniques like xy-chains can take over. So I reckon in practice, you can almost reverse the order of your groups B and C - first the advanced methods, then the middle ranking ones.

Very interesting! I follow the order of the groups B and then C simply because nice loops are sometimes very time-consuming! Of course, if the grid is even then full of candidates, I don’t go to the trouble of trying to find xy-chains and I go directly to nice loops…But, the truth is that all these methods are not applying just once-on the contrary, accordingly to the conditions and the stage of solving we have reached, we may bring them back again and again, up to the end.
Also, what use are AIC's? As far as I can see they are not relevant to the manual solver as it seems (to me) to be a theoretical concept that applies at the level of chains of candidates

No!! The AICs (known in Andrew Stuart’s Solver as Rule 2) is one of the most helpful and valuable methods ever invented for sudoku!! This method by Myth Jellies (see his thread on the topic) brings me every time I solve an extreme sudoku, among 3-7 eliminations!! I dare to say that AICs bring on as much eliminations to an extreme puzzle as do the nice loops (at least this happen to me)!!
I use my patent method using a network diagram here for identifying simple loops.I've never been successful in finding a grouped nice loop that did anything. Have you? What is your technique?

I haven’t read yet your article. It seems to me very interesting. Wait for my reaction, please. As for the grouped NL, they are very often functional in a nice loop chain, but I haven’t any recipe to find them. Read please some older threads about the topic in this forum, by Jeff and others-they will help you!
I’ll come back soon!!Regards.
andre43
 
Posts: 16
Joined: 03 September 2006

Postby ronk » Sat Oct 06, 2007 10:40 am

andre43 wrote:I dare to say that AICs bring on as much eliminations to an extreme puzzle as do the nice loops (at least this happen to me)!!

I see no fundamental difference between Nice Loops (NLs) and Alternating-Inference-Chains (AICs). What do you see as differences?

I'm not referring to the differences in notation here, that difference is obvious. I'm referring to the basic properties of the chains/loops ... and maybe to the methods a manual solver uses to find them.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Max Beran » Sat Oct 06, 2007 11:41 am

Well ronk, from my perspective as a died-in-the-wool nice-looper the fact that you can, for example, propagate across a bivalue cell with a weak link in and a weak link out means that the links are not alternating (which is what the "A" in AIC stands for). There are other examples where links do not alternate between strong and weak.

Okay, you can interject a within-cell strong link in the bivalue case just mentioned so that a theory wonk can represent it as an alternating chain at the candidate level. But how does this help the manual solver who is working with links between cells, not candidates (at least for the pattern methods I'm accustomed to)? Are there techniques where it is essential to think about within-cell propagation and it is not possible to express the technique in terms of rules that operate at cell link level (like Jeff's propagation and inference rules for nice loops)?
Max Beran
 
Posts: 57
Joined: 17 August 2005

Postby ronk » Sat Oct 06, 2007 1:02 pm

Max Beran wrote:Okay, you can interject a within-cell strong link in the bivalue case just mentioned so that a theory wonk can represent it as an alternating chain at the candidate level.

Exactly. Inference streams don't propagate very far without alternating strong and weak inferences. The strong inferences of bivalued cells are merely implicit in NL notation and explicit in AIC notation.

Max Beran wrote:But how does this help the manual solver who is working with links between cells, not candidates (at least for the pattern methods I'm accustomed to)?

How is recognition of implicit strong inferences a hindrance?

Max Beran wrote:Are there techniques where it is essential to think about within-cell propagation and it is not possible to express the technique in terms of rules that operate at cell link level (like Jeff's propagation and inference rules for nice loops)?

I think that is essentially my question to andre43.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Max Beran » Sat Oct 06, 2007 1:44 pm

How is recognition of implicit strong inferences a hindrance?


Two ways:
1. Carrying around superfluous information in a finite brain is an obstacle
2. Giving the impression that there is a distinct solving procedure called AIC is confusing.

I'm not saying AIC isn't an insightful unifying principle that underpins many methods but then so is the OR operator and I doubt many of us think explicitly about that when we are sitting in our armchair solving Sudokus.
Max Beran
 
Posts: 57
Joined: 17 August 2005

Postby champagne » Sat Oct 06, 2007 2:10 pm

andre43 wrote

I’d like e.g. to learn more about the combination of two ALS in creating a nice loop…Is there any volunteer??!


Another example, may be more focused on your requirements, but again with three ALS.

The nice loop turns aroung the external frontier of the puzzle, crossing the following ALS

- r1c2 r1c3 r2c1 r3c1
- r1c7 r1c8 r2c9 r3c9
- r7c1 r8c r9c2 r9c3

and using empty rectangle r9c7 r9c8 r8c9 r7c9.

Code: Select all
6     289   279   |2789  4     15a789 |125   129    3     
489   1     2349  |23689 2568  689    |246   7      569   
479   2349  5     |23679 1267  1679   |8     12469  169   
-----------------------------------------------------------
14789 4689  14679 |5     678   2      |13467 134689 16789 
3     568   167   |4678  9     4678   |1567  168    2     
45789 24689 24679 |1     678   3      |467   4689   56789
----------------------------------------------------------
145   346   8     |2467  12567 1467   |9     23     167   
149   7     13469 |24689 1268  14689  |23    5      168   
2     569   169   |6789  3     156789 |167   168    4     


and the nice loop

6(r9c7r9c8)/6(r9c2r9c3)_6(r7c2r8c3)/4(r7c2r8c3)|*r7c2r8c3 _4(r7c1r8c1)/4(r2c1r3c1)_4(r2c3r3c2)/2(r2c3r3c2)|*r2c3r3c2 _2(r1c2r1c3)/2(r1c7r1c8)_2(r2c7r3c8)/6(r2c7r3c8)|*r2c7r3c8 _6(r2c9r3c9)/6(r7c9r8c9)


This is my best start for that puzzle published about two years ago on Gould forum.
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby andre43 » Sat Oct 06, 2007 3:35 pm

Of course Ronk, the concept of alternation inheres in the world of X-Cycles. But, I think that AICs (as I understand them) have two extra features-though yes, you may say that there is not a fundamental difference between nice loops and AICs! Sure, these features could be the rules 4 & 5 of the “discontinuous” nice loops, continuing their well known three rules!! The main rule of AIC, as we know it all, permits us to leave a cycle unfinished, stopping at a different cell which, however, must be at the same row, column or box with the starting cell (and which must has as a final digit a different one of that of the point of departure), and then we may proceed to a possible elimination. The only need is to start and end with a strong link. Note that, this rule partly overlaps the 3rd rule of the “discontinuous” nice loops, that is, the rule which refers to the two links with different inference. Please, correct me if I’m wrong somewhere-but, anyway, I find this subtle method awfully helpful in the precess of solving my extreme puzzles.. As for the other rule of AICs, is simply a kind of development of xy-chains. It’s again a method of an unfinished cycle, but this time there is no need for the starting and ending nodes to “see” each other-this time the basic condition is only to have both the same digit. So, any other digit both of them can see, may be eliminate. I can’t wait, ronk, to hear your reaction…Thanks.
andre43
 
Posts: 16
Joined: 03 September 2006

Postby ronk » Sat Oct 06, 2007 4:43 pm

champagne wrote:The nice loop turns aroung the external frontier of the puzzle, crossing the following ALS

- r1c2 r1c3 r2c1 r3c1
- r1c7 r1c8 r2c9 r3c9
- r7c1 r8c r9c2 r9c3

and using empty rectangle r9c7 r9c8 r8c9 r7c9.
[...]
and the nice loop

6(r9c7r9c8)/6(r9c2r9c3)_6(r7c2r8c3)/4(r7c2r8c3)|*r7c2r8c3 _4(r7c1r8c1)/4(r2c1r3c1)_4(r2c3r3c2)/2(r2c3r3c2)|*r2c3r3c2 _2(r1c2r1c3)/2(r1c7r1c8)_2(r2c7r3c8)/6(r2c7r3c8)|*r2c7r3c8 _6(r2c9r3c9)/6(r7c9r8c9)

champagne, that is a most interesting continuous loop ... which yields 13 eliminations. Since few here are familiar with your notation:

r9c78 -6- (ALS:r9c23 =6|159|4= r78c1) -4- (ALS:r23c1 =4|789|2= r1c23) -2- (ALS:r1c78 =2|159|6= r23c9) -6- r78c9 =6= loop

... implies r9c46<>6, r8c3<>19, r46c1<>4, r2c3<>9, r3c2<>9, r1c4<>2 r3c8<>19 and r46c9<>6

Due to the continuous loop, weak links become conjugate links and almost-locked-sets become locked. The "=6|159|4=" notation denotes digits 1, 5, and 9 are the digits locked into the set.

BTW the convention on the Players' Forum is to use nice loop notation when using the nice loop term.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby champagne » Sat Oct 06, 2007 7:34 pm

Ronk wrote

champagne, that is a most interesting continuous loop ... which yields 13 eliminations.


After having posted the previous example, I thought it could not be considered as relevant.

That’s why I posted that one which can be considered as a “school case”. As you noticed, it yields 13 eliminations. Moreover, it’s a very nice move.

But I have a problem with that example.

That puzzle was in the first lot I used to test my “step two”.

I have been highly impressed by that nice loop. In fact, most of the nice loops I produced later on where similar to the previous one I posted, going directly thru the “almost cell” complementary to the ALS without using the ALS. Reversely, although Ronk is using a kind of shortcut similar to W-link of Keith, use of ALS implies use of the complementary “Almost cell” if you present it thru a standard AIC.


For sure the logic I am using is much in favour of “Almost cells” but I think it’s a tool having better potential than ALS.

So when Ronk writes

BTW the convention on the Players' Forum is to use nice loop notation when using the nice loop


I could say: As long as it does not hide the logic used yes (by the way, where are these conventions). This is the way I am moving from the beginning.
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby sirdave » Sat Oct 06, 2007 8:07 pm

andre43 wrote:As an afterword, permit me please to express a complaint: although today we have many sources of nearly all techniques of sudoku, I find that there is a poor coverage of the theme of ALS Chains! There is a tutorial by SirDave in www.sudoku.org.uk -but it isn’t enough…I’d like e.g. to learn more about the combination of two ALS in creating a nice loop…Is there any volunteer??!


I'm glad you happened on my tutorial and are using the term, ALS Chains. Here is a more direct link to the tutorial:
http://www.sudoku.org.uk/discus/messages/29/4448.html?1185670798

In response to 'but it isn't enough', I would like to clarify the fact that it is about as complete a tutorial on the subject of ALS Chains from the point of view of pattern-solving as one will find anywhere; it was never intended to address the use of the ALS in chains. However, IMO, the place to start understanding ALS Chains is in pattern-solving. Once one has that down, the use in nice loops or AICs becomes almost second-nature.
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby sirdave » Sat Oct 06, 2007 8:17 pm

Max Beran wrote:Well ronk, from my perspective as a died-in-the-wool nice-looper the fact that you can, for example, propagate across a bivalue cell with a weak link in and a weak link out means that the links are not alternating (which is what the "A" in AIC stands for). There are other examples where links do not alternate between strong and weak.


My guess is that most people choose between nice loops and AICs based on which they learned first and which fits most with the individual's concept of solving. No one has ever proven that one method is better than the other. One of my gripes with nice loops is that the rules you have to follow are not intuitive- you follow them because you know them and thus, they are prone to error. AICs, on the other hand, stick to a relatively simple alternating inference pattern.
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby re'born » Sat Oct 06, 2007 9:26 pm

sirdave wrote:One of my gripes with nice loops is that the rules you have to follow are not intuitive- you follow them because you know them and thus, they are prone to error. AICs, on the other hand, stick to a relatively simple alternating inference pattern.

Ironically, I use nice loops (hopefully correctly) and I've never read the rules.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby sirdave » Sat Oct 06, 2007 10:29 pm

re'born wrote:
sirdave wrote:One of my gripes with nice loops is that the rules you have to follow are not intuitive- you follow them because you know them and thus, they are prone to error. AICs, on the other hand, stick to a relatively simple alternating inference pattern.

Ironically, I use nice loops (hopefully correctly) and I've never read the rules.


That's because you are one of the lucky few whose parents taught you how to use them before you could even walk.:)
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby Myth Jellies » Sat Oct 13, 2007 6:44 pm

Max Beran wrote:
How is recognition of implicit strong inferences a hindrance?


Two ways:
1. Carrying around superfluous information in a finite brain is an obstacle
2. Giving the impression that there is a distinct solving procedure called AIC is confusing.

I'm not saying AIC isn't an insightful unifying principle that underpins many methods but then so is the OR operator and I doubt many of us think explicitly about that when we are sitting in our armchair solving Sudokus.


The thing is, Max, you are also carrying around superfluous information. All of the special rules that you have to worry about regarding connections to bivalue cells versus connections to multivalue cells are superfluous from an AIC standpoint. From an AIC standpoint, all your link labels and rules regarding them and all of your various loop classifications and differing deductions based upon them are superfluous. So the question really amounts to whether you wish to remember all of the different rules for assembling Nice Loops, or would you rather remember the different ways that you can form strong and weak links for AICs? If you are going to find your deductions via noting loops in b/b-plots then the nice loop rules are a good choice. If you are ever going to find deductions via some other methods (3d-multicoloring, molecular method, transport, straight-up pattern recognition) then it's been my experience that the AIC rules tend to be more efficient.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Previous

Return to Advanced solving techniques