The New Sudoku Players' Forum

[Jeff]

Hi castalia, This is a continuation of the discussion on "trial & error" (T&E) from this post.

To determine the complexity of a technique, simply count the number of operations required to carry it out. If that number is proportional to a simple power of N, the complexity is polynomial; if it's some number to the Nth power, that makes the technique exponential.

Full backtracking is the best example of an exponential technique in sudoku. Limited backtracking (e.g. Nishio) can be polynomial, but doesn't always succeed. Looking for pairs is polynomial (proportional to N^2).

The presence of backtracking is perhaps the tell-tale sign of any trial and error (i.e. exponential) technique.

Thank you for the explanation. According to the definition above, is it appropriate to say that:

• "Trial" itself doesn't render a technique being T&E.
  
• All techniques that don't use backtracking as part of their identification processes are non-T&E, including all pattern recognition techniques such as BUG, swordfish, b/b plot, advanced colouring and POM.
  
• Techniques that use backtracking could be T&E or non-T&E, depending upon the degree of backtracking required. The degree of backtracking can be determined by the number of operations; as being polynomial or exponential.
  
• Forcing chain, by itself, cannot be considered as T&E or not, but techniques for identification of forcing chains could be T&E or non-T&E depending on the degree of backtracking. If this is the case, could you give an example each, techniques that you would consider T&E and non-T&E according to the above definition.

Thanks with anticipation.

[Myth Jellies]

I'm not sure I buy the connection between T&E and an exponential number of operations.

For example, if I decide to search for candidates to exclude by baldly choosing each possible candidate in each cell and performing up to a constant 1000 basic puzzle solving operations after that selection unless I got a crash or the puzzle solved. I figure you have N**2 for the number of cells, and N for the possible number of candidates per cell. So this would only be a technique on the order of N**3, and thus logical? I might not solve every puzzle with this method, but I can sure get rid of a lot of candidates. Heck, 1000 was an arbitrary constant. I can always adjust it higher. It won't solve NxN puzzles when N gets large, but it will slaughter them when N = 9.

Perhaps I am missing a key concept here and my example doesn't apply, but I currently don't see an exponential order as being a necessary condition for declaring a technique T&E. I might buy that an exponential order is sufficient to declare a technique T&E, but that is a different argument.

[gsf]

its so easy to get sucked into this topic

the problem is you can weasel almost any activity in and out of trial and error

cycle detection and pattern recognition employ trial and error
but its a type of trial and error amenable to human solvers

iterating through all candidate values for all cells to see what works
with no other reasoning besides knowing that exhaustion will find a solution
may or may not be trial and error
but it definately is no fun for a human solver

[Myth Jellies]

I am just curious.

Why did trying to find a pattern, even a pattern of somewhat arbitrary length and content such as a bivalue xy chain, become equated with a trial that arbitrarily assumes either a cell's candidate is true or assumes a cell's candidate is false? When you look for an ab-bc-...-de-ea chain, you don't assume anything about the validity or invalidity of any candidate in any cell of that chain.

I mean, I had to try to find the puzzle in the Sunday paper--a trial of exponential order if ever there was one. Did this doom the puzzle to T&E before I hardly got started? Surely what the trial is trying to accomplish should count for something in our definition of T&E--or am I missing a key point. I'm open to changing my definition if someone can show me the error of my ways.

[Jeff]

cycle detection and pattern recognition employ trial and error.......

iterating through all candidate values for all cells to see what works
with no other reasoning besides knowing that exhaustion will find a solution may or may not be trial and error

Thanks for sharing your thoughts, gsf. Could you please elaborate:

• How does pattern recognition employ T&E?
  
• Why "iterating through all candidate values for all cells to see what works with no other reasoning besides knowing that exhaustion will find a solution" can be regarded as non-T&E?

[gsf]

• How does pattern recognition employ T&E?

one cycle detection algorithm is depth first search (DFS)
if you trace DFS in action you might see many chains that
lead to a dead end rather than a cycle
those dead end chains are the error part for cycle detection

• Why "iterating through all candidate values for all cells to see what works with no other reasoning besides knowing that exhaustion will find a solution" can be regarded as non-T&E?

I don't think that, but there have been arguments to that effect on
other T&E threads, like "you have to look at both the positive and
negative outcomes to be considered trial and error"

[Jeff]

one cycle detection algorithm is depth first search (DFS)
if you trace DFS in action you might see many chains that lead to a dead end rather than a cycle those dead end chains are the error part for cycle detection

Thanks gsf, Isn't that because you have no target of what to look for? For me, by following recognisable patterns, each pattern represents one chain and I won't run into any dead ends. Of course, that's another matter if you think it's T&E just to look for these patterns; everything including naked pair would then be T&E.

"you have to look at both the positive and negative outcomes to be considered trial and error"

I sense that you are merely expressing other people's viewpoint. Since you appear to understand the above statement, could you explain what positive outcomes and negative outcomes mean in this context? How does it relate to the statement "iterating through all candidate values for all cells to see what works with no other reasoning besides knowing that exhaustion will find a solution"? Can you shed more light with an example perhaps?

[castalia]

the problem is you can weasel almost any activity in and out of trial and error

cycle detection and pattern recognition employ trial and error
but its a type of trial and error amenable to human solvers

It's difficult to buy your argument. The nonrepetitive path and cycle detection algorithms described in Eppstein's paper execute efficiently (i.e. in polynomial time) and don't use trial and error at all.

Indeed, the term "trial and error" itself is likely the source of confusion since different people understand it to mean different things. That's why I think it's more constructive to focus on whether a technique (or set of techniques) operates in polynomial time, because such a perspective is mathematically precise and removes all ambiguity.

Exponential techniques, when applied in general to 9x9 sudokus, are beyond the capability of human solvers. Polynomial techniques, on the other hand, have the potential to be applied by humans, though they may be EXTREMELY challenging, especially before getting accustomed to them by repeated practice. But learning and mastering these more sophisticated techniques is one of the real delights of the game.

Is there a set of polynomial techniques which collectively solve all 9x9 sudokus? A fascinating question IMHO.

[tarek]

I was embriled earlier this month in similar discussion.


Trial in my book is easy to define: Any attempt to find a pattern/chain is a trial.......wether it was in the head or on paper

but what defines an ERROR. The previous discussion I was involved with suggests that if there was a CONTRADICTION encounterd in the TRIAL then it constitutes an error.

It helps sometimes to be Pedantic ( I love this word, a member used it in a similar argument) about this, & choose a simple well defined red line.

From here it seems that there are 2 emerging Red Lines.

1. Encountering a contradiction to prove an elimination
2. Exponentiality(Complexity) of the chain needed to prove the eliminaton.

Without a red line we'll carry on with this topic for ages & I'll tell you why:

1. double implicaton chains stop short of reaching a contradiction, one of the chains will definitely reach a contradiction, so are forcing chains T&E
2. Most of the patterns used as solving techniques are based on Forcing chains (Therefore involved in point 1).
3. If you encounter a contradiction in one branch of a forcing net, & The end result was in another branch of your net which hasn't reached a contradiction YET. can we say that you've done a T&E.
4.A helper program would show you a Logical explanation to reach a conclusion, however the program itself used an exponential complex (but faster) method to solve it & then backtracked from the end to the start to contsruct a simpler chain, is that T&E ?

[Jeff]

1. double implicaton chains stop short of reaching a contradiction, one of the chains will definitely reach a contradiction, so are forcing chains T&E

Hi Tarek, just one point. Judging from what you have described, it seems to me it's bifurcation you are talking about; not a double implication forcing chain. A double implication chain (singular) has 2 implication streams that start with each possibility in a cell, branch out in 2 paths and end up with the same deduction in a cell.

[gsf]

"you have to look at both the positive and negative outcomes to be considered trial and error"

I sense that you are merely expressing other people's viewpoint.

"..." meant I was
it was a quote but not an affirmation
I'm going back to coding
have fun defining trial and error

[tarek]

[quote="Jeff"]Judging from what you have described, it seems to me it's bifurcation you are talking about; not a double implication forcing chain[quote]

Hi Jeff,

The implication chain stops short of becoming a bifurcation, choosing a cell for the chain to end doesn't change the fact that one of the possibilities will ALWAYS end with a contradiction if it was allowed to propagate to the end & show all its implications.

Tarek

[Jeff]

The implication chain stops short of becoming a bifurcation, choosing a cell for the chain to end doesn't change the fact that one of the possibilities will ALWAYS end with a contradiction if it was allowed to propagate to the end & show all its implications.

Hi Tarek, Just to make it crystal clear.

Double implication forcing chain
A closed cycle that has 2 implication streams that start from one node and end in one node, eg.

r9c6=7 => r9c1=8 => r9c1<>7
r9c6=8 => r8c5=7 => r3c5<>7 => r3c1=7 => r9c1<>7
Therefore r9c1<>7

Single implication network
An open path that has one implication stream that starts with a candidate selected in one node and propagates until a contradiction is revealed, eg. one digit appears 2 times in a unit. This is the principle of a "backtest" (refer definition of a backtest here). There is currently no known technique for non-T&E identification of such an open path.

Correct me if I am wrong; I sensed that you are referring to single implication network in your post, but calling it a double implication chain.

[tarek]

r9c6=7 => r9c1=8 => r9c1<>7
r9c6=8 => r8c5=7 => r3c5<>7 => r3c1=7 => r9c1<>7
Therefore r9c1<>7

Hi Jeff,

I know all of that, The thread you started leaves no confusion

what I'm trying to say is this: unless it is a pseudopuzzle. All cells will have only one candidate & therefore using a double implication chain or ANY type of possibility streams starting in one cell carries with it the sense of "Wait a minute, I know this is logical but there can be no 2 occupants of the same cell".

Saying that a double implication stops short of a contradiction is also correct:
adding to the above example:

Code: Select all

r9c6=7 => r9c1=8 => r9c1<>7
r9c6=8 => r8c5=7 => r3c5<>7 => r3c1=7 => *r9c1<>7 => r9c9=5 => r1c9<>5 => r1c9=4 => r1c6<>4 => #r1c6=8
Therefore r9c1<>7  (if you stopped at *)
Therefore r9c1<>7  (if you stopped at #) & you have reached a contradiction.


you chose to terminate the cell at the same cell, who said that the implications stop there. one of the possibility streams if left to propagate (as a chain or net at whatever complexity) will eventually reach a contradiction. I know that at this point it stops being a double implication chain, but that is not the point I'm trying to say.

[Jeff]

r9c6=7 => r9c1=8 => r9c1<>7
r9c6=8 => r8c5=7 => r3c5<>7 => r3c1=7 => *r9c1<>7 => r9c9=5 => r1c9<>5 => r1c9=4 => r1c6<>4 => #r1c6=8
Therefore r9c1<>7 (if you stopped at *)
Therefore r9c1<>7 (if you stopped at #) & you have reached a contradiction.

Hi Tarek, I am sure you understand. Just as a matter of interest, if you have a double implication chain that implies r9c1<>7, why would you keep going on one of the implication streams.

On the other hand, if you just use the single implication network, you can prove r9c6<>8 (not r9c1<>7), by just using the second implication stream alone. But then, we already know that there is currently no known technique for non-T&E identification of a single implication network; which makes it irrelevant to our discussion of trial & error anyway.