Gordon, thanks for your comments to the assumptive/non-assumptive question as well. Took me a while to get back to it.
ghfick wrote:Andrew has a number of forcing chains in his solver strategy list. Some of these strategies are also sometimes called Krakens. One can have Kraken Units, Kraken Cells, Kraken Rows, Kraken Columns... There are also Kraken Fish like Kraken Finned X-Wings, Kraken Finned Swordfish....
Before biting into the main course, I'd like to say that I really don't like the term "strategy" here, even though Andrew himself uses it. None of those above are solving strategies but tactics (in the form of candidate reducing patterns). Strategy is a comprehensive plan to attack a puzzle, which includes prioritizing one's goals (efficiency, elegance, speed, etc) and choosing acceptable solving methods (p&p or software, patterns, searching techniques, etc). Andrew's solver implements a single solving strategy which is applying a list of known tactics in a predetermined order.
Many Sudoku writers would say that most, if not all, of these strategies are 'assumptive'
And what would be their argument? What exactly makes those patterns intrinsically assumptive?
To me "assumptiveness" or "non-assumptiveness" is not a fixed attribute of almost any elimination pattern. It has much more to do with the process of finding them. The most obvious assumptive technique is the classic t&e, when the player assumes a candidate (or a combination of them) to be true (or false) and then solves on a copy of the grid (possibly in their head) to see where it leads. If it results in a contradiction (or a full solution), they have learned something about the initial assumption. Otherwise they have learned nothing, and have to try another value or add a nested assumption.
Nishio is an obvious assumptive technique, but I also regard Discontinuous Nice Loops as such, even though the latter is a well-established pattern. The defining characteristic of both is that they're producing contradictions instead of verities. Of course, any elimination (or placement) can be presented as either a contradiction or a verity, so we can't really know anything about a solver's process of finding an elimination just by looking at the documented pattern. Non-assumptive patterns might well have been found using assumptive search methods, and (theoretically) vice versa.
Btw, here's an example of applying a no-limits, computer-assisted, fully assumptive strategy (no, I don't usually solve that way -- in fact, this was a first):
http://forum.enjoysudoku.com/help-to-solve-another-hardest-wu-303-t34897.html#p268156
So what is non-assumptive then? To me it is recognizing or constructing a verity-producing pattern without any a priori assumptions about what it's going to produce. The pattern itself doesn't matter -- only the process of finding it. There's logically nothing assumptive per se about Kraken patterns, or even nets, for example. However, I would bet that many Krakens and nets presented by manual solvers have been reverse-engineered from Nishio contradictions (which are usually much easier to find), but that only makes the process assumptive -- not the pattern itself (finding AICs can be just as assumptive!). No matter how they're found, most Krakens are very easy patterns to understand when presented as solution steps.
To try to prepare a definition of 'assumptive' requires a definition of a 'pattern'.
Not necessarily, though you didn't actually provide one either. You only listed examples of what you consider patterns.
An MSLS is a pattern. Its logic is clear and the MSLS pattern appears quite often in extreme puzzles.
It should be obvious by now that I, for example, don't (yet) think its logic is clear (but that's my problem, and hopefully a transient one)
One problem with complicated patterns is that their eliminations are obvious only to the initiated. On the other hand, well-presented net solutions (like totuan's), can be understood by anyone with an elementary understanding of sudoku rules.
Most writers would say that Exocets [that are not Junior] are not patterns.
I would say they are, but not fully self-contained ones like JEs. In many cases they're probably not practical patterns for manual solvers, but that doesn't make them non-patterns.
Once you see it [a pattern] and understand its logic, the exclusions follow from it.
Actually, you don't need to understand the logic of a well-defined and self-contained pattern, as long as you trust the pattern provider. It could just as well be a black box. You only need to recognize the pattern ("count the elements") and remember the elimination rules. Zero logic needed. I bet there are people who actually use (or code) some complicated patterns without really understanding how and why they work.
A strategy may be called 'assumptive' if its exclusions can only be seen starting with an IF statement [an assumption].
By that definition any pattern is internally "assumptive" and so is using it! Patterns are recurring and recognizable pieces of pre-packaged logic, and logic always has those IF statements (possibly hidden under higher level abstractions, such as set logic, but they're still there). You can't get rid of them by using patterns -- you just don't have to think about them, if you've memorized the elimination rules. Basically, you've replaced several if-then-else statements with a single "if pattern==true, then eliminate xxx". A pattern is nothing more than a higher level abstraction that hides logic details.
If a chain can be expressed in a bidirectional way, most authors would say that such a chain can be described as a pattern and so it is non-assumptive. If a chain can only be expressed as unidirectional, many writers would say that it is 'assumptive'.
And what would be their supporting argument? Most if not all unidirectional chains can be made bidirectional with a little tweaking, so would that make them non-assumptive all of a sudden? You basically ask the same question later, so you must know that claim is very weak. Besides, I don't see what directionality has to do with assumptiveness in the first place. A unidirectional chain with strong links at both ends establishes a derived strong link (OR) between the two ends just as well as a bidirectional one, so effectively it's always bidirectional (even if it's harder to see):
- Code: Select all
~a -> b <=> a | b <=> b | a <=> ~b -> a
Thus, it's functionally no different from an AIC.
Such a unidirectional chain must start with an assumption.
Can you elaborate? All chains, including AICs, start with an assumption. Do you mean an assumption of "node=true"? That's only true for Nishios and some Discontinuous Nice Loops which produce contradictions. All verity-producing chains and nets, whether bidirectional AICs or bi/unidirectional AIC Nets or memory chains (or Krakens), work just like AICs; i.e. they have a derived strong link between the two (or more) ends, which is used to prove a verity (or many in case of a loop). In their case the initial assumption which starts the chain is always "node=false" (including Krakens, if you start at one of the ends instead of the SIS hub as usually presented). If you think that's assumptive, then you must stop using AICs too.
[Edit: The defining difference is not whether the assumption is "node=true" or "node=false". It's whether only one of those is used in the proof. Chains that produce contradictions only use one or the other, and those are what I would call "assumptive". AICs, AIC Nets, Krakens, etc use both options (but only one starts the chain) when proving that at least one of the end nodes of the chain/net must be true (a derived SIS), and thus any candidates weakly-linked to all of them must be false. That's why they're non-assumptive by my definition.]
Here's a bit more about my thoughts on the relationships between some chaining patterns:
http://forum.enjoysudoku.com/forcing-chains-nishios-krakens-aics-dnls-t34574.html
Many chains that have 'memory' along its direction would be called assumptive.
Again, I don't think that's a fixed property of a memory chain per se. However, it's hard to imagine building a memory chain without having an a priori elimination objective in mind. The same is true for other kinds of nets and even split-node chains. I guess it would be fair to say many of them are probably assumptive from that point of view, but there's no proof unless we know how they were built. In any case, the pattern itself is no more assumptive than an AIC.
A bidirectional chain can have nodes that are patterns of various kinds. A node [or nodes] can be ALS's, X-Wings, JEs... So all of these chains are non-assumptive.
So are unidirectional chains with the same kinds of nodes as well. No logical difference. Both are just as equally assumptive, if we know their constructing process was such.
[Edit: The nodes can also be other AICs, which means that every Kraken with linear branches can be converted into an AIC with nested AICs as boolean nodes, as demonstrated behind the previous link. If you accept that, then you must accept that (at least linear) Krakens are non-assumptive by your definitions as well.]
Many authors would say it is worthy and interesting to exhaust all non-assumptive steps in solution path construction.
And I would agree. However, it's nothing but a personal preference. It's also not a religious commandment to me, which is why I can entertain other kinds of steps as well if need be.
Some authors prefer to leave a puzzle unsolved rather than complete solution paths with assumptive steps.
Another personal preference, though not one I share. To me an ugly solution is usually better than no solution. If I've understood correctly, even the non-assumptive purist David submits to using net methods etc if he can find nothing else that works. For him that threshold is just very high for obvious reasons.
The boundary between assumptive and non-assumptive is hazy to me. A single finned Kraken X-Wing can be seen as a bi-directional chain with an X-Wing as a node. So it can be said to be non-assumptive. [maybe?] Sometimes a chain with memory appears to be unidirectional but then the reverse direction becomes apparent [perhaps with different logic] and so maybe such a chain is now non-assumptive.
Have you considered that the problem of haziness might go away if you adjusted your definitions a bit?
My definition of assumptiveness is really easy and consistent: if you *assume* something and try it to produce a contradiction (or a full solution), then it's assumptive, otherwise not. With my definition very few patterns (mainly Nishios and Discontinuous Nice Loops) are assumptive per se. Many intrinsically non-assumptive patterns can be found using assumptive methods, though, and it's more likely for some than others.
Some authors enjoy finding a small set of strategies [sometimes even just a single killing step] that solves a difficult puzzle. There is a thread on the forum entirely devoted to finding that one crucial step.
According to a bit wider interpretation of my definition, all one-stepper solutions to the daily puzzles are very much assumptive, as they start with a known elimination target around which a proving pattern is built. The patterns themselves aren't (usually) assumptive, but the process most definitely is. Does it somehow make those ingenious solutions less interesting? I don't think so.
and more... 