The New Sudoku Players' Forum

[Hajime]

Busy with programming AIC-method (Alternating Inference Chain).
Already programmed X-chain (same candidate k along the chain) and XY-chain (bivalue) and loops.
Now it occurs to me that AIC is a mix of X-chain and XY-chain....
Is that true ?
Within a bivalue cell the candidate may change from k1 to k2 (strong link) in the chain.
Within a house (row,col,box) the candidate can not change (weak link or strong link) over cells in the chain.
Weak links and Strong links must alternate.
Is this correct? Missing something?

[denis_berthier]

.
This is not incorrect.
AICs (basic ones) are what I call less ambiguously bivalue-chains. They are the 3D counterparts (or supersymmetric extension) of the 2D xy-chains.

[StrmCkr]

strong links

Correct, they Alternate relationships of weak - strong
So that digits don't change in a sector,
Digits change when cells don't change.

Strong link: a group of cells or digits that is precisely true or false for the sector or cell

A =B as (cells) or (digits) form the exchange

Weak link is deterministic based on 1 outcome of the previous selection

If a is false then we build a list of strong links that are indirectly effected by the choice b is true.

Consider this

Code: Select all

 
X// /// XXX              (1)
/
/
/
/
/
X// /// X//            (2)
/
/

For example the col has a Strong link between the rows is not needed and cant be used as it contains the cell of (1).

Code: Select all

xXx  = x   -  x = x

Code: Select all

+-----------------------+------------+---------+
| /            .    .   | .  .     . | .  .  . |
|-3456789(12)  .    .   | . -12    . | .  .  . |
| /            .    .   | .  .     . | .  .  . |
+-----------------------+------------+---------+
| /            .    .   | .  .     . | .  .  . |
| /            .    .   | .  .     . | .  .  . |
| /            .    .   | .  .     . | .  .  . |
+-----------------------+------------+---------+
| (1)         -12  -12  | .  .     . | .  .  . |
| (2)         -12  -12  | .  .     . | .  .  . |
| /            (1)  (2) | /  (12)@ / | /  /  / |
+-----------------------+------------+---------+

the strong links of 1 & 2 are easy to build using the indirect reference above.
the distinction is best seen here:
if you consider the bivalve (@) as the starting point.
there is no Indirect links for 1 or 2 listed.

instead it uses the cell R9C5 as the weak inference.

http://forum.enjoysudoku.com/alternating-inference-chains-t3865.html
http://sudopedia.enjoysudoku.com/Alternating_Inference_Chain.html
https://www.sudopedia.org/wiki/Alternating_Inference_Chain

Code: Select all

+------------------------+----------------------+--------------------+
| 37     9        67     | 126     1267   4     | 1367   8     5     |
| 347    1        4567   | 256     8      2567  | 9      2367  237   |
| 78     5678     2      | 3       9      1567  | 167    4     17    |
+------------------------+----------------------+--------------------+
| 12347  2367     1467   | 12456   12567  9     | 13457  237   8     |
| 5      278      1478   | 124     3      127   | 147    9     6     |
| 9      2367     1467   | 8       12567  12567 | 13457  237   12347 |
+------------------------+----------------------+--------------------+
| 7(1)   4        7(159) | 569(1)  56(1)  8     | 2      367   379   |
| 278    78-2(5)  3      | 569(2)  4      56(2) | 678    1     79    |
| 6      28       8(19)  | 7       (12)   3     | 48     5     49    |
+------------------------+----------------------+--------------------+

(5) 64 = 56 (5) - (9) 56 = 74 (9) - (1) 74 = 54 56 (1) - (1) 57 58 = 76 (1) - (2) 76 = 64 68 (2)
=>> 64 <> 2

Edit more sources to read added
https://paulspages.co.uk/sudokuxp/howtosolve/niceloops.htm
http://hodoku.sourceforge.net/en/tech_chains.php

[RSW]

It took me a while to become comfortable with how the alternating inferences work. Please forgive me if what I say is completely obvious, but here is my simple take on it.

If you have a number of propositions zA, yB, xC, wD, vE... each of which can be either true or false, then the "strong" link zA=yB means that either zA is true or yB is true, or both are true. In other words, at least one of them must be true. A "weak" link yB-xC means that either yB is false or xC is false, or both are false. In other words, at least one of them must be false.

