Identical Pair Forcing Pattern

Advanced methods and approaches for solving Sudoku puzzles

Postby denis_berthier » Sun Sep 07, 2008 1:40 pm

Myth,

That's exactly why I didn't want to speak of implementation: because of the confusion it may generate between the two levels - sometimes with obvious bad intentions.
An xy chain is an xy-chain, fullstop.
In my implementation of SudoRulles, for which I want the shorter chains, I choose the shorter ones, fullstop.
A player chooses the eliminations he likes, fullstop
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby ronk » Sun Sep 07, 2008 2:12 pm

Denis, writing sentences that end in the word "fullstop" is much like waving a red flag in a bull ring ... or holding up a lightning rod while standing on a mountain top.:idea:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Mon Sep 08, 2008 1:34 am

Denis,

I fail to see how drawing a logical conclusion from your statements involves "bad intentions". My commentary did not use any judgement phrasing that you had not already used yourself, so surely you could not object to that.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby denis_berthier » Mon Sep 08, 2008 1:51 am

Myth Jellies wrote:Denis,

I fail to see how drawing a logical conclusion from your statements involves "bad intentions". My commentary did not use any judgement phrasing that you had not already used yourself, so surely you could not object to that.


Apologies if the intentions weren't bad. But, by confusing the two levels, the interpretation was.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Mon Sep 08, 2008 2:19 am

This is very far from the initial topic of this thread, but as discussion as deviated on this, let me clarify things quickly.

In my approach, resolution rules, such as rules for triplets, xy-chains, nrczt-chains, ..., are defined at a purely logical level, independent of any implementation and of the various strategies according to which they can be used.

A resolution theory is a fixed set of resolution rules. All the theories I consider have the property that if they contain chains of a certain type and of length n then they contain all the chains of the same type and of smaller length. (This corresponds to the idea that if a player accepts xy-chains of length 7 he would be really stupid to refuse xy-chains of length 4 or 5).

From a pure logic POV, there can be no priority between the different rules in a resolution theory.
But, when a theory T has the confluence property (which all my theories have), then one can superimpose on the rules in T various strategies (defined by various sets of priorities on the rules). With different strategies, the resolution paths for a given puzzle will be different, but the final results will be the same.

Any computer based solver has to be based on some pre-defined strategy. The default strategy of SudoRules chooses a simplest first (i.e. shortest chains first) strategy. In addition to solving puzzles, this allows to compute their NRCZT rating (for definitions and discussions of this, see the "rating rules/puzzles" thread). But many different strategies can easily be defined by changing the priorities of the rules.

A real player is likely to choose a more oportunistic strategy and use any chains he finds without checking that there are shorter ones.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Myth Jellies » Mon Sep 08, 2008 11:22 pm

Both cases (potentially degenerate patterns vs. non-degenerate patterns) result in confluence, so that is not a discriminant. I assume you bring it up to show that one could search for non-degenerate patterns in any order. But the resolution rules use the patterns, and in order to ensure the non-degenerate pattern of length N is non-degenerate, it had to have some component in the definition that eliminates all similar chains with the same deduction that are of length N-1 or less. That is going to be a hefty definition and resolution rule. Of course your program recovers from that potential inefficiency (I assume) by working the chains in ascending order. But if you work them out of order you won't be able to assume that the non-degeneracy component of the pattern & resolution rule has already been taken care of.

A real player is likely to choose a more oportunistic strategy and use any chains he finds without checking that there are shorter ones.


I agree. So if we are including real players in the conversation, and we are asserting the use of some sort of resolution rule; that pretty much forces us to talk in terms of potentially degenerate patterns.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby denis_berthier » Tue Sep 09, 2008 12:20 am

Myth Jellies wrote:in order to ensure the non-degenerate pattern of length N is non-degenerate, it had to have some component in the definition that eliminates all similar chains with the same deduction that are of length N-1 or less. That is going to be a hefty definition and resolution rule.

Still confusing the logic and the implementation levels.
At the logic level, a chain of length n is defined as a chain of length n; no one has to specify that it isn't of shorter length or that other shorter chains can't do its job.
If we speak of implementation, in the case of Triplets, implementing only the non degenerate case results in a much more efficient program (fewer cases to search for). Similarly, Singles and non-degenerate Pairs are implemented as separate rules.

