AIC help

When you have problems solving a Sudoku, ask fellow members to help you
Post Reply
magician
Rookie
Rookie
Posts: 5
Joined: Sun Apr 01, 2007 7:25 pm
Location: UK

AIC help

Post by magician »

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.
Image
Ruud
Site Owner
Site Owner
Posts: 601
Joined: Fri Dec 30, 2005 10:21 pm

Post by Ruud »

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: Select all

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: Select all

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: Select all

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: Select all

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: Select all

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: Select all

3[J6] - 3[A6]
A6 only contains candidates for numbers 2 and 3. One of them must be true.

Code: Select all

3[A6] = 2[A6]
A5 and A6 belong to the same row. They cannot both contain number 2.

Code: Select all

2[A6] - 2[A5]
A5 and J5 contain the last 2 candidates for number 2 in column 5.

Code: Select all

2[A5] = 2[J5]
When combined, here is the complete AIC:

Code: Select all

3[J4] = 3[J6] - 3[A6] = 2[A6] - 2[A5] = 2[J5]
(the same AIC in Eureka notation:)

Code: Select all

(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
Post Reply