The New Sudoku Players' Forum

[tarek]

Code: Select all

+-------+-------+-------+
| 8 . 5 | 1 . . | . 7 . |
| 3 . . | . 2 . | . . 5 |
| . . 7 | . . . | . . . |
+-------+-------+-------+
| . . 1 | . . 3 | . . . |
| . . 9 | 6 . . | . 2 . |
| 2 . 3 | . 9 . | . . 4 |
+-------+-------+-------+
| . . . | 5 3 8 | 4 . 1 |
| . 1 . | . . . | . . . |
| . . . | 4 . . | . 8 7 |
+-------+-------+-------+
8.51...7.3...2...5..7........1..3.....96...2.2.3.9...4...5384.1.1..........4...87


Play this puzzle online

Download Sukaku Explainer

[RSW]

Code: Select all

+---------+------------+------------+
| 8 29  5 | 1  46  49  | 23  7  369 |
| 3 6   4 | 78 2   79  | 18  19 5   |
| 1 29  7 | 3  568 59  | 28  4  689 |
+---------+------------+------------+
| 6 458 1 | 2  458 3   | 7   59 89  |
| 7 458 9 | 6  458 145 | 138 2  38  |
| 2 58  3 | 78 9   157 | 6   15 4   |
+---------+------------+------------+
| 9 7   2 | 5  3   8   | 4   6  1   |
| 4 1   8 | 9  7   6   | 5   3  2   |
| 5 3   6 | 4  1   2   | 9   8  7   |
+---------+------------+------------+

9r2c6 > (1r2c8 > 5r6c8)&(7r6c6) > R6∌1 ∴ -9r2c6 stte

Yes, I know, it's not Eureka notation, but the math notation is easily understandable.

[eleven]

Yes, I know, it's not Eureka notation, but the math notation is easily understandable.

It would be better understandable, if you would mark the cells in your grid (also we are used to the row/column notation).

Code: Select all

    +---------+------------+------------+
    | 8 29  5 | 1  46  49  | 23  7  369 |
    | 3 6   4 | 78 2  a79  | 18 b19 5   |
    | 1 29  7 | 3  568 59  | 28  4  689 |
    +---------+------------+------------+
    | 6 458 1 | 2  458 3   | 7   59 89  |
    | 7 458 9 | 6  458 145 | 138 2  38  |
    | 2 58  3 | 78 9  c157 | 6  b15 4   |
    +---------+------------+------------+
    | 9 7   2 | 5  3   8   | 4   6  1   |
    | 4 1   8 | 9  7   6   | 5   3  2   |
    | 5 3   6 | 4  1   2   | 9   8  7   |
    +---------+------------+------------+

