The New Sudoku Players' Forum

[daj95376]

[Edit: Withdrawn]

[David P Bird]

Denis, many thanks for your efforts.

It's clear that different contributors speak Sudoku in different dialects which makes penning definitions and descriptions awkward, but no more so than in our conversations in everyday life. Provided the terms in different dialects are fit for purpose and aren't ambiguous, there should be no loss of clarity, although readers may be irritated by the dialect used in any particular piece. I therefore consider that there is no need to write such things as "units/houses" in our work here.

To give one example, for several years I've been calling a row of boxes a 'tier' and a column of boxes a 'stack' which has allowed me to use a 'band' of boxes as being either a tier or a stack in the same way that a line of cells means either a row or column of them. This avoids having to use clumsy phrasing such as 'chute or tower depending on the orientation'. From their reactions, I believe that other contributors have been able to accept this as part of my dialect. Of course if I were ever to write a book I would have to provide a glossary of my terms.

Now to specifics:

I accept referring to base digits rather than base candidates and your reasoning behind it.

Conditions on candidates

1) No base cell is decided.
Each base cell may have up to 4 candidates, but together, they contain only digits (called the base digits) taken from a set of cardinality 3 or 4: {a, b, c (and d)}

2) Each Object Cell Pair is made of two cells: the target cell and the companion cell
Each target cell contains at least one target digit (plus possibly non-target digits)
Companion cells contain no target digit

3) For each target digit, there are two units/houses (different from the cross-lines) containing/covering all its occurrences in the S cells (be it as a candidate or as a decided value).

Remark: the units/houses may be rows or blocks (in case of the above graphics), resp. columns or blocs (in case the graphics is rotated).

Here you've switched from using base candidates in (1) to target digits in (2) and (3)

I don't see 1) as being much of an improvement on the original
1) The base cells must be restricted to a set of three or four digits (the base candidates)
I also consider the reference to cardinality to be a big turn-off for the majority of readers, and in the light of your closing remarks a bit of over-kill.

2) I can accept

3) Is neater but I consider that "(different from the cross lines)" is not a condition. When a cross line is also a containing house the partial sword fish degenerates into a partial X-wing but it makes no difference to the truth counts.

If the examples are provided, the remark should be unnecessary.

I like your Proof of the JExocet Rule - I always suspected that mine could be improved. I would only want to change your word order in some places.

Generally the way JExocet pattern is defined and proved should pave the way for the JE+ definition and proof, so it would be best to wait until that is covered too before anything is finally decided. This is one of the reasons I posted my piece on partial fish – the other is that it may open the door to other single band inference patterns that could be used in combination with them.

[blue]

Hi champagne,

I have the feeling that you are mixing the 2 cases;
I don't use the permutations when looking for JEXOCETS. Reversely, I have a permutation process to detect non JEXOCETS patterns.

Correct. When you said "pattern", I didn't read "JEXOCET pattern".

I got a very nice speedup, by solving the puzzle beforehand, and looking only at cases where the base and target pairs, actually contain the same pair of (distinct) digits in the solution.

very good idea.I keep it in mind and will do the same. My first reaction would be "what about twin exocets"

I don't look for twins, specifically. I only find both, when they exist.

4) setting the base to true and the targets to false lead to a reasonable number of permutations

This number is actually zero, is it not ?
Do you mean a reasonable number of "partially competed permutations, that are obviously impossible to complete" ?

The correct wording would be

if it is not the searched pattern you can stop at the first valid permutation
and as you say , if it is the pattern you have a reasonable number of "partially competed permutations",

Right. I should have said that it's zero or one, in the search for valid instances, and some number of "partially completed permutations" in both cases.

Regards,
Blue.

[denis_berthier]

Here you've switched from using base candidates in (1) to target digits in (2) and (3)

I don't see 1) as being much of an improvement on the original

3) Is neater but I consider that "(different from the cross lines)" is not a condition. When a cross line is also a containing house the partial sword fish degenerates into a partial X-wing but it makes no difference to the truth counts.

If the examples are provided, the remark should be unnecessary.

I made a few corrections along these lines.


When I said I wanted a final definition, I didn't mean one that couldn't be re-formulated into an equivalent form. I only meant one on the meaning of which everybody agrees.

