The New Sudoku Players' Forum

[denis_berthier]

In Shye's presentation, there is first a proof (of undefined complexity) of a "strong link" (her terms) and then this is used in the Kraken thing: 2 independent steps.

Not Kraken 'thing', Kraken Firework. Unlike the complexity of 'thing', the complexity of fireworks is clearly defined (they're finned mutant x-wings).
Whether they are independent or not is a matter of opinion, one can even think of any link in a chain as of a step of its own if they wish so.

Up to now, the complexity of proving the "strong link" part (which I understand as being the "firework" part) is not well defined. Say it's 7 (the 7 cells necessary to prove it). Either you count this as an independent step with result the assertion of the 3-way OR, or you add 7 to the complexity of the whole pattern; I can't see any other rational choice - except as Shye, totally avoiding the topic of complexity.
And no, a link in a chain is not a step - nobody here would accept this.

There's no "structure in the grid". The only structures there can be are those one writes explicitly.

The entire point of any notation is to represent the structures in the grid.
These representations can have their own structure, but they are mere descriptions.
That allows you to match equivalent patterns even if the ways they're presented are completely different, such as the kraken and the braid.
I honestly don't understand your POV on this.

The only structure there is "in the grid" is rows, columns, blocks, cells, fixed links between labels for candidates.

Patterns are abstract logical structures relating elementary facts (cells, candidates...) that one tries to find in the grid. Notation is just a way of representing such patterns, but it also expresses the way one interprets the underlying facts as satisfying the pattern.
If the notation says bivalue-chain, then it means the set of facts is seen as a bivalue-chain; if the notation says Kraken-thing, then it means the same set of facts is seen as a Kraken-thing.
Said otherwise, the same set of facts can match two different patterns (even allowing the same eliminations) without these two patterns being conceptually "the same".
Between the raw facts "in the grid" and notation, there is the essential (more or less) abstract level of interpretation as a pattern. This is what you seem to forget.

The simplest example is Pairs and bivalue chains: any set of facts that can be interpreted as a Pair can also be interpreted as a bivalue-chain[2] with the same eliminations. But Pair and bivalue-chain[2] are obviously different patterns. They can be proven along different lines and the allow totally different generalisations: Pair -> Triplet -> Quad -> ... vs biv-chain[2] -> biv-chain[n] -> whip[n] -> ...

In the present example, a whip[6] is a continuous sequence of candidates; the generalised Kraken is a network starting from a big OR, i.e. a forcing-something. Structurally not much in common, even if the Kraken can be re-interpreted as a (much simpler) whip.

All this explains why, in my books, I never write "pattern A is the same as pattern B". What I write is "subsumption theorems":
- any elimination done by pattern A can be done by pattern B.

[denis_berthier]

It's difficult for me to see any fun in overly complicated solutions, when an elementary one exists.

thats fair. for me theyre fun because theyre interesting, stuff i havent thought about yet, sudoku would get a bit monotonous without that

I have fun in Sudoku also, but in different ways. My fun is in trying to find the proper conditions for a pattern to be valid, in analysing its resolution power (wrt to other, simpler patterns) and in trying to extend it.

In the case of your pattern, it would lead me to ask the following questions, in order:
- what is the complexity of proving the "strong link" part?
- is the current presentation (involving all the cells in one row and all the cells in one column) the correct one?
- instead of fixing givens in some cells, wouldn't it be better and much more general to define the conditions by mentioning only allowed/disallowed candidates in the cells outside the block (and in the row or column) ? e.g. 9 must be present in t1c1, r1c9 and r9c1; 9 must be absent in r1c45678 and in r45678c1. This would make 12 cells to check, a huge number.
- considering the high complexity obtained above, is there any simpler way to write the conditions? Indeed, yes: instead of considering rc-cells, one has to consider only 1 rn-cell r1n9 and 1 cn-cell c1n9 => complexity reduced to 2.

[marek stefanik]

Up to now, the complexity of proving the "strong link" part (which I understand as being the "firework" part) is not well defined.

instead of considering rc-cells, one has to consider only 1 rn-cell r1n9 and 1 cn-cell c1n9 => complexity reduced to 2.

I see you have figured it out on your own.
I will spare you my objections to your notion of complexity, I think it more or less works with the patterns you use it for.

Patterns are abstract logical structures relating elementary facts (cells, candidates...) that one tries to find in the grid.

I see the set of elementary facts in the grid as a pattern and anything that uses that exact set of facts as a mere POV.
Like something being expressed in different languages. It doesn't matter whether you call an apple 'apple' or 'pomme'.

The simplest example is Pairs and bivalue chains: any set of facts that can be interpreted as a Pair can also be interpreted as a bivalue-chain[2] with the same eliminations. But Pair and bivalue-chain[2] are obviously different patterns.

This is a bit different.
Since any pair can be described as a bivalue-chain[2], a mere translation would be inaccurate.
So, in my POV, what is in the grid is equivalent to 'the apple' where pair means 'an apple' and bivalue-chain[2] means 'a fruit that is not as tasty as pears are'.

And no, a link in a chain is not a step - nobody here would accept this.

My wording was poor.
Chains are build recursively. I was thinking of AICs, where only the head and tail are important.
Take the grouped w-wing (1=2)r4c1 – 2r3c1 = 2r1c23 – (2=1)r1c4 => –1r4c4. You could represent it as two steps:
(1=2)r4c1 – 2r3c1 = 2r1c23 => 1r4c1 = 2r1c23
1r4c1 = 2r1c23 – (2=1)r1c4 => 1r4c1 = 1r1c4 => –1r4c4
You can see the latter as a kraken (it's written as binary, but you can deal with 2r1c2 and 2r1c3 separately if you wish so).
If you accept the idea that krakens and their bases are two separate steps, then these are two separate steps.
I understand that in your POV the two steps are fundamentally different from the grouped w-wing, but in mine they're equivalent.

In the present example, a whip[6] is a continuous sequence of candidates; the generalised Kraken is a network starting from a big OR, i.e. a forcing-something. Structurally not much in common, even if the Kraken can be re-interpreted as a (much simpler) whip.

The part that is notated is simpler, since that is a bivalue chain.
But when following the reasoning of the whip you have take into account every previous link to take care of the candidates that don't appear in the notation (such as z-candidates).
This makes the reasoning of a kraken much simpler to follow.
It is also way easier to reuse a kraken (add a few links and get a different elimination) than to do the same with the equivalent whip.

Marek

[denis_berthier]

Patterns are abstract logical structures relating elementary facts (cells, candidates...) that one tries to find in the grid.

I see the set of elementary facts in the grid as a pattern and anything that uses that exact set of facts as a mere POV.

Nonsense. How do you first extract "that exact set of facts" from all the facts?

The simplest example is Pairs and bivalue chains: any set of facts that can be interpreted as a Pair can also be interpreted as a bivalue-chain[2] with the same eliminations. But Pair and bivalue-chain[2] are obviously different patterns.

This is a bit different.
Since any pair can be described as a bivalue-chain[2], a mere translation would be inaccurate.
So, in my POV, what is in the grid is equivalent to 'the apple' where pair means 'an apple' and bivalue-chain[2] means 'a fruit that is not as tasty as pears are'.

See above. "What is in the grid" is undefined.

when following the reasoning of the whip you have take into account every previous link to take care of the candidates that don't appear in the notation (such as z-candidates).

I see you haven't yet understood whips, so no discussion of them will be useful.
Previous links don't have to be taken into account.
z-candidates are not part of the pattern.

[shye]

I have fun in Sudoku also, but in different ways. My fun is in trying to find the proper conditions for a pattern to be valid, in analysing its resolution power (wrt to other, simpler patterns) and in trying to extend it.

In the case of your pattern, it would lead me to ask the following questions, in order:
- what is the complexity of proving the "strong link" part?
- is the current presentation (involving all the cells in one row and all the cells in one column) the correct one?
- instead of fixing givens in some cells, wouldn't it be better and much more general to define the conditions by mentioning only allowed/disallowed candidates in the cells outside the block (and in the row or column) ? e.g. 9 must be present in t1c1, r1c9 and r9c1; 9 must be absent in r1c45678 and in r45678c1. This would make 12 cells to check, a huge number.
- considering the high complexity obtained above, is there any simpler way to write the conditions? Indeed, yes: instead of considering rc-cells, one has to consider only 1 rn-cell r1n9 and 1 cn-cell c1n9 => complexity reduced to 2.

so the reason i was avoiding the topic of complexity is because i dont really concern myself with it. sometimes i will prefer a more complex pattern, just if it "feels nice" to solve with, which im aware is very subjective. i can try to answer your questions but i do not fully understand your metrics for a deductions complexity ''｡•́ ∧ •̀
i think further discussion on it would be better within this thread, i would like to get some insight from you and others on
a) how complex the base firework idea is
b) how valuable this type of deduction is (can it find things other simpler techniques cannot)
c) which implementations i provided as examples are worthwhile, and which are just arguably more complex viewings of a different thing, i suspect the firework chains are always the latter