Then the AIC can be easily found:
(9=1)r2c8 - r6c8 = (1-7)r6c6 = 7r2c6 => -9r2c6
[Edit: fixed a typo, thanks SpAce. Note that the marking of the cells is in the order of RSW's solution.]

[RSW]

Sorry, Eleven, I normally use K9 notation for my own notation, then realized that I'd posted it that way, and went back to change it to RnCn, but you had already replied. I appreciate your translation of it to a Eureka AIC.

I've been attempting for a very long time to learn this notation, but I've never found a complete specification.

As for the lack of notation in the PM grid, this is another area of confusion. Again there doesn't seem to be any official specification for the proper notation. So, I decided to post an unannotated grid rather than none at all.

[eleven]

Hi RSW,

there should be some links, where you can find, how to write (basic) AIC notation. I hope, others will provide it.
Most of us learned it by looking at other's solutions and by doing then.

All you have to understand is the meaning of the signs:
"=" stands for the logical OR, i.e. either the left or right side or both must be true (strong inference: if one side is false, the other must be true)
"-" for NAND, i.e. not both sides can be true (weak link: if one side is true, the other must be false)

AIC's are reversible, you can read them from left to right and from right to left.
They start and end with a "=" link, and the links must be alternating (note, i had a typo above).
Then you have guaranteed, that there is a strong inference between the first and last term too: at least one of them must be true.

Above you can see, that one of 9r2c8 and 7r2c6 must be true. In both cases r2c6 cannot be 9.

For the markings there are no fixed rules. Everybody tries to do it in a way, that best shows, how the solution can be followed.
For simple AIC's like above you usually number the cells in the order as written in the AIC with a,b,c, etc., where also some cells can be grouped for an ALS (almost locked set, where you have n+1 digits in n cells of a house and all but one must be true).

Personally i accept each notation, which is logically correct and which i can understand. There are only very rare cases however for the (one-stepper) solutions here, where AIC is a bad choice.

[rjamil]

Code: Select all

 +-----------+----------------+-----------------+
 | 8  29   5 | 1   46   49    | 23   7      369 |
 | 3  6    4 | 78  2    (79)  | 18   (19)   5   |
 | 1  29   7 | 3   568  59    | 28   4      689 |
 +-----------+----------------+-----------------+
 | 6  458  1 | 2   458  3     | 7    59     89  |
 | 7  458  9 | 6   458  145   | 138  2      38  |
 | 2  58   3 | 78  9    (17)5 | 6    (1)-5  4   |
 +-----------+----------------+-----------------+
 | 9  7    2 | 5   3    8     | 4    6      1   |
 | 4  1    8 | 9   7    6     | 5    3      2   |
 | 5  3    6 | 4   1    2     | 9    8      7   |
 +-----------+----------------+-----------------+

Strong Wing: SL 9 @ r2c68 7 @ r26c6 1 @ r26c8 r6c68 => -5 @ r6c8; stte

:: OR ::

Code: Select all

 +-----------+----------------+----------------+
 | 8  29   5 | 1   46   49    | 23   7     369 |
 | 3  6    4 | 78  2    (79)  | 18   (19)  5   |
 | 1  29   7 | 3   568  59    | 28   4     689 |
 +-----------+----------------+----------------+
 | 6  458  1 | 2   458  3     | 7    59    89  |
 | 7  458  9 | 6   45   145   | 138  2     38  |
 | 2  8-5  3 | 78  9    (157) | 6    (15)  4   |
 +-----------+----------------+----------------+
 | 9  7    2 | 5   3    8     | 4    6     1   |
 | 4  1    8 | 9   7    6     | 5    3     2   |
 | 5  3    6 | 4   1    2     | 9    8     7   |
 +-----------+----------------+----------------+

Almost Locked Set move: 1579 @ r6c68 r2c68 => -5 @ r6c2; stte

R. Jamil

[RSW]

Eleven,
Thank you for taking the time to post this explanation. I've attempted a few times to convert from my one way logic to a reversible AIC but I've failed every time. I have looked at the basic definition of AIC's here:
http://sudopedia.enjoysudoku.com/Altern ... Chain.html
And I've also looked at, and tried to analyze many of the solutions posted in the Puzzles section.
I do understand definition of strong and weak links. The difficulty is in taking the leap from those simple definitions to a full AIC in a Sudoku solution. It's very helpful that you have provided a translation from my form of logic to the proper Eureka notation. I am absorbing it slowly, and it is slowly sinking in.

[eleven]

If you find a contradiction for a digit, you can try to negate and reverse it (which is logically the same).
9r2c6 > (1r2c8 > 5r6c8)&(7r6c6) > R6∌1 ∴ -9r2c6 stte
not R6∌1 > -7r6c6 | (-5r6c8 => -1r2c8) => -9r2c6

The result will be forcing chains starting with the digits of the contradiction.

There are 2 digits 1 in r6, in r6c6 and r6c8, so "not R6∌1" means 1r6c6 or 1r6c8.

Then without contradiction you could write:
1r6c6 => -7r6c6 => 7r2c6 (=> -9r2c6)
1r6c8 (=> -5r6c8) => -1r2c8 => 9r2c8 (=> -9r2c6)
This is a simple "double forcing chain". These can easily be transformed to an AIC.

In AIC notation:
(1-7)r6c6 = 7r2c6
1r6c8 - (1=9)r2c8

With the 2 1's in r6 you have an OR link 1r6c6 = 1r6c8 and you can combine them to a valid AIC (take the first line from right to left and continue with the second):
7r2c6 = (7-1)r6c6 = 1r6c8 - (1=9)r2c8

Of course you would not make these complicated steps each time, but build the AIC from the grid. I just wanted to show, that the 2 ways are logically the same.

[Mauriès Robert]

Hi Eleven and RSW,
Your debate reminds me of the debates I had on this forum about the tracks and anti-tracks I use (See TDP).
For me AICs are simply the expression in coded language of a string of candidates that one composes by following links. Usually they are chains of contradictions which thus allow one or more eliminations. But their correct writing is not always easy, and I have seen very often discussions on this subject on this forum.
In my opinion it is easier to build and express chains by simple implication (->) which is a universal language known to all. TDP is based on implication and the basic rules of sudoku.
Here's how I eliminate 9r2c6 with an anti-track:
P'(9r2c8): (-9r2c8) => 1r2c8->1r6c6->7r2c6 => -9r2c6 since 9r2c6 sees both 7r2c6 and 9r2c8
This (anti-track) chain, like Eleven's AIC, is here very visibly a chain of contradiction, but generally the property attached to the anti-tracks makes it possible to build chains whose contradiction is not established. I recall this property here:
if a candidate Z sees both E and P'(E), Z can be eliminated. In this statement E can be a candidate or a set of candidates.
For example, on this puzzle, with the antitrace from 1r6c6 without the contradiction being visible, it gives :
P'(1r6c6) : (-1r6c6) => 1r6c8->9r2c8->7r2c6 => -7r6c6 => solution.
Sincerely
Robert

[eleven]

I don't see any logical difference or advantage in this simple example between the implication notation and AIC.
There are some differences (i.e. loops in my opinion are better presented as AIC, but it has other weaknesses, it had always to be extended and there were long and undecided discussions how to write an SK-loop), but for me basically it is a matter of taste and habit, which one to prefer.

[SpAce]

Hi Robert,

For me AICs are simply the expression in coded language of a string of candidates that one composes by following links. Usually they are chains of contradictions which thus allow one or more eliminations.

I wouldn't call them "chains of contradictions" (unless written as such, i.e. by having a weak link at the start or end or both). A real contradiction chain starts with an assumption and proves it false by encountering a contradiction. The slanderer's original chain is a contradiction chain but neither eleven's AIC nor your anti-track is one.

Idiomatically written AICs (with a strong link at both ends) are verity chains, and so are anti-tracks, Denis Berthier's bivalue-chains, and matrices. All or them describe verities (truths) instead of contradictions (falsehoods), which makes them persistent patterns (I just invented that term) in the sense that they can exist and be recognizable in a grid even if they have nothing to eliminate. If eliminations are available, they're external to the chain (except in the rare case of cannibalistic chains), and thus the pattern itself remains even after the eliminations (though having lost its potency). That's not the case with a contradiction chain (or net) which always starts with the to-be-eliminated assumption and ends with a contradiction (if written as an implication chain; as an AIC it could be either way since it's bidirectional or more accurately non-directional). Once you execute the elimination, the contradiction pattern is also destroyed, thus it's not persistent.

