Chained APE

Overkill · Posted: Thu Feb 01, 2007 8:59 am Post subject: Chained APE

Hello!

Implementing yet another sudoku app I implemented several strategies (i found and understood) for a solver/generator/help-system. Reading (E)APE I thought about combining the logic of XY Chains with APE.

Within a chain like AB-BC-CD I call A the unchained candidate of the first cell and D the unchained candidate of the last one. A better naming is welcome.

The logic of Chained APE (CAPE) is: If you can find a XY Chain that
- the first cell of the chain shares its "unchained" candidate A with X and
- the last cell shares its unchained candidate B with Y
then the combination A+B can be excluded for APE on X & Y.
If X would be A, the chain forces its last cell to be B and thus Y can not have Candidate B.

Obviously, the chain can be of odd or even length (different as in pure XY Chains) and the rules of APE and EAPE should be applied, also.

Using Chained APE I could solve #87 and #91 of the top 95 puzzles - see my test case dump:

Ruud · Site Admin

Although I see the logic working in your technique, it may be too complicated for the human player. Your user name is well chosen. Smile

Here is an alternative view, using the same cells:

1. If r3c2<>3 => r2c2=3.
2. If r3c2=3 => (r2c2<>3) r3c7=4 => r3c5=9 => r2c6=4 => (r2c2<>4) r2c1=1 => r2c2<>1 : r2c2=9

Because 1. and 2. cover all cases, r2c2 is reduced to {3,9}

Personally, I prefer this method because it does not require the elaborate administration that APE variants need.

Please be aware that APE is closely related to ALS. Embedding ALS into chains is common practice for advanced solvers.

Ruud
_________________
Meet me at sudocue.net

Overkill · Posted: Fri Feb 02, 2007 12:41 pm Post subject:

Thanks for Your reply. This reduction is *very* nice and short - but hasn't it a bit of trial and error to get there?
Question

Or is there a way to tell in advance that to check "what if a is a candidate and what if its not" will result in an reduction of any cell. Was it an educated guess or is there some strategy i did not see yet.

btw.: I am currently implementing ALS-strategies and thought I've read that APE and ALS are closely related several times I can not see the relation. (ok, its a three letter strategy starting with A Wink

- but there should be more)
maybe I should scan the forum for camparisons or start a new threat on that relationship...