[blue]

Hi Denis,

I think there's a fundamental difference between the two situations.

In the JExocet case (as for any resolution rule), you can refer to a "mathematical" theorem (the JExocet rule), proven once and for all.

(...)

By saying that the difference is fundamental, I mean in particular that it is not mainly one of complexity, as you seem to be suggesting (though it is not totally unrelated to it and I find your comments on complexity interesting).
When you refer to a theorem, it doesn't matter how hard its proof may have been.

(...)

I understand, but I would add one caution.

If an "exocet property" has been verified by computer, you could list the cells, and refer to "Theorem Exocet-X-B-T" ... "certainly provable, and in fact just proved by my computer" ... where X represents the PM state and B and T are the base and target specifications. An odd twist.

If you want to say that that sort of thing is inapproriate ... and I do want to say that ... then it seems like the thing to do, is to note that there are an infinite number of theorems like that, not all proven (of course), and introduce the idea that the solution paths may to refer (without proof), to only a finite number of pre-designated theorems. Any other theorem used to support the validity of the path, would be required to have a supporting proof included. With that, the complexity issue re-surfaces, and requiring that proofs for the pre-designated theorems be included as well, wouldn't change the complexity analysis.

This discussion arose here, but it is also relevant to logel's tentative definition of a general "elimination pattern".

Exactly.

If it could be shown that not-necessarily-minimal instances of the "pattern", could be verified in polynomial time in the puzzle size, it would follow that (P = NP).
If it could be shown that minimal instances of the "pattern" ("his patterns"), could be verified in polynomial time in the puzzle size, it would follow that (Co-NP = NP).

You may be familiar with this, but ...

Co-NP is the class of decision problems that ask the complementary question for an NP problem. The (NP-complete) sudoku problem, asks "does this puzzle have a solution ?". The associated (Co-NP-complete) problem, asks "is this a puzzle with no solution ?". (Co-NP = NP) would follow from (P = NP), if it were true, and people have tried (with no luck) to prove that Co-NP and NP are distinct. If that could be shown, it would follow that P and NP are distinct. People who believe in (P = NP), have presumably tried proving that (Co-NP = NP), since it would be provide "supporting evidence" for the (P = NP) conjecture. Like the (P = NP) conjecture, it hasn't been proven one way or another (to my knowledge).

Regards,
Blue.

[denis_berthier]

If you want to say that that sort of thing is inapproriate ... and I do want to say that ... then it seems like the thing to do, is to note that there are an infinite number of theorems like that, not all proven (of course), and introduce the idea that the solution paths may to refer (without proof), to only a finite number of pre-designated theorems. Any other theorem used to support the validity of the path, would be required to have a supporting proof included. With that, the complexity issue re-surfaces, and requiring that proofs for the pre-designated theorems be included as well, wouldn't change the complexity analysis.