But their correct writing is not always easy, and I have seen very often discussions on this subject on this forum.
In my opinion it is easier to build and express chains by simple implication (->) which is a universal language known to all.

It's true that implication chains are probably the most intuitively understandable and easily written expressions of sudoku logic. Yet they're not perfect, as they typically contain less information (only half of the nodes shown compared to AICs) which makes them harder to follow. Of course they can include all the same information, but that's not the idiomatic way to write them, and it would make them much longer than the corresponding AICs. AICs are thus more space-efficient expressions, and can often be compressed even more if need be (though probably sacrificing readability).

Also, pure implication chains are the easiest to understand if used as contradiction chains. To make them intuitively understandable verity chains, one has to include an extra OR condition (implied in your anti-tracks) which means they're no longer pure implication chains. AICs and Denis' biv-chains don't need such kludges, and neither do matrices, as they prove verities natively.

Of course one can also write pure implication chains that prove verities, but they're less intuitive. For that you have to start with a negation -a -> b, which is equivalent to -b -> a. To understand it as a verity one must mentally convert it into (a | b), which eliminates anything that sees both a and b, just like an AIC. Technically you could replace your anti-track syntax by simply writing the implication chains like that -- no information would be lost.

Here's how I eliminate 9r2c6 with an anti-track:
P'(9r2c8): (-9r2c8) => 1r2c8->1r6c6->7r2c6 => -9r2c6 since 9r2c6 sees both 7r2c6 and 9r2c8

(A typo corrected.) The same as a pure implication chain (i.e. what I said above):

-9r2c8 -> 1r2c8 -> 1r6c6 -> 7r2c6 => -9r2c6

or equivalently:

-7r2c6 -> 7r6c6 -> 1r6c8 -> 9r2c8 => -9r2c6

Either of those proves the verity (7r2c6 OR 9r2c8) and hence the elimination. Thus no real need for the P' syntax if one wants to be a purist and keep the notation as simple and standard as possible. Here's the same as a contradiction chain:

9r2c6 -> 1r2c8 -> 1r6c6 -> 7r2c6 (contradiction) => -9r2c6

This (anti-track) chain, like Eleven's AIC, is here very visibly a chain of contradiction

