The New Sudoku Players' Forum

by **gurth** » Thu Jan 04, 2007 12:17 pm

___________________________________________________________________
CONTRADICTION NETS

I have long ago learnt not to argue with those who have closed minds. It would be waste of time to respond to the attacks on Contradiction Nets and my other methods by people who have not the faintest idea of what I am doing, and want to keep things that way.

However, no doubt there are other people with more open minds who would like my opinions on these matters.

Certainly it is possible to resort to Contradiction Nets in a stupid way: using blind trial and error and systematic brute force. The observant will notice that I have moved away from such stupid methods quite drastically, to the extent where there is no error at all.

Resulting from my study and analysis of the Sudoku, I arrive at a COHERENT STRATEGY. This is something unprecedented in Sudoku, and more resembles master chess.

In the past "strategy' has simply meant applying your list of available "techniques" in order of difficulty to eliminate candidates WHEREVER POSSIBLE. That is to say, if you see a naked pair, do it; if you see a chain, use it; if you see an ALS use it. This is not what I call strategy. It is just unplanned opportunism, and if you DON'T see anything, then you quit. That is of course what normally happens with the ultras.

By strategy I mean this: I don't TRY anything (no trial and error), and I make NO errors (no trial and error). What I do is create a MASTER PLAN: determine a precalculated sequence of steps which will lead to solution. The steps are all decided on before any of them are "tried" or put into practice. And these steps are all part of an organic whole. It's no longer a case of "Do what you can and hope that some unforeseen opportunity will appear."

It is rather stupid to condemn all past techniques based on Contradiction Nets without having any idea of what new Contradiction Net techniques might be discovered.

All that is not to say that there is anything wrong with using Trial and Error to an optimal extent. In one's studies, one should always TRY as many things as possible : that is the royal road to discovery and learning.

FINALLY, my strategies continue to develop and become more numerous, because there is not only ONE optimal strategy, but many possible strategies, which once they reach a reasonable stage of development may be used for different Sudokus.

In fact, as I expect and look forward to the appearance soon of 10.8, 10.9 and elevener Sudokus, there will be a continued pressure on the strategies and techniques within Contradiction Nets to develop in order to keep pace and continue to work.

This scenario is very far removed from the claims of the ignorant "that this has all been done before" and "that there are no advanced techniques involved." The ANSWER is DEVELOPMENT.
____________________________________________________________________________________________

by **Myth Jellies** » Thu Jan 04, 2007 5:52 pm

I see a lot of derisive prattle about how unobservant I must be, but I don't see anything here which indicates how your tentative assumptions are any different from those of Ariadne's Thread. You might be using some strategies to hone your guesses and determine when to abandon them, but I observe that to be well within the realm of what a person would do with Ariadne's Thread, especially a limited form of AT which allows exclusions only. A systematic application of a limited Ariadne's Thread is still Ariadne's Thread.

by **ronk** » Thu Jan 04, 2007 6:42 pm

If this new thread is intended as the place to post solutions to extremely difficult puzzles, I applaud the move.

That would certainly be better than a separate thread per puzzle.

Someone could volunteer to maintain an index with links to the different puzzles within the thread, and having that index in -- or very close to -- the opening post would work best IMO.

Ron

by **StrmCkr** » Fri Jan 05, 2007 5:31 am

by **Steve K** » Thu Jan 25, 2007 5:49 pm

Contraction nets can be seen wholly as a subset of forbidding chains, in my humble opinion.

One can show the logical equivalence of a contradiction net to the general form of forbidding matrices, which can be used to justify every possible sudoku elimination.

To argue that a technique is more or less logical really is in the eye of the beholder.

For example, it is often said that a hidden pair is harder to find than a naked pair. To my way of thought, this is turning human solving of sudoku puzzles upside down. Hidden pairs are often easily found before entering the possibilities. Naked pairs are only found after entering possibilities. For this reason, when I tackle a puzzle without using aids to develop the possibility matrix for me, I look for hidden pairs before entering any possibilities. Even when using such an aid, hidden pairs are often more easily located by making the possibility matrix invisible. This often solves much more of the puzzle, and sometimes eliminates the need to use possibilities. Does this make that approach illogical? Certainly it cannot. It is merely different.