Complexity analysis has probably some part to play in saying that "that sort of thing is inappropriate". But I think there is also some non formalisable aspect, something that revolves around the ideas that a theorem has to have some meaning for us or that a proof has to be elegant/beautiful. A mathematician is not a theorem prover; he is first a kind of visionary (I'm thinking of some of our local people: Schwartz, Neveu, Thom, Grothendiek; you probably have yours also); and, when acting as a theorem prover, he doesn't work like a formal one.
Another way of putting it is, a "theorem" in the sense of formal logic (i.e. a formula proven to be true) - e.g. the "infinite number of theorems like that" you are mentioning - would in most cases not qualify as a theorem in the usual sense.

If it could be shown that not-necessarily-minimal instances of the "pattern", could be verified in polynomial time in the puzzle size, it would follow that (P = NP).
If it could be shown that minimal instances of the "pattern" ("his patterns"), could be verified in polynomial time in the puzzle size, it would follow that (Co-NP = NP).

Yes, but... would you engage in such an adventure?

Like the (P = NP) conjecture, it hasn't been proven one way or another (to my knowledge).

Oh no. If it had been settled, you'd see it in all the newspapers.

BTW, the conjecture is not P = NP, but P <> NP. From a formal POV, it may seem to be the same thing. But, in practice, a vast majority of people dealing with it believe that NP <> P. [OK, maths isn't a matter of polling].
From my experience with classification in Sudoku[9] (instances becoming extremely harder as they become extremely rarer) and a brief look into larger ones, I have the feeling that as size increases, the possibilities for such worst cases increase almost exponentially. Of course, this feeling may be wrong, but that's enough for deterring me from trying to prove P=NP.
As for proving P<>NP, it's a lifetime job and I'll keep it for some future life if any - but not the next, nor even the second next; there are so many other things I'd like to do before! Indeed, if I had to work on this, what'd I'd probably try to prove is not P<>NP, but that it is undecidable.

[David P Bird]

When I said I wanted a final definition, I didn't mean one that couldn't be re-formulated into an equivalent form. I only meant one on the meaning of which everybody agrees.

No worries then as you have satisfied yourself that you understand the JExocet pattern and therefore I suppose the JE+ pattern. I also appreciate you've got other fish to fry at the moment.

If and when you turn to daj's case, twin JExocets and ABI loops I'll be interested in you’re your reactions. I don't consider either daj's case or ABI loops fully qualify as patterns. Twin JExocets are very powerful though. The multiple eliminations they provide arise from combining the inferences provided by different parts of the pattern in different ways.

I feel rather out of place anyway as I'm the only manual solver here and will only accept branching when it's confined to recognisable patterns. So I'll hold this topic in abeyance for now and turn to frying other fish as well.

[denis_berthier]

I don't consider either daj's case or ABI loops fully qualify as patterns.

I don't know what an abi loop is, but if it's some of the stuff that can only be defined via some obscure procedure, I don't even want to know.

[David P Bird]

I don't consider either daj's case or ABI loops fully qualify as patterns.

I don't know what an abi loop is, but if it's some of the stuff that can only be defined via some obscure procedure, I don't even want to know.

They're a way to reduce the possible pairings of the base digits that can be true that champagne uses. He can describe them better than me.

[denis_berthier]

I feel rather out of place anyway as I'm the only manual solver here.

I don't think the discussion with Blue about what can be called a pattern is really alien to your POV as a manual player. Probably you will accept fewer patterns than can be defined by factual/descriptive/logical/non-procedural conditions only, but I'm quite certain that you wouldn't accept more.

[champagne]

I don't consider either daj's case or ABI loops fully qualify as patterns.

I don't know what an abi loop is, but if it's some of the stuff that can only be defined via some obscure procedure, I don't even want to know.

They're a way to reduce the possible pairings of the base digits that can be true that champagne uses. He can describe them better than me.

the "abi loop" is a clear process, nothing "obscure", but it uses the uniqueness property, so Denis is not interested anyway

[denis_berthier]

the "abi loop" is a clear process

First reason for not being interested, if it can only be described as a process, i.e. a procedure.

but it uses the uniqueness property, so Denis is not interested anyway

Right

[David P Bird]

the "abi loop" is a clear process, nothing "obscure", but it uses the uniqueness property, so Denis is not interested anyway

That slipped my mind!

However you're now describing it as a process not a pattern, so does this mean you've had change of heart about the difference between the two? If so, then Exocet (rather than JExocet) is a process triggered by finding a qualifying pattern, which is the way I've always considered it.

[Added] We can call what we do to find a pattern a process too, but that only involves checking if the elements of the pattern exist and doen't depend on following inferences.

[denis_berthier]

Exocet (rather than JExocet) is a process triggered by finding a qualifying pattern, which is the way I've always considered it.

At least, we're on the same line here. Your "qualifying pattern" is the same thing as the "partial pattern" I evoked before.
Of course, it doesn't imply that the process may not be interesting as a search tool for discovering real patterns - which appears to be precisely the case, as the discussions about the Exocet process played a role in the elicitation of the JExocet pattern.

[champagne]

the "abi loop" is a clear process, nothing "obscure", but it uses the uniqueness property, so Denis is not interested anyway

That slipped my mind!

However you're now describing it as a process not a pattern, so does this mean you've had change of heart about the difference between the two? If so, then Exocet (rather than JExocet) is a process triggered by finding a qualifying pattern, which is the way I've always considered it.

[Added] We can call what we do to find a pattern a process too, but that only involves checking if the elements of the pattern exist and doen't depend on following inferences.

sorry for the word "process". The "abi loop" is clearly a pattern.