Like I said, it's not a chain of contradiction the way we normally use that term. It's a verity chain like AICs and Denis' biv-chains, because it doesn't start with an assumption and the elimination is external to it. Rather it proves that either 9r2c8 OR 7r2c6 must be true (verity), hence 9r2c6 can't be true (verity). There's no contradiction within the chain itself, and not explicitly even with the elimination, thus not a contradiction chain. A contradiction chain would start by assuming 9r2c6 and running into a contradiction (an example above), like the original solution. Another difference is that a verity chain can prove multiple eliminations simultaneously (not in this case, though), while a contradiction chain can only prove one (the original assumption). Btw, since I know you use both kinds, what do you call the actual contradiction chains to differentiate them?

Btw, here's how I think it would be written using Denis' system (hope he corrects me if I got something wrong):

Code: Select all

biv-chain[3]: r2c8{n9 n1} - r6n1{c8 c6} - c6n7{r6 r2} ==> r2c6 ≠ 9; stte

And here's the matrix form, which I think is the most informative and language-agnostic way to express almost any kind of sudoku logic:

Code: Select all

 9r2c8 1r2c8
       1r6c8 1r6c6
 7r2c6       7r6c6
------------------
-9r2c6

Matrices are also excellent for analyzing and comparing the complexities of different pieces of logic relatively objectively.

--
Edit: typo corrected.

[Ajò Dimonios]

Hi Eleven

Eleven wrote:

I don't see any logical difference or advantage in this simple example between the implication notation and AIC.
There are some differences (i.e. loops in my opinion are better presented as AIC, but it has other weaknesses, it had always to be extended and there were long and undecided discussions how to write an SK-loop), but for me basically it is a matter of taste and habit, which one to prefer.

The difference is in the fact that with the anti-track I can write chains, clearly not reversible, in which the memory of one or more implications of the chain are used to reach the condition “if a candidate Z sees both E and P '(E) , Z can be eliminated”, in pure AIC this is not possible. As for the SK-loops, see for example that of Easter Monster 1 ....... 2.9.4 ... 5 ... 6 ... 7 ... 5.9.3 ..... ..7 85..4.7 ..... ....... 6 9.8 ... 3 ... 2 ... 1 .....,
, the expression of loop "(38 = 27) r2c13 - (27 = 48) r13c2 - (48 = 16) r79c2 - (16 = 45) r8c13 - (45 = 27) r8c79 - (27 = 39) r79c8 - (39 = 16) r13c8 - ( 16 = 38) r2c79 - loop" written in this way is not clearly correct, all strong inferences contain several independent ones. In the first, for example, when 38r2c13 is false it does not imply that 27r2c13 is true and vice versa, this is because the falsehood of 38r2c13 generates three different situations or only 3 is false and 8 is true or 8 is false and 3 is true on the 3rd or both are false. Maybe writing it (3 | 8 = 2 | 7) r2c13 - (2 | 7 = 4 | 8) r13c2 - (4 | 8 = 1 | 6) r79c2 - (1 | 6 = 4 | 5) r8c13 - (4 | 5 = 2|7) r8c79 - (2 | 7 = 3 | 9) r79c8 - (3 | 9 = 1|6) r13c8 - (1 | 6 = 3 | 8) r2c79 - loops fully cover all the possibilities of strong inferences but at this point it is not a single AIC but several AICs written simultaneously which are correct because the loop exists. I frankly prefer the interpretation in terms of MSLS in which the 16 truths are the cells obtained from the crossing of r2; r8; c2; c8; b1; b3; b7; b9, while the 16 links are 48c2.93c8.83r2.54r8 , 27b1,16b3,16b7,27b9 with bases 54893 and 1267.

Paolo

[SpAce]

Hi Paolo,

I guess I'm a slow learner...

The difference is in the fact that with the anti-track I can write chains, clearly not reversible

In theory, every chain is reversible, though not necessarily easily or practically (and it might depend on what one considers reversed). If you want to debate that, do it with eleven. He'll explain. It has been covered extensively in other threads.

, in which the memory of one or more implications of the chain are used to reach the condition “if a candidate Z sees both E and P '(E) , Z can be eliminated”, in pure AIC this is not possible.

Sure it's possible, if I understood correctly what you meant. Multi-headed AICs are perfectly valid, though their eliminations are hard to see unless the embedded end-points are clearly marked and connected with them. It's a lovely way to reduce step count (and redundancy) in some situations when a single chain can be extended with additional end-points that give more eliminations. Even David Bird used them, so they must be not only correct but acceptable by the standard. Of course one can always write a separate chain for each end-point pair, but that involves a lot of repetition. Example:

Code: Select all

(a=b) - (b=c) - (c=d) - (d=e) => -x,y,z

With that AIC (which is not necessarily an xy-chain, though it looks like one) you can eliminate any candidate that sees both members of any of the possible (derived) strong links, i.e. these pairs:

Code: Select all