If a technique can be formalized using logic, it is logical. I can see no other standard that makes sense.

For this reason, I prefer to consider the number of native strong sets a technique or step uses to evaluate its difficulty. This seems to be the only manner of evaluation that is not arbitrary to the eye of the beholder. Regardless of the technique, it is easy to list what information the technique actually requires. In all cases, only native strong sets need to be considered, as weak links are universal to every puzzle. For example, regardless of the puzzle, r1c1 =1 forbids r1c9=1. It matters not whether or not 1 can actually exist in either of these locations. The statement is still true.

I do not like to use forcing chains, or forcing nets, or contradiction nets. But, since I can show that their logical equivalence to other technqiues, I cannot disparage them as not being logical.

by **re'born** » Thu Jan 25, 2007 6:26 pm

Hi Steve,

Welcome to the forum. We look forward to your unveiling the definition of forbidding chains and the forbidding matrix.

Steve K wrote:I do not like to use forcing chains, or forcing nets, or contradiction nets. But, since I can show that their logical equivalence to other technqiues, I cannot disparage them as not being logical.

I don't think the issue with anyone here is whether or not contradiction nets, etc. are logical. The question is whether or not they are Trial and Error (which is definitely logical). Any technique that requires the user to start by saying, "assuming this cell contains [or does not contain] this candidate, then...", will not be appreciated by a large number of forum members. The issue raised by Gurth seems to be that there is a difference between sitting down, dropping your finger on a cell, having your wife choose a candidate and then checking whether or not you get a contradiction versus studying the grid, the weak and strong links, etc., and then testing cells that somehow control the puzzle. The normal response of the 'non-assumptive' players is summed up by Myth Jellies:

Myth Jellies wrote:A systematic application of a limited Ariadne's Thread is still Ariadne's Thread.

It is then up to the player to decide what makes Sudoku fun. Is it worthwhile to solve a puzzle using (educated) T&E? Do you feel better about an assumptive technique if you put in a lot of research first? Are you willing put aside the really really hard puzzles that known non-assumptive techniques won't crack (or are maybe just to darn difficult to apply by hand)?

by **Steve K** » Fri Jan 26, 2007 2:13 pm

Hi rep'na!

Thanks for the kind welcome.

Because I find a logical equivalence across all sudoku techniques that do not require the rule of Uniqueness, this logical equivalence wraps itself into a nice loop that means:

All sudoku techniques (not involving uniqueness of solution) can be shown to be equivalent to Ariadne's Thread.

This makes the discussion of whether or not a technique is T&E moot, since Ariadne's Thread is always thought of as T&E.

I suppose that it is entirely in the eye of the individual solver as to how satisfying their own application of logic truly is. Personally, I absolutely love using logical techniques, regardless of name, to attack a truly difficult puzzle.

The equivalence across techniques is especially of interest to me:
For example, it is almost trivial to show that the following three techniques are precisely equivalent:
Pairs, Hidden Pairs, X wings.

In a simlar fashion, all ntuples are equivalent, strictly, to single candidate fish of size n.

All elimination involving two native strong sets are stricly equivalent to the finned X wing.

All eliminations involving three native strong sets and more than one candidate are strictly equivalent to the Y wing.

Upon the consideration of three native strong sets, things start to get interesting. Since techniques involving a single candidate allow more complex grid interaction, things get interesting there first. Nevertheless,

All eliminations involving three native strong sets are strictly equivalent to a 3x3 triangular forbidding matix.

What do I mean by strictly equivalent? I mean that by placing the strong sets within the equivalence vehicle, every single technique is represented.

Once one gets to 4 native strong sets, things get really interesting:
First, one must start to either deal with Uniqueness or not.
Second, one needs a much stronger vehicle to represent all possible eliminations. This is a natural result of all the possible grid interactions.

Andrei Zelevinsky and Bruno Greco have developed the theory that handles every possible sudoku elimination not involving uniqueness from this point forward. The theory is a bit long to present here, and generally does not come into play in actually solving a sudoku puzzle. But, as a unifying theory, it has convinced me that a more general approach is the most logical of all approaches. Of course, that evaluation is completely arbitrary.