[marek stefanik]

How do you first extract "that exact set of facts" from all the facts?

From eureka notation, it's very simple.
Whenever there is a strong link, we're using the fact that at least one of the candidates can be true. With a weak link at most one of them.
Note that every link is contained in a cell (in your extended meaning) unless there is an embedded pattern that justifies it, in which case you take the facts that pattern uses.
With oddagons every link acts as both strong and weak.
With uniqueness based techniques every pattern of size n that violates uniqueness can be counted as n-1 weak links, the strong links are explicit in the notation or not hard to figure out.
(this is a special case since such patterns aren't prohibited by the rules of sudoku, but by other information the solver may or may not have at their disposal)
From Xsudo's notation it's also very simple, but its notion of truths is equivalent to them being both weak and strong links (upon closer examination one of these links may be found redundant).
From your notation it's a bit harder.
Every variable included in the notation acts as a strong link, the weak links have to be determined (one weak link for every candidate of every variable used, except for its rlc, that contains the target or a previous rlc).

The simplest example is Pairs and bivalue chains: any set of facts that can be interpreted as a Pair can also be interpreted as a bivalue-chain[2] with the same eliminations. But Pair and bivalue-chain[2] are obviously different patterns.

This is a bit different.
Since any pair can be described as a bivalue-chain[2], a mere translation would be inaccurate.
So, in my POV, what is in the grid is equivalent to 'the apple' where pair means 'an apple' and bivalue-chain[2] means 'a fruit that is not as tasty as pears are'.

See above. "What is in the grid" is undefined.

Any example of a pair.

I see you haven't yet understood whips, so no discussion of them will be useful.
Previous links don't have to be taken into account.
z-candidates are not part of the pattern.

z-candidates are guardians of an impossible pattern.
I understand that they cannot be part of it, otherwise the pattern wouldn't be impossible.
Nonetheless you cannot use an impossible pattern without its guardians (unless your goal is to prove that a puzzle doesn't have a solution, in which case there would be no guardians).
If you think you can, I really want to know how.

Marek

[denis_berthier]

How do you first extract "that exact set of facts" from all the facts?

From eureka notation, it's very simple.
Whenever there is a strong link, we're using the fact that at least one of the candidates can be true.

Oh, so now, facts are deduced from notation? I don't see any point for continuing this discussion.

[denis_berthier]

i think further discussion on it would be better within this thread, i would like to get some insight from you and others on
a) how complex the base firework idea is
b) how valuable this type of deduction is (can it find things other simpler techniques cannot)
c) which implementations i provided as examples are worthwhile, and which are just arguably more complex viewings of a different thing, i suspect the firework chains are always the latter

I was not speaking of the complexity of the idea, but the complexity of the pattern, in terms of my specific measure of complexity.
Let's see what comes in the other thread.

[marek stefanik]

How do you first extract "that exact set of facts" from all the facts?

From eureka notation, it's very simple.
Whenever there is a strong link, we're using the fact that at least one of the candidates can be true.

Oh, so now, facts are deduced from notation?

If you weren't asking about extracting the sets of facts from different notations so that you can compare them, I don't understand the question.

I don't see any point for continuing this discussion.

Fair.

Marek

[denis_berthier]

...

Patterns are abstract logical structures relating elementary facts (cells, candidates...) that one tries to find in the grid.

I see the set of elementary facts in the grid as a pattern and anything that uses that exact set of facts as a mere POV.

Nonsense. How do you first extract "that exact set of facts" from all the facts?

From eureka notation, it's very simple.
Whenever there is a strong link, we're using the fact that at least one of the candidates can be true.

Oh, so now, facts are deduced from notation?

If you weren't asking about extracting the sets of facts from different notations so that you can compare them, I don't understand the question.

I never mentioned notation. I talked about selecting a small set of facts making a pattern from the set of all the facts in the grid. How can you do such a selection if you don't know beforehand what pattern you're looking for? Pattern are not "in the grid", they're in our heads.

[marek stefanik]

I never mentioned notation. I talked about selecting a small set of facts making a pattern from the set of all the facts in the grid. How can you do such a selection if you don't know beforehand what pattern you're looking for? Pattern are not "in the grid", they're in our heads.

I don't think you're realizing the differences between our definitions.
For something a solver looks for I prefer the word technique. The solver decides to look for it.
When I said 'structure in the grid', I meant the set of facts that produces the elimination. The solver finds it and concludes that it matches their criteria.
The word pattern can IMO be used in both contexts.