(a=b), (a==c), (a==d), (a==e), (b=c), (b==d), (b==e), (c=d), (c==e), (d=e)

Thus, it's not just (a==e), even though it's the normal way to use AICs. Most of the time the internal end points don't produce extra eliminations, but if they do, they're up for grabs.

[SK Loops] I frankly prefer the interpretation in terms of MSLS

With this I actually agree, though not with your notation. Standard set logic notation is the best for any MSLS, including SK-Loops, imo. MSLS doesn't need its own notation. That said, the incorrect AIC-like notation is the worst for SK-Loops, so no disagreement there. The second worst option is a correctly written AIC -- when it's even practically possible it's horribly unreadable, and very few people can write them correctly anyway.

If one really wants to notate an SK-Loop as a loop instead of set logic (understandable, because most probably find and see them as loops), there are other ways to do it than to abuse Eureka with incorrect links. Personally I prefer what David originally suggested, i.e. to replace all instances of '=' with '/' and the standard '- loop' at the end with '- SKLoop'. That way the loop is just as readable but there's no confusion with AICs:

Code: Select all

(38/27)r2c13 - (27/48)r13c2 - (48/16)r79c2 - (16/45)r8c13 - (45/27)r8c79 - (27/39)r79c8 - (39/16)r13c8 - (16/38)r2c79 - SKLoop

...or as set logic:

Code: Select all

16\16 (Rank 0): {28N1379 1379N28 \ 38r2 45r8 48c2 39c8 27b19 16b37}

Those are the two best notation options for SK-Loops, imo, though not necessarily in that order. Sometimes it might be clearest to provide both POVs.

A symmetric pigeonhole matrix would work too, of course, and it would probably please SteveK as well. However, such a huge matrix does not show the big picture very well (though the picture is indeed big), but it does show the details of the internal logic better than anything.

[eleven]

The main idea behind AIC's (Alternating Inference Chains) was that you can build chains, which can be extended on both sides and which always keep the property, that at least one of the first and last term must be true. And if you can close it to a loop, then all weak inferences become strong ones, allowing other eliminations. Otherwise you look, if extending the chain on the left or right side can bring you to an elimination between the outer terms.
This way you can never run into a contradiction.

Of course you can express the same with anti-tracks, but the concept is different. Here you define a fixed starting situation and look, what you can get out of it, i.e. if you can find a common outcome (which also can be that one side is wrong), basically the same concept as for double forcing chains.

However it turned out, that this AIC concept is much too weak to solve hard puzzles. So the definition was extended and extended, and by marking memory digits also the paradigma of the reversibility partially dropped.
Also Krakens (or SIS: strong inference sets) became allowed to be able to handle 3 or more way deductions.

All that has been integrated in TDP too in the one or other form.
Until now i have not seen a chain by Robert, which could not be written as (such extended) AIC with memory markers (indeed independantly we had a couple of almost identical eliminations, when solving a harder puzzle).
So at the end i cannot see a difference but the notation - and maybe the way, how it is searched for them, but the harder the puzzles are, the more similar also that will be.

Being a 3-way (either the left side is true or the right side or both are wrong), the SK-loop cannot be expressed with a basic AIC and both of the ways you showed are not correct. E.g. blue showed a correct way, and David suggested another one ...
Since it is proven, that the eliminations are always valid, if there is such a loop, it would be sufficient to write it in the simple form and add the word SK-loop.

[Mauriès Robert]

Hi Space,
I'm not going to go through your answers point by point, because I don't have your writing skills. I'm only going to clarify what I mean by a chain of contradictions, because obviously we don't have the same definitions and we don't give the same meaning to the terms used.
I say that the following chain (-9r2c8) => 1r2c8->1r6c6->7r2c6 => -9r2c6 is a chain of contradiction because 7r2c6 implies +9r2c8 which is a contradiction with -9r2c8. This contradiction is clearly visible.
On the other hand, the chain (-1r6c6) => 1r6c8->9r2c8->7r2c6 => -7r6c6 is not (for me) a chain of contradiction because 7r2c6 does not imply +1r6c6.
The AIC used by eleven is totally equivalent to the first of the two (anti-track) chains I have just described is a chain of contradiction in my opinion.
The same goes for the biv-chain you write totally equivalent to the AIC of eleven.
In the same way, for me Denis Berthier's chains (whip, braid) are chains of contradiction.
For example, whip [3]: c2n3{r1 r5} - c2n8{r5 r3} - r1c3{n8 .} ==> r1c2 ≠ 7 expresses that the placement of 8r1c3 implies a contradiction in the puzzle. Denis will correct me if I'm wrong.
Sincerely