SudoCue Users Forum Index SudoCue Users
A forum for users of the SudoCue programs and the services of SudoCue.Net
 
 FAQFAQ   SearchSearch   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

AIC help

 
Post new topic   Reply to topic    SudoCue Users Forum Index -> Help Me! I'm stuck!
View previous topic :: View next topic  
Author Message
magician
Rookie
Rookie


Joined: 01 Apr 2007
Posts: 5
Location: UK

PostPosted: Sat Sep 29, 2007 2:06 pm    Post subject: AIC help Reply with quote

I am working through Andrew Stewarts book and it is great, but I was stumped by a recent puzzle. It is using AICS, I cant get my head round them, can anyone explain how the follwong is reached please? In simple terms.
Back to top
View user's profile Send private message
Ruud
Site Owner
Site Owner


Joined: 30 Dec 2005
Posts: 601

PostPosted: Sat Sep 29, 2007 6:45 pm    Post subject: Reply with quote

Hi magician,

Alternating Inference Chains allow you to make a logical connection between 2 remote candidates. The logical connection between 2 candidates is what we call inference.

There are 2 types of inference, identified by the - and = symbols:

- represents weak inference. When there is weak inference between two candidates, they cannot be true at the same time. In other words: if one of them is true, the other must be false. In circuit logic, we call this a NAND relationship.

= represents strong inference. When there is strong inference between two candidates, they cannot be false at the same time. In other words: if one of them is false, the other must be true. In circuit logic, we call this an OR relationship.

In a Sudoku grid, two candidates which belong to a single cell always have weak inference. There is only room for one of these candidates in the solution. However, if these are the LAST 2 candidates in that cell, they also have strong inference, because if they were both false, the cell would have no remaining candidate for the solution.

A similar relationship exists between candidates for the same number in a single row, column or box. The rule states clearly that exactly one of each number must go in a unit, so candidates for the same number in a unit always have weak inference, but they also have strong inference if they are the LAST 2 candidates for that number in that unit.

Suppose we have a pair of candidates with strong inference:
Code:
A = B

Now we know that A and B cannot be false at the same time.

Here is a second pair of candidates with strong inference:
Code:
C = D

This tells us that C and D cannot be false at the same time.

Now what if B and C belong to the same cell:
Code:
B - C

This tells us that B and C cannot be true at the same time.

These individual links are the building blocks of AICs. They really become effective when we combine them into a chain:
Code:
A = B - C = D

Since B and C cannot both be true, one of them must be false. If B is false, A must be true. If C is false, D must be true. So this short chain has revealed a relationship between A and D. One of them must be true.

Now let's go back to your example:

Row J has 2 candidates for number 3. They have strong inference.
Code:
3[J4] = 3[J6]


J6 and A6 belong to the same column. They cannot both be 3, so there's weak inference between these two candidates.
Code:
3[J6] - 3[A6]


A6 only contains candidates for numbers 2 and 3. One of them must be true.
Code:
3[A6] = 2[A6]


A5 and A6 belong to the same row. They cannot both contain number 2.
Code:
2[A6] - 2[A5]


A5 and J5 contain the last 2 candidates for number 2 in column 5.
Code:
2[A5] = 2[J5]


When combined, here is the complete AIC:
Code:
3[J4] = 3[J6] - 3[A6] = 2[A6] - 2[A5] = 2[J5]

(the same AIC in Eureka notation:)
Code:
(3)r9c4 = (3)r9c6 - (3=2)r1c6 - (2)r1c5 = (2)r9c5


This chain has created a connection between candidate 3 in J4 and candidate 2 in J5. One of them must be true.
- When J4=3, J4 cannot be 2.
- When J5=2, J4 cannot be 2.
Since one of these 2 must be true, we can eliminate 2 from J4.

The output from Andrew's solver is a bit confusing, but it is correct:
- When J4=3, J5 cannot be 3.
- When J5=2, J5 cannot be 3.
We could also, had there been such a candidate, eliminate 3 from J5.

To understand how they work, you need to know about the logic behind them. To use them, you only need to remember the way to find them:

1. Mark the cells with only 2 candidates (bivalue cells)
2. Mark the units with only 2 candidates for a number (bilocal units)
3. Connect the dots. Mark the weak inference between candidates found in step 1 and 2. Do not reuse the same candidate. You may use a strong link for weak inference if you need it. Make sure that the first and the last pair of candidates in the chain have strong inference.
4. At any stage, check if there are candidates than can see the first and the last candidate in the chain. If so, you have an effective AIC.

Just ask if you need more clarification. Maybe one of the other forum members can jump in if my explanation is too technical.
Ruud
Back to top
View user's profile Send private message Send e-mail
Display posts from previous:   
Post new topic   Reply to topic    SudoCue Users Forum Index -> Help Me! I'm stuck! 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