Myth Jellies wrote:Of course your program recovers from that potential inefficiency (I assume) by working the chains in ascending order. But if you work them out of order you won't be able to assume that the non-degeneracy component of the pattern & resolution rule has already been taken care of.

As already stated in my previous post, I'm not obliged to work in ascending order in SudoRules. Thanks to the confluence property proven at the logic level, I know in advance that I can apply the rules in any order. The "shortest first" order chosen in the default (and only in the default) strategy of SudoRules is convenient for rating purposes, but many different strategies can be programmed and, thanks to confluence, we are sure they are safe.
Just to make it clear, because I'm wondering if you haven't completely misunderstood this also: "shortest first" order means that, at any point in the resolution process, a shortest chain is chosen. It doesn't mean that the next step must use a longer chain. The eliminations made at the current step may make a new chain of shorter length available for the next step.

Myth Jellies wrote:
Denis_Berthier wrote:A real player is likely to choose a more oportunistic strategy and use any chains he finds without checking that there are shorter ones.

I agree. So if we are including real players in the conversation, and we are asserting the use of some sort of resolution rule; that pretty much forces us to talk in terms of potentially degenerate patterns.

Absurd. SudoRules is the material proof of the contrary: it has no potentially degenerate pattern.
A chain defined to be of length n must be built on 2n existing candidates (n left-linking and n right-linking). At the implementation level, this guarantees that one doesn't have to look for useless patterns and it provides efficiency - not inefficiency.
If we are including a real player in the conversation, that pretty much forces you to provide the real example of an AIC using inexistent candidates, as you've been asked for now 4 days.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Myth Jellies » Thu Sep 11, 2008 11:50 pm

Denis wrote:At the logic level, a chain of length n is defined as a chain of length n; no one has to specify that it isn't of shorter length or that other shorter chains can't do its job.


Which is what I have been saying all along. You have been the one saying that we can't have a possible degeneracy and I have said that is incorrect.

If we speak of implementation, in the case of Triplets, implementing only the non degenerate case results in a much more efficient program (fewer cases to search for)


In general, that is a red herring. There are more cases of integers between 1 and 100 than there are prime numbers between 1 and 100, but that doesn't make it faster to determine that a random integer is in the prime set rather than the all inclusive set.

Just to make it clear, because I'm wondering if you haven't completely misunderstood this also...


Yes, I can see where it might be hard for you to resist tossing out insulting insinuations just out of the blue.

If we are including a real player in the conversation, that pretty much forces you to provide the real example of an AIC using inexistent candidates, as you've been asked for now 4 days.


That would only possibly be true if I shared your rather limited view of usefulness. That isn't the case. I also mentioned URs that have had a base digit knocked out by some other reduction. Those could be incorporated in AICs as well. I'm not about to waste my time finding an instance where it has been used as it doesn't much matter to me whether you find the concept potentially useful or not. Our personal solving ethos are just too different for it to matter.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby denis_berthier » Fri Sep 12, 2008 12:05 am

Myth Jellies wrote:
Denis wrote:At the logic level, a chain of length n is defined as a chain of length n; no one has to specify that it isn't of shorter length or that other shorter chains can't do its job.

Which is what I have been saying all along. You have been the one saying that we can't have a possible degeneracy and I have said that is incorrect.

The fact is there can't be any degeneracy in my definition of a chain which doesn't allow the absence of some candidates: if it is defined to be of length n, it can't be of shorter length. Only your definition of AICs with non existent candidates can lead to degeneracy problems.

Myth Jellies wrote:
If we speak of implementation, in the case of Triplets, implementing only the non degenerate case results in a much more efficient program (fewer cases to search for)

In general, that is a red herring. There are more cases of integers between 1 and 100 than there are prime numbers between 1 and 100, but that doesn't make it faster to determine that a random integer is in the prime set rather than the all inclusive set.

Contrary to you, I'm not speaking of generalities in order to create diversions but of something precise.

Myth Jellies wrote:
If we are including a real player in the conversation, that pretty much forces you to provide the real example of an AIC using inexistent candidates, as you've been asked for now 4 days.

That would only possibly be true if I shared your rather limited view of usefulness. That isn't the case. I also mentioned URs that have had a base digit knocked out by some other reduction. Those could be incorporated in AICs as well. I'm not about to waste my time finding an instance where it has been used as it doesn't much matter to me whether you find the concept potentially useful or not. Our personal solving ethos are just too different for it to matter.

Don't worry. I was sure you wouldn't be able to provide the required example.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby StrmCkr » Fri Sep 12, 2008 12:21 am

this thread is way off topic now.

but heres more of my two sence.

if your ordering operand to simplistic techniques first followed by more complexities then your are deffintily not following the techniques of a person solver whom may infact not see the orignal simplisitic pattern and go for the harder ones take this grid.

there is also this fact that is missed: Many Techniques are optional at every given point of a puzzle. how do we pick one. or do we go for them all.

from the first page of Ultimet fish guide.

here is two patterns at once that could be seen.

a player can spot either or: or advance it further and see both.

the pattern can also be used to find "9" and remove it from the same marked cells.

Candidate '8': finned mutant bbbb\rrcc
Code: Select all
*-----------------------------------------------------------*
 |*4689 *689  *489   | 1     3     7     |-489   5     2     |
 | 2    /1    /3     | 489   5     6     | 7     49   #489   |
 |*489  /5    /7     | 489   2     48    | 6     1     3     |
 |-------------------+-------------------+-------------------|
 | 5     3    *89    | 7     1     2     |*489   469  *689   |
 |*89   /4    /1     | 3     6     89    | 2    /7    /5     |
 | 7    /2    /6     | 5     48    489   |*89   /3    /1     |
 |-------------------+-------------------+-------------------|
 | 1     6789  2     | 468   478   5     | 3     469   4679  |
 | 46    67    5     | 2     9     3     | 1     8     467   |
 | 3     6789  489   | 468   478   1     | 5     2     4679  |
 *-----------------------------------------------------------*



Code: Select all
*-----------------------------------------------------------*
 |*4689 *689  *489   | 1     3     7     |*489   5     2     |
 | 2    /1    /3     | 489   5     6     |/7    /49   *489   |
 |*489  /5    /7     | 489   2     48    |/6    /1     3     |
 |-------------------+-------------------+-------------------|
 | 5     3    *89    | 7     1     2     |*489   469  -689   |
 |*89   /4    /1     | 3     6     89    | 2     7     5     |
 | 7    /2    /6     | 5     48    489   |#89    3     1     |
 |-------------------+-------------------+-------------------|
 | 1     6789  2     | 468   478   5     | 3     469   4679  |
 | 46    67    5     | 2     9     3     | 1     8     467   |
 | 3     6789  489   | 468   478   1     | 5     2     4679  |
 *-----------------------------------------------------------*


both and reduce 2 extra clues.

Code: Select all
 *-----------------------------------------------------------*
 |*4689 *689  *489   | 1     3     7     |*489   5     2     |
 | 2    /1    /3     | @489-   5     6     |/7    /49   *489   |
 |*489-  /5    /7     | 489@   2     48@    |/6    /1     3     |
 |-------------------+-------------------+-------------------|
 | 5     3    *89    | 7     1     2     |*489   469  -689   |
 |*89   /4    /1     | 3     6     89@    | 2     7     5     |
 | 7    /2    /6     | 5     48 @   489@   |#89    3     1     |
 |-------------------+-------------------+-------------------|
 | 1     6789  2     | 468   478   5     | 3     469   4679  |
 | 46    67    5     | 2     9     3     | 1     8     467   |
 | 3     6789  489   | 468   478   1     | 5     2     4679  |
 *-----------------------------------------------------------*


or

how about they instead see a
grouped ALS chain that is self decripting. as a disjointed sub set sum pattern
of 489

