Error Chains (new solve technique?)

Graeme · Posted: Sun Feb 05, 2006 10:03 am Post subject:

Here are two examples of my Error Chain technique.

If placement of a candidate value removes all candidates from another cell, that candidate value can be removed.

If the candidate value in blue is set, then all candidates are removed from the cell shaded blue. So we can remove the {6} and {4} candidates in the cells shaded yellow.

Henk · Posted: Sun Feb 05, 2006 11:29 am Post subject:

The examples you just shown look a lot like Forcing Chains. The one on the top left is just plain forcing chains, a dual implications chain. The other example also is forcing chains, a triple implications chain.

I'm currious about your implementation of these techniques. And the visualisation you shown, is that coming from your program, or is it a hand-painted?

As you show it here, it is not backtracking.
_________________
Generate and solve Sudoku puzzles with Into Sudoku!

Graeme · Posted: Sun Feb 05, 2006 11:58 am Post subject:

Hi again, Henk.

No, Error Chains are nothing like Forcing Chains at all. (the caps below are to highlight the differences; I'm not shouting) Smile

Forcing Chains test EVERY candidate in a cell to determine if a certain value is set* in another cell regardless of initial candidate choice. Furthermore, Forcing Chains set that value in the OTHER cell.

Error Chains test ONE candidate to see if it removes all candidates from another cell. If it does, then it removes the candidate from the INITIAL cell.

* btw, Angus includes "if a candidate is removed from another cell regardless of initial candidate choice" in his definition of Forcing Chains. Even with this addition, the candidate value is still removed from the other cell, and not from the initial cell, like Error Chains.

And sorry, that pic is just a mock-up in PowerPoint.

Henk · Posted: Sun Feb 05, 2006 12:59 pm Post subject:

Graeme · Posted: Sun Feb 05, 2006 1:32 pm Post subject:

Henk, I think your link shows two good examples of Forcing Chains - one shows where a value is set in another cell regardless of initial candidate choice in the test cell, and the other shows where a candidate value is removed in another cell regardless of candidate choice in the test cell.

Of course, Forcing Chains are not restricted to test cells (AB in your diagrams) with just 2 candidate values, they could have all 9 possibilities for a 9 way implication chain!

I'm obviously not explaining myself clearly, so I'll try a different approach:

Error Chains and Forcing Chains and Nishio have these steps in common:
(1) Set a candidate value
(2) Set naked singles and remove candidates in the same groups
(3) Look for a condidtion
(4) Take an action if condition (3) exists

And here are the differences:

(1) Set a candidate value
Error Chains place a single candidate value
Forcing Chains place each candidate value one at a time, and repeat steps (1) to (3) for every candidate, before progressing to step (4)

(2) Set naked singles and remove candidates in the same groups
No difference here

(3) Look for a condidtion
Error Chains look for another cell with no candidates
Forcing Chains, after testing each candidate, look for another cell that has the same value set (or the same candidate removed) for every different candidate value set in step (1)

(4) Take an action if condition (3) exists
Error Chains remove the candidate from the cell in step (1)
Forcing Chains set the forced value (or removed candidate) from the cell in step (3)

I hope this shows more clearly that Error Chains and Forcing Chains are completely different things.

Graeme · Posted: Sun Feb 05, 2006 2:02 pm Post subject:

And a couple of other points from your last post, Henk:

Yes, the simple (pairs only) example of Error Chains does work like forcing chains in reverse, but the other example shows why this doesn't always work.

And thanks for the offer of using you program for screen captures. I'm designing my own of course, so I'll probably use that for my own help screens.

regards,
Graeme

Henk · Posted: Mon Feb 06, 2006 8:47 pm Post subject:

gsf · Posted: Mon Feb 06, 2006 9:08 pm Post subject:

tarek · Posted: Tue Feb 07, 2006 11:24 am Post subject:

I would put any method that uses conradiction to eliminate candidates(The method mentioned in this thread, subtypes of the forcing chains, subtypes of colouring, Nishio,........) closer to The Pure guessing end of the solution.......

I would exhaust all non-(contradiction elimination methods) before resorting to these methods.

They all employ logic (even Pure guessing), however using contradiction puts things in the grey zone next to T&E (Not saying that they are) & therefore avoided until necessary.

Tarek

Graeme · Posted: Tue Feb 07, 2006 1:28 pm Post subject:

Hi gsf & tarek,

IMHO, in order of least guesses to most ...

Nishio and Error Chains require guessing of one candidate at a time, in one cell at a time, to see if the required condition is met

XY-Chains require guessing one candidate at a time, in 2 cells at a time (to see if the chain works both ways, to allow candidate reduction in intersecting cells)

Forcing Chains required guessing every candidate in one cell at a time, to see if every guess candidate leads to a common outcome in a forced cell

And of course brute force trial & error allows unlimited guessing to find a solution, or not.

tarek · Posted: Tue Feb 07, 2006 3:11 pm Post subject:

gsf · Posted: Tue Feb 07, 2006 3:54 pm Post subject:

Ruud · Site Admin

From time to time, the old Logic vs. Guessing/T&E debate flames up again. I like the arguments, but to me it is a trivial debate.

A backdoor (Magic Cell we used to call it) has the same validity as a lucky guess. When it leads to a solution, it only proves there is a solution, not that there is only one solution.

However, a commonly used pattern recognition technique, Uniqueness Test and the lesser known BUG are based on the same principle.

When a single solution is presumed, any technique that finds it and which is based on this premise, is rooted in logic, whether it is a pattern recognition routine, a simple guess or a thorough search algorithm.

With the Nightmare players, who discuss them on the SudoCue forum, the uniqueness discussion is more important than the T&E vs. logic discussion. There are some players who refuse to use these techniques, others can't get enough of it.

On a separate note, we should not compare our programs too much with the pencil-and-paper guys. First, when they're visiting these forums, they're not entirely pencil-and-paper guys, are they? I've seen some die-hard manual solvers asking questions about how to use some features of a certain piece of software that I shall not name here, but it can be found in my signature...

Nevertheless, with the available tools, they do discover and develop new solving techniques, replacing N^4 algorithms with easier patterns with a more difficult name.

But we're pleasing a very small crowd here. The majority of players want easier sudokus, not more difficult. I had to use negative ratings to be able to add easier sudokus, which they will solve only by guessing. And they're having fun with it. For me, that's the most important part.

Ruud.
_________________
Meet me at sudocue.net

Henk · Posted: Tue Feb 07, 2006 8:10 pm Post subject:

Amen ruud!

gsf · Posted: Tue Feb 07, 2006 11:28 pm Post subject: