dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

AICs vs. Forcing Chains

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology
View previous topic :: View next topic  
Author Message
daj95376



Joined: 23 Aug 2008
Posts: 3854

PostPosted: Tue Jul 21, 2009 8:26 am    Post subject: AICs vs. Forcing Chains Reply with quote

I've had something on my mind for awhile now, and decided the only way to get beyond it is to share it. I doubt if it's anything new, but I don't recall seeing anyone else express this opinion.

First off, let me say that I use and am a strong supported of AICs. I find them to be a convenient and effective way to present logical relationships. Second, there are those who support AICs but will bad-mouth Forcing Chains in the same breath. I'm writing this to put a damper on their position.

Code:
Note 1: AICs have a bidirectional property.

Note 2: Forcing Chains are based on the premise that at least one stream must be true.

Let's see where this can take us.

Code:
 puzzle provided by Keith and PM+AIC provided by Norm
 .------------------.------------------.------------------.
 | 39    237   4    | 28    6     589  | 359   1     78   |
 | 6     127   79   | 3     279   1589 | 59    4     78   |
 | 5     137   8    | 179   4     19   | 39    2     6    |
 :------------------+------------------+------------------:
 | 2     5     6    | 14    39    14   | 7     8     39   |
 | 7     9     3    | 5     8     2    | 1     6     4    |
 | 4     8     1    | 79    379   6    | 2     5     39   |
 :------------------+------------------+------------------:
 | 8     37    5    | 49    1     349  | 6     79    2    |
 | 1     4     29   | 6     29    7    | 8     3     5    |
 | 39    6     279  | 28    5     389  | 4     79    1    |
 '------------------'------------------'------------------'

 (7=9)r2c3 - (9)r8c3 = (9)r9c13 - (9=7)r9c8 - (7)r7c8 = (7)r7c2; r123c2 <> 7

Code:
Step 1: Split the AIC at a strong inference.

   1a) (7=9)r2c3 - (9)r8c3
   1b)                     =
   1c)                       (9)r9c13 - (9=7)r9c8 - (7)r7c8 = (7)r7c2

Code:
Step 2: Use Note 1 to rewrite right-to-left interpretation of (1a) as left-to-right.

   2a) (9)r8c3 - (9=7)r2c3
   2b) =
   2c) (9)r9c13 - (9=7)r9c8 - (7)r7c8 = (7)r7c2

Code:
Step 3: Add implications based on each stream.

   3a) (9)r8c3 - (9=7)r2c3                      => r123c2 <> 7
   3b) =
   3c) (9)r9c13 - (9=7)r9c8 - (7)r7c8 = (7)r7c2 => r123c2 <> 7

Since the results of Step 3 are based on a strong inference (3b) between the two streams, we can apply Note 2 because one of the streams must be true. So, at least in this case, the AIC can be viewed as the merging of two Forcing Chain streams by applying the above steps in reverse order.
Back to top
View user's profile Send private message
Myth Jellies



Joined: 27 Jun 2006
Posts: 64

PostPosted: Thu Jul 23, 2009 7:35 am    Post subject: Reply with quote

Idea The difference lies not in what is discovered, but how it is discovered.

An AIC is a meta-pattern.

I can find an AIC by finding sub-patterns.

These sub-patterns (bivalued cells, bilocated digits, ALS's, URs, etc) always possess the same weak and strong link charateristics no matter what puzzle I work on.

Thus, I can assemble these sub-patterns into an AIC meta-pattern and learn something new about the puzzle without ever making an assumption other than that the puzzle-maker was following his rules.

This is very similar to the process most people use to find a naked pair. One usually sees the first ab-bivalue cell sub-pattern and then looks for an appropriately located second ab-bivalue cell to complete the pattern. No assumptions are needed during the entire process. Not surprising really since a naked pair is an AIC loop.

A forcing chain relies on you making assumptions to start it off. Comparing an AIC to a forcing chain is the same as comparing someone who recognizes a naked pair and uses it to make a deduction to someone who has to assume both cases of one of the naked pair bivalue cells and sees what happens to find the same result.

Thus, an AIC maker is looking for patterns that fit a pre-existing theory, while the forcing chain-ist is using ad hoc assumptions to prove things on the fly.

In addition, an AIC maker can learn to recognize and use new sub-patterns and gain the sense of satisfaction that that brings. The forcing chain-ist is limited improvement-wise to picking a good start point, which is very similar to the dilemma faced by those who utilize Ariadne's Thread-type algorithms to solve puzzles.

I'm not meaning to bad-mouth forcing chains. Rather I am just pointing out that solving puzzles in that way leaves little room for improvement, and thus, hardly requires a discussion forum.
Back to top
View user's profile Send private message
daj95376



Joined: 23 Aug 2008
Posts: 3854

PostPosted: Thu Jul 23, 2009 3:53 pm    Post subject: Reply with quote

I abhor getting into a discussion about semantics. An AIC says nothing about how the user found the final relationship. All it says is that starting at one end and proceeding to the other end leads the reader through all of the sub-patterns used. If anything, a forcing chain at least gives the reader an idea of where the user started.

For example, an XY-Wing is a very common sub-pattern that's described (in this forum) as vertex, pinchers, and eliminations -- in that order. This is definitely a forcing chain description. However, this description can't be written as an AIC. Does this mean that everyone who starts by looking for the vertex in an XY-Wing is wrong ... or that they can't transcribe it into an AIC later?

Moving along and using the AIC from above ...

Code:
(7=9)r2c3 - (9)r8c3 = (9)r9c13 - (9=7)r9c8 - (7)r7c8 = (7)r7c2; r123c2 <> 7

you wrote:
Alternating Inference Chain (AIC) is a chain which starts with an endpoint candidate which has a strong inference on the next candidate, which has a weak inference on the next candidate, which has a strong inference on the next candidate, and so on alternating weak and strong inferences until it ends with a strong inference on the final candidate at the other endpoint. The nodes of an AIC are really just the candidate premises themselves.

...

Deductions
Quite simply, at least one or the other (possibly both) of the two endpoint candidates (or candidate premises) of an AIC is true. Any deductions that you can make based on that are valid. This tends to produce the best results if the endpoints either share a group, or if the endpoints involve the same candidate. When your chain endpoints satisfy one of those conditions, it is time to check for any deductions.


This sure sounds like the above AIC deduction is derived from ...

Code:
[r2c3]=7 => [r123c2] <> 7

-or-

[r2c3]<>7 via the chain => [r7c2]=7 => [r123c2] <> 7


In my discussion above, I did not say that the strong link used to split the AIC couldn't be the first!!!

BTW: How would you write the (ERI) situation in [b7]? I would write it as ...

(9)r89c3 = (9)r9c13

... if I were to try and make it work bidirectionally in an AIC. This issue doesn't arinse in a forcing chain.
Back to top
View user's profile Send private message
wapati



Joined: 10 Jun 2008
Posts: 472
Location: Brampton, Ontario, Canada.

PostPosted: Fri Jul 24, 2009 4:48 am    Post subject: Reply with quote

daj95376 wrote:
For example, an XY-Wing is a very common sub-pattern that's described (in this forum) as vertex, pinchers, and eliminations -- in that order. This is definitely a forcing chain description. However, this description can't be written as an AIC. Does this mean that everyone who starts by looking for the vertex in an XY-Wing is wrong ... or that they can't transcribe it into an AIC later?


I start at ends looking at any pattern. That is how I solve puzzles.

I might turn a finned-sword into a normal jelly, that is my transcribe.

From what I have seen, most methods I use can be WRITTEN as forcing chains, I don't see them that way, or find them that way.
Back to top
View user's profile Send private message
Myth Jellies



Joined: 27 Jun 2006
Posts: 64

PostPosted: Fri Jul 24, 2009 6:36 am    Post subject: Reply with quote

The issue is that when you describe an AIC construct via a forcing chain, you give the very natural impression that you plugged in one truth value and followed its implications along, then you plugged in the other value and did the same thing; and where the two agreed you had your deduction.

The reality is you may have found it like I do, and made no such assumptions; but try explaining that to a bunch of newcomers. I have many times and it is just not easy when their primary exposure to the concept is "if you assume x then it leads to y, and if you assume not x it leads to y, therefore y"

Quote:
For example, an XY-Wing is a very common sub-pattern that's described (in this forum) as vertex, pinchers, and eliminations -- in that order. This is definitely a forcing chain description. However, this description can't be written as an AIC. Does this mean that everyone who starts by looking for the vertex in an XY-Wing is wrong ... or that they can't transcribe it into an AIC later?


Actually, I'd call your xy-wing a pattern and not a forcing chain description at all. Your vertex and pincers sub-patterns, and I'd say that they map quite readily into an AIC. You can even use a vertical link to allow you to indicate which element you saw first in your discovery process. I do this all the time with my more complex AIC nets when I think such information might be of interest.

Code:

   vertex

  (a)r1c1 - (a=c)r1c9  pincer1
  ||                               => r1c23,r2c789 <> c
  (b)r1c1 - (b=c)r2c2  pincer2


Quote:
BTW: How would you write the (ERI) situation in [b7]? I would write it as ...
(9)r89c3 = (9)r9c13

For a strong-only hinge/ER subpattern, that is the best way. The reason being is that if you managed to form an AIC loop, then you can change every link in the loop to a conjugate link (both strong and weak). When you change that to a conjugate link, you can eliminate (9)r9c3 at the vertex of the hinge. The fact that (9)r9c3 shows up on both sides of this link makes this potential deduction more apparent.
Back to top
View user's profile Send private message
storm_norm



Joined: 18 Oct 2007
Posts: 1741

PostPosted: Wed Sep 02, 2009 8:23 am    Post subject: Reply with quote

Quote:
When you change that to a conjugate link, you can eliminate (9)r9c3 at the vertex of the hinge. The fact that (9)r9c3 shows up on both sides of this link makes this potential deduction more apparent.

Myth Jellies,
do you have an example where the value in the ERI cell is eliminated in a AIC loop?
Back to top
View user's profile Send private message
Myth Jellies



Joined: 27 Jun 2006
Posts: 64

PostPosted: Mon Sep 07, 2009 3:23 am    Post subject: Reply with quote

storm_norm wrote:
...do you have an example where the value in the ERI cell is eliminated in a AIC loop?


Not for a normal sudoku. The reason for that is there is always a shorter and usually simpler discontinuous AIC that eliminates the intersection (using the same subpatterns/candidates) that one tends to notice prior to seeing the loop.

I have used the concept in squiggly puzzles, though. There is a particular set of squiggly nonets that covers each corner and the outside edge cells with exactly 4 nonets. Thus you have practically built-in AIC hinge/group/ER type loops around the outside edge. You can use this property to show that all the digits that occupy the cells in the four corners must be the same digits that occupy the cells in those four nonets that do not lie on an outside edge.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group