Code: Select all
 *-----------------------------------------------------------*
 |4689 689  *489   | 1     3     7     |*489   5     2     |
 | 2    /1    /3     | 489@   5     6     |/7    /49#   *489   |
 |*489  /5    /7     | 489@   2     48#    |/6    /1     3     |
 |-------------------+-------------------+-------------------|
 | 5     3    *89    | 7     1     2     |*489   469  689   |
 |*89   /4    /1     | 3     6     89@    | 2     7     5     |
 | 7    /2    /6     | 5     48#    489@   |*89    3     1     |
 |-------------------+-------------------+-------------------|
 | 1     6789  2     | 468   478   5     | 3     469   4679  |
 | 46    67    5     | 2     9     3     | 1     8     467   |
 | 3     6789  489@   | 468   478   1     | 5     2     4679  |
 *-----------------------------------------------------------*


solves to here:
(the restrcitions are self contained in the set)
plus restitions can occur via line of sight not listed.

Code: Select all
 *-----------------------------------------------------------*
 |4689 689  *8   | 1     3     7     |*4   5     2     |
 | 2    /1    /3     | 4@   5     6     |/7    /9#   *8   |
 |*4  /5    /7     | 9@   2     8    |/6    /1     3     |
 |-------------------+-------------------+-------------------|
 | 5     3    *9    | 7     1     2     |*8   469  689   |
 |*8   /4    /1     | 3     6     9@    | 2     7     5     |
 | 7    /2    /6     | 5     8#    4@   |*9    3     1     |
 |-------------------+-------------------+-------------------|
 | 1     6789  2     | 468   478   5     | 3     469   4679  |
 | 46    67    5     | 2     9     3     | 1     8     467   |
 | 3     6789  4@   | 468   478   1     | 5     2     4679  |
 *-----------------------------------------------------------*


Code: Select all
 non existent candidates


how is there none exsitance candiates?

if there wasnt any what did i do?
mathmatically note each sell is missing equal candiadtes then arrange the cells into combinations and find some that lead to a zero state? it is possible. the reliminations seen in the complex move are zero states of the pattern.

when All the givens of a row directly reads what is missing in the none locked cells.

there for the cells must be a candidate of some kinda more specifically they are the ones not found in the row,box,column and restctions via line of sight incurred at each cell. ie the numbers visible to them. so you mathamtically know what is and what is not.

combinatiosn of limitation of sight = restrictions no matter how they are mathmatically aranged in order of

"a leads to b", concepts

or bi directional truth options: where both operations of choice of either of two locals arrive at the same conclusion. (in other WOrds AIC)

where 1 has 2 occupances mathmatically limiting via line of sight so that B cannt equal to A
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 627
Joined: 05 September 2006

Postby denis_berthier » Tue Sep 16, 2008 7:38 am

All this should not lead us to forget that we are still waiting for Myth's real example of an AIC with ALS built on inexistent candidates.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Glyn » Tue Sep 16, 2008 7:51 am

denis_berthier wrote:All this should not lead us to forget that we are still waiting for Myth's real example of an AIC with ALS built on inexistent candidates.


StrmCkr wrote:this thread is way off topic now.


Actually the request (as opposed to requirement) has nothing to do with the original intent of this thread and hopefully will be pursued in the new thread.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby denis_berthier » Tue Sep 16, 2008 7:54 am

Glyn wrote:Actually the request (as opposed to requirement) has nothing to do with the original intent of this thread and hopefully will be pursued in the new thread.

Thanks for correcting my English.
As the request is about the use of inexsitent candidates - as the example in the first post - it has much to do with this thread.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Glyn » Tue Sep 16, 2008 8:08 am

denis There are only two participants in this aspect of the thread, neither of whom are the original poster; to me that indicates that this bone of contention is not of general interest and would be more suitable in its own thread. I see Myth has already started one in which the two of you can discuss this.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby denis_berthier » Tue Sep 16, 2008 8:17 am

Glyn wrote:denis There are only two participants in this aspect of the thread, neither of whom are the original poster; to me that indicates that this bone of contention is not of general interest and would be more suitable in its own thread. I see Myth has already started one in which the two of you can discuss this.

OK. Indeed, there's no longer any real debate on the topic of inexistent candidates in patterns, neither here nor in any other thread: Myth has been unable to provide any example that could have given any credit to his statements. Everyone can conclude for himself.
I'm not interested in starting again the same discussion in another thread, where the conclusions obtained here will be forgotten - a speciality of Eureka.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques