Error Chains (new solve technique?)

Graeme · Posted: Mon Feb 13, 2006 9:11 am Post subject:

I'm enjoying the interesting points & discussion, all.

My program is a bit of a quest to make it as human as possible, which of course is mostly futile. But I'm building in things I think many humans would do, such as placing naked singles as soon as they appear. Indeed, it was this that led me to Error Chains (which I now know have been discovered before).

Also, from a discusion with tso on another forum, I'm fairly sure that Error Chains ARE Forcing Chains in reverse (ie they both come from the same puzzle state), however, IMHO there are cases such as the 2nd example above where Error Chains are much simpler than Forcing Chains for both human and programmed solvers. I doubt whether many human solvers use anything more than naked singles when testing implications of guessed candidates, in which case the Forcing Chain won't discover the possible candidate removal above.

splitline · Posted: Wed Mar 08, 2006 2:26 am Post subject: question about your algorithm.

I'm quite new to sudoku and i'm having trouble making sense of your algorithm. I would like for you to maybe go into a little more detial and/or show some code. Maybe you can post you program or something..

Thanks

Graeme · Posted: Wed Mar 08, 2006 8:05 am Post subject:

sure splitline,

This technique can be built as a standalone technique, or added into existing techniques that use single candidate guesses, such as forcing chains, and possibly XY chains (depending on how you've programmed it)

The basic idea is:

For each candidate in each cell (one at a time please Wink

1. Set the candidate value (this is the guess)
2. Test the implications of that placement - at it's simplest, this means doing what you normally do when you set a value: remove that candidate from other cells in the same groups, then place any naked singles, and repeat thiis step until no further changes are possible
3. In step 2, if at any stage you remove a candidate leaving no remaining candidates in a cell, you know the guess causes an error, so you can remove the candidate guessed in step 1, and move immediately to step 4
4. Restore the initial puzzle state, excluding any candidate removed in step 3

Hope that's clear.

rgds
Graeme