A technique can explain several structures that may or may not be isomorphic.
On the other hand, there might be numerous techniques that can describe a given structure and explain its eliminations, even if the ways they do so are fundamentally different.

Marek

[denis_berthier]

I never mentioned notation. I talked about selecting a small set of facts making a pattern from the set of all the facts in the grid. How can you do such a selection if you don't know beforehand what pattern you're looking for? Pattern are not "in the grid", they're in our heads.

I don't think you're realizing the differences between our definitions.

What I do realise is, you have no definitions at all and you assemble English words in non standard ways.

For something a solver looks for I prefer the word technique. The solver decides to look for it.
When I said 'structure in the grid', I meant the set of facts that produces the elimination. The solver finds it and concludes that it matches their criteria.
The word pattern can IMO be used in both contexts.

No. Words in English have precise meanings. Just in case you don't know the words "pattern", "structure" and "technique",
check here: https://dictionary.cambridge.org/dictionary/english/pattern
and here https://dictionary.cambridge.org/dictionary/english/structure
and here: https://dictionary.cambridge.org/dictionary/english/technique

As I said, there's no "structure in the grid"; there's only a large unstructured set of elementary facts; and such a set doesn't have any structure.
It's the solver (be it human or program) that superimposes its own patterns by selecting a small set of facts that match the conditions of some of the patterns it "knows", e.g. a Naked Pair or a bivalue-chain or a whip[4] or an sk-loop.

"Technique" would mean the particular ways the solver has to do this and it is totally irrelevant here.

"Pattern-matching" is the technical name used in AI to refer to the specific technique implemented in inference engines.
But I think "pattern-matching" is also a good description of what a human solver does: he knows some patterns (and associated resolution rules) and he tries to find some of them among the whole set of undifferentiated facts present in the grid.

[marek stefanik]

From your links I understand that my usage of the first two terms was correct.

Pattern: a particular way in which something is done, is organized, or happens
In our case a way in which the candidates in the grid are organised (the way I used it that you didn't like).
Or a way in which the solver justifies the eliminations (which I think is the way you use it that I said was also possible).

Structure: the way in which the parts of a system or object are arranged or organized, or a system arranged in this way
Pay special attention to the 'or a system arranged in this way' part.

I agree with you on technique, though.
Technique: a way of doing an activity that needs skill
In our case a way of justifying an elimination, given the elementary facts.
The way I explained it in my previous post wasn't accurate.

Marek

Edit Nov 9:
The definition of pattern mislead me a bit. After successfully forgetting it, I realised you meant its usage in functional programming.
I am surprised the site lacks that definition, the closest I found was 'something that is used as an example, especially to copy', which is too concrete, as if you had to provide example inputs.

[denis_berthier]

.
Someone said: when someone doesn't want to understand, don't waste your time trying to explain.

[totuan]

OFF TOPIC
=======
Here, remind me the post here on long time ago from one of famous member:

After serious discussions with my wife, I have decided it is time to retire from active sudoku duty. Raising a family, looking for my next academic job, trying to do research and keeping on top of posts in 5 different forums has become too much for me. I just want to thank some of the people who have helped me to learn the intricate complexities of such a remarkably simple game:
udosuk, ronk, MCC, tarek, JPF, emm, ravel, Cec, gsf, tso, RW (the inventor of my all time favorite move, the reverse BUG), Danny, coloin, Jeff (whose work on nice loops I still read), Carcul (who taught me nice loop notation and that if there is a solution using two steps, there's probably a solution in one step), Ruud (I spend as much time with SudoCue on as I spend with my children ), Myth (perhaps the best combination of theorist, player and expositor in Sudoku, past, present and most likely future), wapati (whose puzzles are the perfect balance of complexity and solvability), Ocean, Havard (skyscapers and 2-string kites made a huge difference in my sudoku life), Mike Barker (always a gentleman, genius, guru, etc...), m_b_metcalf, Red Ed, angusj (SS is still the gold standard), vidarino, claudiarabia (for teaching me the beauty of the bicycle), Mauricio, gfroyle, bennys, Nick70, rubylibs, gurth (GST's are still pretty cool), keith, Lummox JR, Mad Overlord (I learned sudoku on the Susser and the manual is still the best explanation I've read of some techniques), aeb (subset counting still hasn't gotten the due it deserves), Steve R (for teaching me transport, thank you!), Steve K (absolutely brilliant!), Obi-Wahn.

If I left you out, I apologize (except for Denis Berthier who is left out on purpose). I've enjoyed my time here immensely and I wish you all the best in the future.

Zoom on at highlight then you can see the answer

totuan