Alternating Inference Chains

Advanced methods and approaches for solving Sudoku puzzles

Postby wintder » Wed Jun 20, 2007 3:05 am

I thank you for your post on AIC. I am just starting to look at it and got lost on the example below. There are two "B"s missing and a "C" as well as the end link of the AIC. If I knew what I was doing I could figure it out, but I don't, sigh.


Myth Jellies wrote:Next is a recent Ruud Daily Nightmare
Code:

ALS example
*-----------*
|.6.|5..|.1.|
|...|3..|..4|
|..8|.9.|2..|
|---+---+---|
|4.7|2..|...|
|.5.|.7.|.8.|
|...|..9|1.7|
|---+---+---|
|..3|.4.|6..|
|1..|..7|...|
|.8.|..5|.2.|
*-----------*
*--------------------------------------------------------------------*
| 2379 6 49 | 5 28 48 | 3789 1 389 |
| 259 179 159 | 3 1268 168 | 589 79 4 |
| 35 14 8 | 7 9 14 | 2 356 356 |
|----------------------+----------------------+----------------------|
| 4 A139 7 |-2 -1568 -1368 | 359 3569 3569 |
|A69 -5 A169 | 146 7 B36 | 349 8 2 |
| 8 23 26 | 46 56 9 | 1 3456 7 |
|----------------------+----------------------+----------------------|
| 59 79 3 | 18 4 2 | 6 579 18 |
| 1 249 24569 | 689 36 7 | 34589 3459 3589 |
| 679 8 469 | 169 136 5 | 3479 2 139 |
*--------------------------------------------------------------------*
A3=A(1&6&9)-B6=B3

alternate notation when you don't have a picture
3[r4c2,r5c13]=(1&6&9)[r4c2,r5c13] - 6[r5c6]=3[r5c6]
sparse notation (non-endpoint candidate premise or location given only when changed)
3[r4c2,r5c13] = (1&6&9) - 6[r5c6] = 3[r5c6]

The second candidate premise (1&6&9) asks do the three cells marked with a B contain 1, 6, and 9? If that is true, then since all the 6's in B lie on row 5, the weak inference with other 6's in the row would apply. The chain means that all the cells seeing both C and A cannot be 3's.
wintder
 
Posts: 297
Joined: 24 April 2007

Postby Myth Jellies » Wed Jun 20, 2007 6:56 am

Thanks for the heads up. Fixed bad comments. Replaced my goofy notation with the Eureka notation.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby wintder » Wed Jun 20, 2007 7:48 am

I understand your post now.

It was relevant and very good.

Thanks Myth Jellies!
Last edited by wintder on Fri Jun 29, 2007 12:52 am, edited 2 times in total.
wintder
 
Posts: 297
Joined: 24 April 2007

Postby RW » Wed Jun 20, 2007 8:02 am

windter wrote:I regret my posting because your "excellant post for newbies" AIC post is not now readable,
in the sense, discernable to most people. It used to be very good, maybe is still good, I cannot read it.

Don't give up quite yet. Here's the old and the new version of the chain in Myth's first example:

Code: Select all
alternate notation when you don't have a picture
8[r9c6]=8[r9c7] - 5[r9c7]=5[r8c8] - 5[r3c8]=5[r3c5] - 8[r3c5]=8[r3c2] - 8[r1c3]=8[r8c3]

Eureka notation:
(8)r9c6 = (8-5)r9c7 = (5)r8c8 - (5)r3c8 = (5-8)r3c5 = (8)r3c2 - (8)r1c3 = (8)r8c3


If you look at that for a few seconds you should understand Eureka notation well enough to follow the post.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby wintder » Wed Jun 20, 2007 8:26 am

Thanks RW.

Edited to add:


Thanks Myth Jellies.


Eureka notation
(3=1&6&9)r4c2,r5c13 - (6=3)r5c6

I now get it, thanks both!
wintder
 
Posts: 297
Joined: 24 April 2007

Postby coloin » Fri Oct 19, 2007 10:07 pm

Steve K has apparently put forward a theory to ? solve the "Easter Monster" puzzle with AIC on Eureka here

Code: Select all
1..|...|..2
.9.|4..|.5.
..6|...|7..
---+---+---
.5.|9.3|...
...|.7.|...
...|85.|.4.
---+---+---
7..|...|6..
.3.|..9|.8.
..2|...|..1



   1      A478     34578   | 3567    3689    5678    | 3489   I369     2
  L238     9      L378     | 4      K12368  K12678   |J138     5      J368
   23458  A248     6       | 1235    12389   1258    | 7      I139     3489
 --------------------------+-------------------------+-----------------------
   2468    5       1478    | 9       1246    3       | 128    H1267    678 
   234689 B12468   13489   | 126     7       1246    | 123589 H12369   35689
     2369 B1267    1379    | 8       5       126     | 1239    4       3679
 --------------------------+-------------------------+-----------------------
   7      C148     14589   | 1235    12348   12458   | 6      G239     3459
  D456     3      D145     |E12567  E1246    9       |F245     8      F457
   45689  C468     2       | 3567    3468    45678   | 3459   G379     1


(27)r13c2=(27-16)r56c2=(16)r79c2-(16)r8c13=(16-27)r8c45=(27)r8c79-(27)r79c8=(27- 16)r45c8=(16)r13c8-(16)r2c79=(16-27)r2c56=(27)r2c13 - loop

Note that nodes marked A, C, D, F, G, I, J and L are all AALSs.


Please could someone run it by me again !!

Will this technigue apply to other similar puzzles ?

C
coloin
 
Posts: 1632
Joined: 05 May 2005

Postby ronk » Sat Oct 20, 2007 2:26 am

coloin wrote:Will this technigue apply to other similar puzzles ?

It's an available opening move in these 14 non-equivalents selected from Ocean's post here.

Code: Select all
1.......2.3..4..5...6...7.....1.3....4..8..9....4.5.....7...1...8..3..4.2.......6 # ER=9.9
1.......2.3..4..5...6...7.....1.4....8..7..4....5.8.....7...6...5..3..8.2.......1 # ER=9.9
1.......2.3..4..5...6...7.....1.3....4..6..8....9.4.....7...1...5..9..3.2.......6 # ER=9.8
1.......2.3..4..5...6...7.....1.3....8..7..3....5.8.....7...6...5..3..8.2.......1 # ER=9.8
1.......2.3..4..5...6...7.....1.4....4..7..8....9.5.....7...6...5..9..3.2.......1 # ER=9.8
1.......2.3..4..5...6...7.....1.4....8..7..4....5.3.....2...6...4..5..3.7.......1 # ER=9.8
1.......2.3..4..5...6...7.....1.4....8..9..4....5.8.....2...1...5..3..8.7.......6 # ER=9.8
1.......2.3..4..5...6...7.....1.3....8..5..4....4.9.....7...1...4..3..8.2.......6 # ER=9.7
1.......2.3..4..5...6...7.....1.4....5..2..4....5.3.....2...6...4..8..3.7.......1 # ER=9.6
1.......2.3..4..5...6...7.....1.3....4..2..3....5.4.....7...6...5..8..4.2.......1 # ER=9.5
1.......2.3..4..5...6...7.....1.3....4..7..8....4.5.....7...6...8..5..3.2.......1 # ER=9.5
1.......2.3..4..5...6...7.....1.3....5..7..4....4.8.....2...1...4..8..3.7.......6 # ER=9.5
1.......2.3..4..5...6...7.....1.3....5..7..8....5.4.....7...6...4..5..3.2.......1 # ER=9.5
1.......2.3..4..5...6...7.....1.4....8..2..4....5.8.....2...6...4..3..8.7.......1 # ER=9.5

[edit: changed link to post instead of to page]
Last edited by ronk on Sat Feb 09, 2008 8:44 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby AW » Sun Oct 21, 2007 6:49 pm