(Because of the way these links work with the "at least" condition, I think that the terms "strong" and "weak" are poorly chosen, but it's too late to change the terminology.)

The strong and weak links have no influence on any proposition other than the two that are immediately connected by the link. So, we don't need to remember anything from elsewhere in the chain as we traverse it.

Now, if we string together the propositions by alternating strong and weak links to get, for example:
zA=yB-xC=wD
it's straightforward to work through the logic to show that the relationship between the first and last proposition is:
zA=wD

Similarly, if the chain starts and ends with weak links:
yB-xC=wD-vE
then the relationship between the first and last proposition is:
yB-vE

These examples are for chains with 4 propositions and 3 links, but it's straightforward to work through the logic to show that this holds for chains of any length (as long as the first and last links are of the same type).

So far, no mention has been made of cells or candidates, or even Sudoku. The logic behind AICs can be applied to any problem that can be stated as described above. In the case of Sudoku, we can specify that proposition zA means "digit z is the solution digit for cell A". The proposition has not necessarily been proven.

Now we can build a list of strong links by analyzing the puzzle grid to get the strong links, the simplest types being bivalue cells and bilocal digits. For example, a bivalue cell strong link will be of this form:
rA=sA
Note that the cell is the same but the digits are different.

For a bilocal digit strong link, we have this form:
pA=pB
In this case the digit is the same but the cells are different.

From more complicated patterns such as ALS's we can get derived strong links where both the candidate digits and the cells are different:
rA=sB

Consequently, X-chains and XY-chains are just subtypes of AICs.

Note that in each of these cases, the strong link can be reduced to the same general form of two candidate digits, and two cells. (Group links require more information, but they will be considered later.) From this, it can be seen that the logic involved in finding AICs can be split into two parts. First, build a dataset of all of the strong and weak links. Second, traverse the the set of links, alternating strong and weak, to generate a chain. Doing it this way, knowledge of how the link is derived is only required when building the dataset. The second step of generating the chain requires no knowledge of the links' origins.

For group links, such as grouped X-links, then more complex logic is required to find the link when building the strong link table, and more complex logic is also required to find the related weak links between the grouped strong links. However, once this information has been added to the dataset, they are once again just strong and weak links, and the logic that traverses the data doesn't need to know how they were originally derived.

This is how I implemented my AIC finder. The code finds all of strong links and puts them into a table. Then it finds all of the weak links between every combination of strong links and puts them into a table. Once this is done, the logic used for the traversal of the links and building of the AICs is very simple.

Over time, as I analyze more puzzle patterns to find new ways of generating strong links, I can add these to the dataset building part of the program, while the traversal part of the code remains unchanged.

The point that I'm making here, is that it's a good idea to look at the more abstract nature of AICs, and getting comfortable with that, before jumping into the fine details of how they apply in Sudoku.

[StrmCkr]

notes extensions RWS comments for Groups nodes with Bi locals {for reference check out my strong link thread}

- how you break the grid up for nodes enhances your ability to detect AIC's

Code: Select all

+------------------------+----------------------+--------------------+
| (+3-7)     9     67    | 126    1267    4     | 167-3  8     5     |
| -7(4-3)    1     4567  | 256    8       2567  | 9      2367  237   |
| 78         5678  2     | 3      9       1567  | 167    4     17    |
+------------------------+----------------------+--------------------+
| 1-7(24)  2367  1467  | 12456  1567-2  9     | 13457  237   8     |
| 5          278   1478  | 124    3       127   | 147    9     6     |
| 9          2367  1467  | 8      12567   12567 | 13457  237   12347 |
+------------------------+----------------------+--------------------+
| (17)       4     1579  | 1569   156     8     | 2      367   379   |
| 78(2)      2578  3     | 2569   4       256   | 678    1     79    |
| 6          8(2)  89(1) | 7      (12)    3     | 48     5     49    |
+------------------------+----------------------+--------------------+

(3) R1C1 = R2C1 (3) - (4) R2C1 = R5C1 (4) - (2)R4C1 = R8C1 (2) - (2)R9C2 = R9C5 (2) - (1) R9C5 = R9C3 (1) - (1)R7C1 = R7C1 (7)
=> R1C23 <> 7
=> R1C1 is a single post reductions for cannibalistic eliminations

this one might appear invalid at first as R1c1 & R2C1 share the same col contextually however operationally its box 1 [ row 1 or row 2 ]

[Hajime]

Thank you all. What I suspected is true: X-and XY-chains are special AIC's.
Now I can make one routine for all those chains, including Skyscrapers, 2StringKites, etc
The next challenge will be the "grouped" nodes.
And at the end the breath-first-search in stead of the current depth-first-search (recursive) .