I have introduced a limited case of these general forbidding matrices in another thread. (Also in my blog, sorry about the plug) They really are not a solving tool, but rather a language tool. Nevertheless, understanding them does allow one to see how vastly similar techniques that first appear quite different really are.

In summary, I have no interest whatsoever in a technique that "feels" like T&E. But, I can give no logical explanation of what T&E truly is. I find this forum to be almost entirely about techniques that "feel" absolutely nothing like T&E.

by **udosuk** » Fri Jan 26, 2007 3:51 pm

Steve K wrote:All sudoku techniques (not involving uniqueness of solution) can be shown to be equivalent to Ariadne's Thread.

Can you elaborate a little more on this point please? :?:

Steve K wrote:This makes the discussion of whether or not a technique is T&E moot, since Ariadne's Thread is always thought of as T&E.

Here is some info about this issue:

Wikipedia wrote:Distinction from trial and error

The terms "Ariadne's thread" and "trial and error" are often used interchangeably, which is not necessarily correct. They have two distinctive differences:
The term "trial and error" implies that each "trial" yields some particular value to be studied and improved upon, removing "errors" from each iteration to enhance the quality of future trials. Ariadne's thread has no such mechanic, making all decisions arbitrarily. For example, the scientific method is trial and error; puzzle-solving is Ariadne's thread.
Trial-and-error approaches are rarely concerned with how many solutions may exist to a problem, and indeed often assume only one correct solution exists (as in a scientific formula). Ariadne's thread makes no such assumption, and is capable of locating all possible solutions to a purely logical problem.
In short, trial and error approaches a desired solution; Ariadne's thread blindly exhausts the search space completely, finding any and all solutions. Each has their appropriate distinct uses. They can be employed in tandem - for example, although the editing of a Wikipedia article is arguably a trial-and-error process (given how in theory it approaches an ideal state), article histories provide the record for which Ariadne's thread may be applied, reverting detrimental edits and restoring the article back to the most recent error-free version, from which other options may be attempted.

by **Steve K** » Fri Jan 26, 2007 4:20 pm

Every technique that produces an elimination can be taken one step further and viewed as a proof by contradiction:

{set of conditions that are true} forbid A, therefor:
A forbids {set of conditions that are true}, but this is impossible as {set of conditions that are true} are true.

Every technique involves using just the rules of the game as many times as needed.

Ariadne's Thread can be thus applied to every possible technique, as it uses the rules (axioms), and if it reaches a contradiction, it has proven the original assumption false.

Of course, one may object, as one would have to have foreknowledge that the thread would prove false. But, I did not say:
Choosing a technique is equivalent to choosing Ariadne's Thread. Clearly, that is the rub.

by **udosuk** » Sat Jan 27, 2007 7:33 am

In my impression "Ariadne's Thread" refers to the following brute-force approach:

Save the current state. Start from the first candidate X of the first cell A, assume A holds X, and do all the basic moves (the player can config which basic moves are included). If a contradiction is reached, reload the state, and eliminate X from A, and try the next candidate in A, or proceed to the next cell if all the candidates are tested. If the assumption A=X leads to the solution, you can either stop searching or record the solution and reload the state, eliminate X from A and do the same (to check for multiple solutions etc). If you get stuck (neither a contradiction nor a solution), then you reload the state, but don't eliminate anything, and proceed with the next candidate/cell...

Pattern-based techniques, on the other hand, relies on the skill of observing candidate patterns on the grids... For example, if you scan the grids for cells hold only 1 candidate, you can find naked singles... Similarly, if you scan each row/column/box and look at how candidates are distributed, you can find hidden singles or naked/hidden subsets... If you just focus on the distribution of any particular digit over the grid (or if you use the "filter" feature in some programs), you can find x-wings, swordfish or apply colors etc... Or, even if you just focus on cells holding exactly 2 candidates, you can find xy-wings this way...

