Pattern-based classification of (hard) puzzles

Advanced methods and approaches for solving Sudoku puzzles

Re: Pattern-based classification of (hard) puzzles

Postby David P Bird » Sat Jun 01, 2013 4:23 pm

Denis Berthier wrote:One more point: the full list of rules into which a standard JExocet can degenerate is not obvious. You may consider that some of them are not acceptable from a player's POV, even if "reversible".

I missed this addition to your previous post. The embedded inferences in a JExocet pattern are something I'm trying to catalogue now, which I think should be described in the definition. I believe the pattern requirements are robust enough to identify a JE in whatever semi-resolved state it occurs, so that we can cite the pattern and then pull out the inference to be used in combination with a chain or pattern whenever we want.

Like a barrister, I also have a completely different line of argument, one I first used with Ruud probably in 2006. When we eliminate a candidate in a cell it becomes what he called a "Sudoku Truth", a fact that we've proved must be true once and which can be freely used without needing to be re-proved. We could therefore also recognise derived inferences from patterns as Sudoku Truths. If we did this however it would allow any net-based method to be used simply by logging the derived inferences available from each chain segment and progressively combining them into a linear stream. But, without malice, in my eyes you're already using a form of nets anyway!

This only goes to show that everything in respect to what is acceptable in Sudoku or not is arbitrary and reduces to a mattern of personal choice. We just have to live with the fact that others see things differently.

Denis Berthier wrote:OK, you know that base digit a must be in one of the two target cells, but you don't know in which of the two. Which further elimination does this allow in general?

This appeared as I was preparing this post. The simplest answer is that digit in question must be false in those cells seen by both targets, but the new strong link could also be used to link two chain segments to make a remote elimination.
David P Bird
2010 Supporter
 
Posts: 1043
Joined: 16 September 2008
Location: Middle England

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Sat Jun 01, 2013 5:29 pm

David P Bird wrote:We could therefore also recognise derived inferences from patterns as Sudoku Truths.

If we accept this, every sudoku can be solved by whips[1].

David P Bird wrote:
Denis Berthier wrote:OK, you know that base digit a must be in one of the two target cells, but you don't know in which of the two. Which further elimination does this allow in general?

The simplest answer is that digit in question must be false in those cells seen by both targets, but the new strong link could also be used to link two chain segments to make a remote elimination.

But, apart from the first obvious case, this falls into the problem of uncontrolled inner patterns.
denis_berthier
2010 Supporter
 
Posts: 4233
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby eleven » Sat Jun 01, 2013 9:53 pm

David P Bird wrote:Step N: we locate a JExocet pattern and eliminate the non-base digits from the target cells if there are any.
Step N+X: determines that a digit is locked in the base cells

At this point you get a 1-digit pattern in 3 rows (or columns), which could be spotted also, when the "Exocet" was not yet born.
Step N+X+1: uses the newly revealed inference that that digit must occupy exactly one of the targets to make a further elimination.

So to remember an Exocet ist not needed to get the inference (though it is is nice, when you do).
eleven
 
Posts: 3173
Joined: 10 February 2008

Re: Pattern-based classification of (hard) puzzles

Postby David P Bird » Sat Jun 01, 2013 11:05 pm

Eleven OK so that wasn't a good example but there are others (similar to the one < here > ) where this type of simplification isn't possible.

What I was trying to do was simply understand Denis' viewpoint. But I'm afraid our meeting of minds failed miserably and it remains as much a mystery to me now as it was when I first responded.
David P Bird
2010 Supporter
 
Posts: 1043
Joined: 16 September 2008
Location: Middle England

Re: Pattern-based classification of (hard) puzzles

Postby blue » Sat Jun 01, 2013 11:33 pm

Maybe a better example of the kind of thing that Denis was talking about, would be if a JExocet existed, and then (somehow) you managed to fill one of the base or target cells.
blue
 
Posts: 1052
Joined: 11 March 2013

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Sun Jun 02, 2013 3:48 am

Blue is right, my answer didn't bear on David's specific example (which eleven has shown can be dealt with in simple ways). I was answering the general question I understood he was asking: what happens after we have applied the JE rule? Can we use it again later if part of its structure is altered?
In my view, there are four ways of doing this:

1) ad hoc: I have nothing to say about this;

2) using other independent resolution rules; as JE includes some quasi Fish part, it is likely that this part will sometimes appear to play some role in later eliminations; but it may be the case or not; as these rules exist independently of JE, the kind of information that may be useful about them is, how frequently they happen to be used after JE, based on the remaining JE part;

3) using specialised JE rules corresponding to different special cases allowing more eliminations (without going into details, I remember that daj had a list of such cases);

4) using follow-on rules with conditions including explicitly the JE pattern or part of it; it may be the case that such rules can be written; however, it may be a hard job to specify them; moreover, their complexity will be higher than JE; I can hardly imagine JE being included in some complex chain and David considering this as an "acceptable pattern".


After writing this, I wondered why this question appeared about JE.
For generic rules (whips, Subsets, ...), we have the feeling that the eliminations they specify exhaust their content.
For JE, what can be proven is apparently more than the elimination of the non-base digits: the two Target Cells must contain the same values as the two Base Cells; but the JE rule only says that the non-base digits can be eliminated. However, these eliminations do exhaust the content of the rule. To see this, consider what can happen to the Base Cells:
- if a digit is eliminated from one of them, either it is still present in the other and nothing is changed, or it disappears from both and we are left with a simpler JE that can eliminate it from the Target Cells (whether we have already used the original JE or not);*
- if a value is asserted for one of the Base Cells, this is the case just dealt with by eleven.**


(*) I wonder if this can happen in practice:
- apply JE4
- one of the digits is eliminated (by other rules) from both Base Cells
- apply J3 to eliminate this digit from the Target Cells

(**) this shows that when we accept JE, we must also accept Fish (but this was already obvious).
Last edited by denis_berthier on Sun Jun 02, 2013 4:09 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 4233
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Sun Jun 02, 2013 4:06 am

David P Bird wrote:everything in respect to what is acceptable in Sudoku or not is arbitrary and reduces to a mattern of personal choice.

I wouldn't equate "personal choice" with "arbitrary". A personal choice can be based on rational arguments. These may seem more or less convincing to other people, but this doesn't mean that the choice was arbitrary.

The "everything" also is too strong. To mention only the most obvious, I don't think anyone would consider that rules in SSTS are not acceptable.



David P Bird wrote:We just have to live with the fact that others see things differently.

David P Bird wrote:But, without malice, in my eyes you're already using a form of nets anyway!

Difficult to live with the fact? ;)

I'm using "and branching" in braids (not in whips), which is a very natural thing; but I never use "or branching".
denis_berthier
2010 Supporter
 
Posts: 4233
Joined: 19 June 2007
Location: Paris

Previous

Return to Advanced solving techniques