I was going to post this on Eureka, but the boards are down this week-end.

Stephen's deduction is anything but a conventional AIC. In fact, without extending conventional AIC wisdom, it's not an AIC at all. More like an alternating set chain. The problem with interpreting it as an AIC is that it doesn't rely on the same kinds of inferences. Conventional AICs alternate between "not both false" and "not both true" inferences, but these notions don't apply here. In this new case, the AIC does not transport one truth : it transports 2 truths at the same time. Basically, it extends the chain patterns to accounting for inference sets that transport two truths at once. And it could be further extended to an arbitrary number of truths.

There are generic formulas for shaking up sets, but I don't want to elaborate on those. Just for example, here's the formula to split a set :
AB{m:n} - A{x:y} = B{m-y:n-x}, with any required adjustments to keep all variables within a reasonable range of values (there's the obvious lower bound of 0, the obvious upper bound of the number of possible truths in the set, etc.).
Meaning : if you extract from set 'AB', that has at least 'm' truths and at most 'n' truths in it, a subset 'A' that has at least 'x' truths and at most 'y' truths, then the remaining subset 'B' must have at least 'm-y' truths and at most 'n-x' truths (plus adjustments).

To get a general idea of the principle, here are a couple examples :

In a very basic AIC case (where all the strong inferences are conjugates, and all the weak inferences are same-cell or same-unit-number) :
A strong inference is 'A = B' where the AB set is {1:1} (exactly one is true).
A weak inference is 'A - B' where the AB set is {0:1} (at most one is true).
So the sets push around the truth like so :
Either A is {0:0}, and we get : A{0:0} = B{1:1} - C{0:0} = D{1:1} - E{0:0} ... = Z{1:1}
Or A is {1:1}, and we get : A{1:1} = B{0:0} - C{0:1} = D{0:1} - E{0:1} ... = Z{0:1}

In Stephen's deduction (where the case is pertty basic for N=2, all strong inferences correspond to pairwise conjugates) :
A strong inference is 'A = B' where the AB set is {2:2} (each holds exactly two true candidates).
A weak inference is 'A - B' where the AB set is {0:2} (each holds at most two true candidates).
The A set has three possibilities :
Either A is {0:0}, and we get : A{0:0} = B{2:2} - C{0:0} = D{2:2} - E{0:0} ... = Z{2:2}
Or A is {1:1}, and we get : A{1:1} = B{1:1} - C{0:1} = D{1:2} - E{0:1} ... = Z{1:2}
Or A is {2:2}, and we get : A{2:2} = B{0:0} - C{0:2} = D{0:2} - E{0:2} ... = Z{0:2}

The applicable AIC deductions in the "N=2" case are :
Strong loop : If A and Z are actually the same set, then A must be a {2:2} set (since AZ is either {2:2}, {2:3} or {2:4}). It's the great attractor : any truths taken out of A transport back to it.
Regular loop : If there is a weak inference between A and Z, then AZ must be a {2:2} set, and recursively all inference sets in the chain must be {2:2}. Blind justice, all inferences are assimilated.
Weak loop : If there is a set X such that A - X - Z (weak inferences to A and Z), then ... well this one is funny : we conclude that X is {0:1} (the gray hole : A and Z siphon truths away from X but they do so independently; any truths taken out of A transport to Z, but in the worse case both hold one truth and these target the same candidate in X, so X is still left with one truth.)

In the general case, for sets 'N' : we have strong inferences of at least N truths, and weak inferences of at most N truths.
The strong loop forces A into a {N:N} set.
The regular loop forces all inference sets into {N:N} sets.
The weak loop makes any target set into a {0:N/2 rounded down} set. This conveniently works out to {0:0} when N=1.

Well known patterns can usually be interpreted as cases of set transport :
Basic chains have already been looked at, when N=1. I'll only add that ALS and other original means of transport fall under the set-shaking formulas as well.
Interactions and singles are single inference set patterns with N=1 : AB{1:1} - (A{1:1} = B{0:0}.
Bigger set patterns are single inference set patterns with N>1. For instance, a swordfish relies on AB{3:3} - A{3:3} = B{0:0}.
Set overlap wreaks havoc in all cases, but can be tractable : like the X in the weak loop, some information can still be used, although I usually can't get my head around it.

Stephen's deduction is a simple case of chaining sets where N=2. Its simplicity is what makes it amazing : there are only two truths transported, the weak(cover) sets consistently alternate between cell pairs and boxes, and the strong(base) sets consistently alternate between number pairs in rows and columns, and there is no nasty overlap.
Here's a matrix representating the deduction as both a chain and a set problem, for those who are familiar with these constructs :
Code: Select all
       | (27)b1    r56c2     (16)b7    r8c45     (27)b9    r45c8     (16)b3    r2c56
-------+-------------------------------------------------------------------------------
(27)c2 |(27)r13c2 (27)r56c2
(16)c2 |          (16)r56c2 (16)r79c2
(16)r8 |                    (16)r8c13 (16)r8c45
(27)r8 |                              (27)r8c45 (27)r8c79
(27)c8 |                                        (27)r79c8 (27)r45c8
(16)c8 |                                                  (16)r45c8 (16)r13c8
(16)r2 |                                                            (16)r2c79 (16)r2c56
(27)r2 |(27)r2c13                                                             (27)r2c56
-------+-------------------------------------------------------------------------------
       |(Put the column remainders down here, they are the eliminated.)

Where rows are "at least two" sets (well, actually, "exactly two" in this case), and columns are "at most two" sets.


As a side note, Stephen's alternations between cell-box and row-column suggest this pattern has affinities with braiding. Perhaps an interesting pattern can emerge from studying this.
AW
 
Posts: 27
Joined: 31 January 2007

Postby Steve K » Sun Oct 21, 2007 7:47 pm

In order to chain the deduction using AIC properly, one probably needs to consider two simul chains.

First, for all cases where 2 candidates are limited to four locations within a group, one proper way to use this relationship as an AIC fragment is:
((Can1)loc12=(Can2)loc12)=(Can1&2)loc34

Using this piece of information, construct two simul chains, both very similar to each other:

Generally, (A=B)=(A&B)-(C=D)=(C&D).....

and

(A&B)=(A=B)-(C&D)=(C=D)

One needs to alternate not only the =,- as with standard AIC, but also the contained =,&. One chain leads with contained= and ends with contained & while the other leads with & and ends with contained &. This is more or less the meaning behind saying that it really is a hidden pair loop, as one proper way to chain hidden pairs is this way.

The chain ends (all of them) will be completely symmetric, and will have simultaneous:

(A&B)loc12=-(A=B)loc34 and (A=B)loc12=-(A&B)loc34. There are three ways to satisfy this set of proven conditions:

(The truth table is built upon the contained Booleans, not A,B)

T,F,T,F
F,T,F,T
F,T,T,F

(Note T,F,F,T is clearly impossible)
The first two clearly will justify all the eliminations, while the latter is possible only if both A&B exist at loc1234. This still justifies the eliminations.

Note, although a hidden pair is (A&B) at loc 12, a hidden pair loop really wants the more general partitions: (A&B)=(A=B), and that both partitions co-exist as chainable fragments.

In any event, sans using a matrix to prove the point, this is the best description that I have at this point.
Steve K
 
Posts: 98
Joined: 18 January 2007

Postby ttt » Sat Nov 10, 2007 4:48 pm

Withdraw... :D

ttt
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

Re: Alternating Inference Chains

Postby JasonLion » Wed Mar 23, 2011 6:59 pm

Thanks to Bob in TX we now have some additional posts from this topic made between Nov 2007 and July 2009.

PDF of page 3
PDF of page 4
User avatar
JasonLion
2017 Supporter
 
Posts: 621
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Previous

Return to Advanced solving techniques