All these observation methods give us a more solid way to progress about the solving of a Sudoku puzzle... Forcing chains/contradiction nets etc, have no standardize way (or I'm not aware) to follow... You just pick a cell, assume a value and see if it results in a contradiction quickly... If you're lucky than you can make the elimination... To me it's not an elegant approach to solve a Sudoku...

As an analogy, think about a soccer team who just keep kicking long balls forward and hope the opposite defenders make a mistake for their own striker to scrap through a goal... Or one that use short passes and dribbling skills to steadily push the ball towards the goal, carefully keeping procession of the ball the whole time... The former team might be exciting to watch and can score a goal without too much effort but the latter approach is surely the more elegant way to win a game... To me forcing chains/nets are the former strategy and pattern based moves are the latter...

Just putting my 2 cents in...

by **Steve K** » Sun Jan 28, 2007 2:34 am

gurth wrote:By strategy I mean this: I don't TRY anything (no trial and error), and I make NO errors (no trial and error). What I do is create a MASTER PLAN: determine a precalculated sequence of steps which will lead to solution. The steps are all decided on before any of them are "tried" or put into practice. And these steps are all part of an organic whole. It's no longer a case of "Do what you can and hope that some unforeseen opportunity will appear."

udosuk wrote:Pattern-based techniques, on the other hand, relies on the skill of observing candidate patterns on the grids... For example, if you scan the grids for cells hold only 1 candidate, you can find naked singles... Similarly, if you scan each row/column/box and look at how candidates are distributed, you can find hidden singles or naked/hidden subsets... If you just focus on the distribution of any particular digit over the grid (or if you use the "filter" feature in some programs), you can find x-wings, swordfish or apply colors etc... Or, even if you just focus on cells holding exactly 2 candidates, you can find xy-wings this way...

All these observation methods give us a more solid way to progress about the solving of a Sudoku puzzle... Forcing chains/contradiction nets etc, have no standardize way (or I'm not aware) to follow... You just pick a cell, assume a value and see if it results in a contradiction quickly... If you're lucky than you can make the elimination... To me it's not an elegant approach to solve a Sudoku...

Seems to me that gurth is saying that he has a standardized manner of investigation.

All the patterns that you describe are a subset of a larger whole, as Myth Jellies has noted previously in his description of AIC.

Use of a unifying model to investigate sudoku makes a lot of sense.

For example, the fact that an X wing is precisely the same animal as a naked pair is not immediately obvious, but if one truly considers the precise information each of these two techniques considers, and the deductions one can make from each - they are equivalent in every possible logical respect.

by **Steve K** » Sun Jan 28, 2007 2:57 am

BTW - the soccor team analogy is fantastic. But let us take it a bit further.

One might teach the team a few patterns to use, types of plays to employ. These patterns are useful, and helpful in producing a few elegant wins. Nevertheless, situations will occur that do not fit into the plays presented. Therefor, one would be remiss in not teaching the ideas that are really behind the plays. Then, if a condition occurs that does not allow a predesigned play but does allow the application of the general ideas, the team can still successfully create play.

To me, AIC (forbidding chains), are the general idea behind the specific plays. Since the list of specific plays is prohibitively large, it is not likely I can ever learn each specific play. If I understand the underlying logic clearly, I need know NONE of them, as I can instead create a custom attack to each specific condition.

The approach I prefer is both: Know some specific plays. Know the theory behind them. (It is useful if it is just one theory behind them all).
Use prn.

Why both?

To limit one's investigation to only predesigned patterns misses a lot of elegant manners to solve really tough puzzles.

To limit one's investigation to only new theoretical derivations without recognizing some easy patterns misses a lot of time saving devices to solve a great many puzzles.

Contradiction nets, as I understand them, can also be used as a unifying theory (as can Ad's Thread). To me, they are not the best language choice for such a unifying theory.

Language choices, although arbitrary, are significant - as language is both a help in communication, but also often serves to obfuscate.

I suspect we are more in agreement than you may believe.

by **udosuk** » Mon Jan 29, 2007 3:08 am

Steve K wrote:I suspect we are more in agreement than you may believe.

Yes, I realise that... Actually I agree that it would be a pretty nice thing if we understand the underlying principle of the sudoku logic and apply it to create moves as we solve them... As long as they're done elegantly (e.g. a 10-cell AIC/forcing chain involving 5 candidates which cracks the puzzle into singles is IMHO not elegant even though it is the quickest way to solve a puzzle, but it might be the best option if you're in a race, or the only option if it's a diabolical puzzle)...