Two-Candidate Notation

Everything about Sudoku that doesn't fit in one of the other sections

Re: Two-Candidate Notation

Postby daj95376 » Sun Aug 16, 2015 9:37 pm

David P Bird wrote:The possible alternative (ab/cd) notation for SK Loops is because they are NOT AICs and the logic covers three divisions of the truths not two.

Strange ... and yet ronk presented it like an AIC with the OR(X,Y):(3) logic.

Code: Select all
Steve Kurzhal's original presentation w/ RonK's labels:

1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1

     1      A478     34578   | 3567    3689    5678    | 3489   I369     2
    L238     9      L378     | 4      K12368  K12678   |J138     5      J368
     23458  A248     6       | 1235    12389   1258    | 7      I139     3489
    -------------------------+-------------------------+-----------------------
     2468    5       1478    | 9       1246    3       | 128    H1267    678
     234689 B12468   13489   | 126     7       1246    | 123589 H12369   35689
     2369   B1267    1379    | 8       5       126     | 1239    4       3679
    -------------------------+-------------------------+-----------------------
     7      C148     14589   | 1235    12348   12458   | 6      G239     3459
    D456     3      D145     |E12567  E1246    9       |F245     8      F457
     45689  C468     2       | 3567    3468    45678   | 3459   G379     1

    (27)r13c2=(27-16)r56c2=(16)r79c2-(16)r8c13=(16-27)r8c45=(27)r8c79-
    (27)r79c8=(27-16)r45c8=(16)r13c8-(16)r2c79=(16-27)r2c56=(27)r2c13-loop

The SK-Loop doesn't work unless the first SL forces both of (27) false in r13c2 and both of (27) true in r56c2. We may not have a consensus on how to notate these terms, but it sure looks like an AIC loop in all other respects!

This is even more apparent in the V-Loop version:

Code: Select all
 (48=27)r13c2 - (27=38)r2c13 - (38=16)r2c79 - (16=39)r13c8 -
 (39=27)r79c8 - (27=45)r8c79 - (45=16)r8c13 - (16=48)r79c2 - loop

_
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Two-Candidate Notation

Postby David P Bird » Sun Aug 16, 2015 10:18 pm

daj95376 wrote:Now, because no one wants conditon OR(-A,-B):(3) to be true/possible for "-(ab)" in two cells, I changed it to XOR.

You are mistaken and have been confused by DB's blue smoke. The AIC theorems work on the principle that the arguments for a strong link can't both be false. Check that out in your list of possible results and it includes both OR and XOR relationships. It doesn't matter that sometimes (well almost always) in AICs we know that only one of them can be true and an alternative weak link is available.

Taking this in small steps:

Consider this chain for an XYWing
(1=2)r3c3 – (2=3)r1c1 – (3=1)r1c9 which proves (1)r3c3 and (1)r1c9 can't both be false.
However if (3)r1c5 is true then they would both be true – the derived link between them is an OR not a XOR inference and that is true for all chains that terminate with strong links which is what AICs are all about.

The important thing is that in our constructions, but not it seems in DB's we can use strong only links (ie there is no alternative weak link) as in an UR
(123) (12)
(124) (12)
One of (3)top left and (4)bottom left must be true so we can use that inference in a chain but it doesn't stop both of them being true.

As an analogy we are quite happy to know that the vehicle we are travelling on is a bus, but DB insists on being told if it’s a single-decker or a double-decker. If you re-read the reaction he got everyone is quite happy to say our strong links are OR inferences.

Taking this segment from your SK loop example in your second post
(27)r13c2 = (27-16)r56c2 = (16)r79c2
In the red node there are three possible divisions of the truths.
(2) & (7) both true, (1) & (6) both false
(2) & (7) both false, (1) & (6) both true
One of (2) and (7) true the other false and one of (1) & (6) true and the other false.

However because the loop closes we know that (2) & (7) will occupy two cells in r1356c2 so any other instances of them in c2 must be false.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Two-Candidate Notation

Postby daj95376 » Mon Aug 17, 2015 7:52 am

David P Bird wrote:Taking this segment from your SK loop example in your second post
(27)r13c2 = (27-16)r56c2 = (16)r79c2
In the red node there are three possible divisions of the truths.
(2) & (7) both true, (1) & (6) both false
(2) & (7) both false, (1) & (6) both true
One of (2) and (7) true the other false and one of (1) & (6) true and the other false.

However because the loop closes we know that (2) & (7) will occupy two cells in r1356c2 so any other instances of them in c2 must be false.

Thanks DPB for running this thread in a complete circle.

One of the objectives of this thread was to find an acceptable qualifier symbol for the expressions:

Code: Select all
   =( a + b )                  -->  (  a AND  b )   -- pair       in two cells   (SK-Loop or V-Loop)
   -( a + b )                  -->  ( -a AND -b )   -- pair       in two cells   (SK-Loop or V-Loop)

Since we never arrived at a consensus for the qualifier symbol, I responded to your comment on SK-Loops with an example using unqualified (ab) terms. After all, the focal point was whether or not an SK-Loop was an AIC loop (with properly qualified terms).

Using my proposed qualifier symbol, that chain segment would have been written:

Code: Select all
(2+7)r13c2 = (2+7 - 1+6)r56c2 = (1+6)r79c2

Your subsequent criticism is incorrect because your third division isn't possible for the weak link in red once the terms are qualified. Your first and second divisions are only true depending upon the direction one reads the weak link.

_
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Two-Candidate Notation

Postby David P Bird » Mon Aug 17, 2015 9:08 am

daj95376 wrote:
David P Bird wrote:Taking this segment from your SK loop example in your second post
(27)r13c2 = (27-16)r56c2 = (16)r79c2
In the red node there are three possible divisions of the truths.
(2) & (7) both true, (1) & (6) both false
(2) & (7) both false, (1) & (6) both true
One of (2) and (7) true the other false and one of (1) & (6) true and the other false.

However because the loop closes we know that (2) & (7) will occupy two cells in r1356c2 so any other instances of them in c2 must be false.

Thanks DPB for running this thread in a complete circle.

One of the objectives of this thread was to find an acceptable qualifier symbol for the expressions:

Code: Select all
   =( a + b )                  -->  (  a AND  b )   -- pair       in two cells   (SK-Loop or V-Loop)
   -( a + b )                  -->  ( -a AND -b )   -- pair       in two cells   (SK-Loop or V-Loop)

Since we never arrived at a consensus for the qualifier symbol, I responded to your comment on SK-Loops with an example using unqualified (ab) terms. After all, the focal point was whether or not an SK-Loop was an AIC loop (with properly qualified terms).

Using my proposed qualifier symbol, that chain segment would have been written:

Code: Select all
(2+7)r13c2 = (2+7 - 1+6)r56c2 = (1+6)r79c2

Your subsequent criticism is incorrect because your third division isn't possible for the weak link in red once the terms are qualified. Your first and second divisions are only true depending upon the direction one reads the weak link.

DAJ, you have written your own solver so will know that computer code has to be capable of handling every possible circumstance and so must our elimination chains. You are asserting that one pair of digits must both be true and the other must both be false. On what grounds can you make that assertion?
If you follow your loop it will appear to confirm that this is true but that's not necessarily so.

This is the solution to your example:
Code: Select all
 *--------*--------*--------*
 | 1 7 4  | 3 8 5  | 9 6 2  |
 | 2 9 3  | 4 6 7  | 1 5 8  |
 | 5 8 6  | 1 9 2  | 7 3 4  |
 *--------*--------*--------*
 | 4 5 1  | 9 2 3  | 8 7 6  |
 | 9 2 8  | 6 7 4  | 3 1 5  |
 | 3 6 7  | 8 5 1  | 2 4 9  |
 *--------*--------*--------*
 | 7 1 9  | 5 4 8  | 6 2 3  |
 | 6 3 5  | 2 1 9  | 4 8 7  |
 | 8 4 2  | 7 3 6  | 5 9 1  |
 *--------*--------*--------*

Note that each term in the SK loop contains one true digit. So you'll reach the right eliminations for the wrong reasons. I leave it to you to decide if you're happy with that.

I repeat SK loops aren't AICs and that's the reason that out of all your suggestions, deciding an alternative notation for them is the one I would support.

You originally replied quite differently but then retracted that post and substituted the one I've quoted (in case you change it again). I'm sure I'm not the only contributor who would be grateful if you reflected a little longer on what you have written before pressing 'submit'.

I think you've had enough of me by now (and the feeling is mutual), so I'll leave it there.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Two-Candidate Notation

Postby daj95376 » Mon Aug 17, 2015 1:14 pm

Thanks to ronk's reference to Wikipedia's "List of Logical Symbols", I've found a symbol that I hope is acceptable for SK-Loop and V-Loop terms.

Code: Select all
 Legend:   Two-Candidate Notation

   =( a   b )  ->  =( a & b )  -->  (  a AND  b )   -- pair       in two cells
   -( a   b )  ->  -( a & b )  -->  ( -a XOR -b )   -- pair       in two cells

   =( a ^ b )                  -->  (  a AND  b )   -- pair       in two cells   (SK-Loop or V-Loop)
   -( a ^ b )                  -->  ( -a AND -b )   -- pair       in two cells   (SK-Loop or V-Loop)

   =( a | b )                  -->  (  a XOR  b )   -- candidates in one cell
   -( a | b )                  -->  ( -a AND -b )   -- candidates in one cell

The Easter Monster step can now be written as ...

Code: Select all
SK-Loop:

 (2^7)r13c2 = (2^7 - 1^6)r56c2 = (1^6)r79c2 - (1^6)r8c13 = (1^6 - 2^7)r8c45 = (2^7)r8c79 -
 (2^7)r79c8 = (2^7 - 1^6)r45c8 = (1^6)r13c8 - (1^6)r2c79 = (1^6 - 2^7)r2c56 = (2^7)r2c13 - loop

Code: Select all
V-Loop:

 (4^8 = 2^7)r13c2 - (2^7 = 3^8)r2c13 - (3^8 = 1^6)r2c79 - (1^6 = 3^9)r13c8 -
 (3^9 = 2^7)r79c8 - (2^7 = 4^5)r8c79 - (4^5 = 1^6)r8c13 - (1^6 = 4^8)r79c2 - loop

_
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Two-Candidate Notation

Postby daj95376 » Mon Aug 17, 2015 3:22 pm

David P Bird wrote:This is the solution to your example:
Code: Select all
 *--------*--------*--------*
 | 1 7 4  | 3 8 5  | 9 6 2  |
 | 2 9 3  | 4 6 7  | 1 5 8  |
 | 5 8 6  | 1 9 2  | 7 3 4  |
 *--------*--------*--------*
 | 4 5 1  | 9 2 3  | 8 7 6  |
 | 9 2 8  | 6 7 4  | 3 1 5  |
 | 3 6 7  | 8 5 1  | 2 4 9  |
 *--------*--------*--------*
 | 7 1 9  | 5 4 8  | 6 2 3  |
 | 6 3 5  | 2 1 9  | 4 8 7  |
 | 8 4 2  | 7 3 6  | 5 9 1  |
 *--------*--------*--------*

Note that each term in the SK loop contains one true digit. So you'll reach the right eliminations for the wrong reasons. I leave it to you to decide if you're happy with that.

I repeat SK loops aren't AICs and that's the reason that out of all your suggestions, deciding an alternative notation for them is the one I would support.

You originally replied quite differently but then retracted that post and substituted the one I've quoted (in case you change it again). I'm sure I'm not the only contributor who would be grateful if you reflected a little longer on what you have written before pressing 'submit'.

I think you've had enough of me by now (and the feeling is mutual), so I'll leave it there.

Congratulations! You've just verified that the SK-Loop: (1) starts with a false premise, (2) returns as a false conclusion, and (3) every term in between is also false. Does this invalidate the loop? Does it invalidate the eliminations generated by the loop? Maybe now we have a prime example why loops typically only generate eliminations for candidates not in the loop. (Yes, an ERI cell might be an exception on the typical eliminations.)

My answer to both questions is no. I'm happy with that!!!

Yes, I posted a message where I had given up on defending my position. You had worn me down! Later, I decided not to give up and withdrew the original post to pursue a topic that I thought needed to be resolved/rescued. I posted another rebuttal to your position. So, sue me!

_
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Two-Candidate Notation

Postby David P Bird » Mon Aug 17, 2015 4:25 pm

daj95376 wrote:Congratulations! You've just verified that the SK-Loop: (1) starts with a false premise, (2) returns as a false conclusion, and (3) every term in between is also false. Does this invalidate the loop? Does it invalidate the eliminations generated by the loop? Maybe now we have a prime example why loops typically only generate eliminations for candidates not in the loop. (Yes, an ERI cell might be an exception on the typical eliminations.)

My answer to both questions is no. I'm happy with that!!!

Yes, I posted a message where I had given up on defending my position. You had worn me down! Later, I decided not to give up and withdrew the original post to pursue a topic that I thought needed to be resolved/rescued. I posted another rebuttal to your position. So, sue me!

DAJ I took no pleasure in being a pit bull terrier towards you as frankly it was time consuming trying to write things in a way I thought you might understand. I was doing it for the benefit of the forum as a whole, as of late you've been running amok which is why I also threw in a few home truths.

Now I've finished my role as hard cop, perhaps someone else can be the soft cop and get you to see the error of your ways.

DPB
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Postby ronk » Mon Aug 17, 2015 7:06 pm

daj95376 wrote:Thanks to ronk's reference to Wikipedia's "List of Logical Symbols", I've found a symbol that I hope is acceptable for SK-Loop and V-Loop terms.

The '^' character is an excellent choice for XOR. The four symbols '&', '|', '^' and '~' are all members of the C++ (and C) bitwise operator set. We are already using '&' and '|' for AND and OR, exclusively, so it makes sense to stay with this set of operators. Thus we add '^' for XOR and '~' for NOT (negation).

Code: Select all
 Legend:   Two-Candidate Notation (ronk's reduced version)

   =( a ^ b )                  -->  (  a XOR  b )   -- pair       in two cells   (as in SK-Loop or V-Loop, perhaps)

   -( a ^ b )                  -->  ( ~a XOR  b )   -- pair       in two cells   (as in SK-Loop or V-Loop, perhaps)
                           or  -->  (  a XOR ~b )

I'm not sure about that 2nd XOR so I'll do a derivation. Correction made.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Mon Aug 17, 2015 10:41 pm

ronk wrote:
daj95376 wrote:Thanks to ronk's reference to Wikipedia's "List of Logical Symbols", I've found a symbol that I hope is acceptable for SK-Loop and V-Loop terms.

The '^' character is an excellent choice for XOR. The four symbols '&', '|', '^' and '~' are all members of the C++ (and C) bitwise operator set. We are already using '&' and '|' for AND and OR, exclusively, so it makes sense to stay with this set of operators. Thus we add '^' for XOR and '~' for NOT (negation).

Code: Select all
 Legend:   Two-Candidate Notation (ronk's reduced version)

   =( a ^ b )                  -->  (  a XOR  b )   -- pair       in two cells   (as in SK-Loop or V-Loop, perhaps)

   -( a ^ b )                  -->  ( ~a XOR  b )   -- pair       in two cells   (as in SK-Loop or V-Loop, perhaps)
                           or  -->  (  a XOR ~b )

I'm not sure about that 2nd XOR so I'll do a derivation. Correction made.

I was afraid of this.

At the "List of Logical Symbols" web page, the (^) operator was listed as a symbol for AND. I'm aware of it being the XOR operator in C/C++.

You replaced AND with XOR in the definition by confusing the C/C++ operator with my intent.

That's too bad because the web page's definition for (^) is perfect for my needs:

The statement A ∧ B is true if A and B are both true; else it is false.

It looks like I'm back to hunting for another symbol.

Code: Select all
   =( a ? b )                  -->  (  a AND  b )   -- pair       in two cells   (SK-Loop or V-Loop)
   -( a ? b )                  -->  ( -a AND -b )   -- pair       in two cells   (SK-Loop or V-Loop)

_
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Two-Candidate Notation

Postby JasonLion » Mon Aug 17, 2015 11:35 pm

∧ and ^ are not the same symbol. They are two distinct symbols with two unrelated common usage meanings.

∧ is commonly taken as mathematicians AND
^ is commonly taken as programmers XOR

They do look similar. The one commonly used for AND is more difficult to type.
User avatar
JasonLion
2017 Supporter
 
Posts: 624
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: Two-Candidate Notation

Postby daj95376 » Tue Aug 18, 2015 2:16 am

JasonLion wrote:∧ and ^ are not the same symbol. They are two distinct symbols with two unrelated common usage meanings.

∧ is commonly taken as mathematicians AND
^ is commonly taken as programmers XOR

They do look similar. The one commonly used for AND is more difficult to type.

Thanks Jason,

Im aware that there are two symbols that look similar. I was trying to take the "easy" way out and propose the character directly on my keyboard. Bad mistake!!!

However, I'm now leaning towards choosing some other character at this point. Something simple and not dominating when used. At (@) is out, but apostrophe (') is in the running.

_
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Two-Candidate Notation

Postby ronk » Tue Aug 18, 2015 2:49 am

Danny,
I'm at a loss trying to understand what it is you are trying to do. We already have the AND with (a&b) and even more simply (ab). What is different with your proposed AND using the proposed (a^b)?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Logical connectives

Postby denis_berthier » Tue Aug 18, 2015 6:48 am


Logical connectives


Hi daj95376

There are conventional ways of notating things in logic and in mathematics, that no one should try to modify.
Below are, in sequence (it'd be cleaner if I could make tables, but I don't remember how to do it here):
semantics, logical symbol, alternative logical symbol (somewhat outdated), algebraic symbol (if any), usual programming symbol

A equal B:      A=B                A=B             A=B                           A=B
not A:            ¬A                  ~A               -A                              NOT A
A and B:         A∧B                A&B             A.B (or merely AB)       A AND B
A or B:           AvB                 A|B              A+B                            A OR B
A implies B:   A->B              A=>B                                             if A then B

(I use the letter v for "or". The real symbol is slightly different, but I don't know how to type it here)
I will not elaborate on the use of "=" for anything else !!!

There is no standard symbol for xor (which is not one of the primary logical connectives).
A xor B is merely (A v B) ∧ ¬ (A ∧ B), i.e. in algebraic writ: A+B-AB
Using the ^ symbol for xor is a programming aberration, due to the possible confusion with ∧.

Now, the question is, why should one use XOR in the description of a pattern.
As I mentioned before, all the PRIMARY OR relations are indeed XOR and they can only arise at some point in the resolution path as the set of all the candidates remaining for one of the 324 variables (i.e. one the the rc, rn, cn or bn cells). Moreover, they have no reason for being binary (unless you have a bivalue/bilocal candidate), so that you need a means of writing multi-ary XOR. The simplest way I can see is what I use in the nrc notation: {A B C ...}.
As any pattern should be described only in terms of primary relations or of sub-patterns described in such terms, there should be no need for an XOR with a broader meaning.
In the same way, there is no reason to ever write a NOT XOR.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

If SK-loop is an AIC, then so are flying saucers

Postby denis_berthier » Tue Aug 18, 2015 7:08 am


If an SK-loop is an AIC, then so are flying saucers


daj95376 wrote:
Code: Select all
    (27)r13c2=(27-16)r56c2=(16)r79c2-(16)r8c13=(16-27)r8c45=(27)r8c79-
    (27)r79c8=(27-16)r45c8=(16)r13c8-(16)r2c79=(16-27)r2c56=(27)r2c13-loop

...
Code: Select all
 (48=27)r13c2 - (27=38)r2c13 - (38=16)r2c79 - (16=39)r13c8 -
 (39=27)r79c8 - (27=45)r8c79 - (45=16)r8c13 - (16=48)r79c2 - loop

The main credo of the AIC religion is: everything should be reversible, i.e. everything should be provable from left to right AND from right to left.
But the SK-loop can be proven from neither side alone. If proven in terms of chains, it requires both !!!!
(There is an alternative proof in terms of set covers, but then it is clearly not an AIC.)
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Two-Candidate Notation

Postby daj95376 » Tue Aug 18, 2015 9:23 am

ronk wrote:Danny,
I'm at a loss trying to understand what it is you are trying to do. We already have the AND with (a&b) and even more simply (ab). What is different with your proposed AND using the proposed (a^b)?

First, way too much effort has been spent on finding a symbol to join both "a" and "b" given the limited number of times an SK-Loop or V-Loop will ever be posted. I've decided on the apostrophe (') and will get on to justify its existence.

When a chain segment implies the assignment of "a" and "b" in two cells, then there is no difference in:

Code: Select all
=( a   b )  ->  (  a AND  b )

=( a & b )  ->  (  a AND  b )

=( a ' b )  ->  (  a AND  b )

Similarly, there is no difference in the first two forms for the negation of "a" and "b" in two cells. Currently, this is viewed as the pair is not present. I'll leave it at that. The reason for the new symbol is to allow for the negation of both "a" and "b" in the two cells.

Code: Select all
-( a   b )  ->  ( -a XOR -b )

-( a & b )  ->  ( -a XOR -b )

-( a ' b )  ->  ( -a AND -b )

The format of the SK-Loop and V-Loop for Easter Monster are now represented by:

Code: Select all
SK-Loop:

(2'7)r13c2 = (2'7 - 1'6)r56c2 = (1'6)r79c2 - (1'6)r8c13 = (1'6 - 2'7)r8c45 = (2'7)r8c79 -
(2'7)r79c8 = (2'7 - 1'6)r45c8 = (1'6)r13c8 - (1'6)r2c79 = (1'6 - 2'7)r2c56 = (2'7)r2c13 - loop


V-Loop:

(4'8 = 2'7)r13c2 - (2'7 = 3'8)r2c13 - (3'8 = 1'6)r2c79 - (1'6 = 3'9)r13c8 -
(3'9 = 2'7)r79c8 - (2'7 = 4'5)r8c79 - (4'5 = 1'6)r8c13 - (1'6 = 4'8)r79c2 - loop

These loops are bi-directional and meet all of the other properties of an AIC-loop as far as I can tell. I must believe in flying saucers.

For the SK-Loop, the first SL reads:

Code: Select all
l-to-r:

if both <2> and <7> are eliminated from r13c2 ... then ...
   both <2> and <7> must be true in r2c13

r-to-l:

if both <2> and <7> are eliminated from r2c13 ... then ...
   both <2> and <7> must be true in r13c2

Here is the latest form of my legend. Comments?

Code: Select all
 Legend:   Two-Candidate Notation

   =( a   b )  ->  =( a & b )  -->  (  a AND  b )   -- pair       in two cells
   -( a   b )  ->  -( a & b )  -->  ( -a XOR -b )   -- pair       in two cells

   =( a ' b )                  -->  (  a AND  b )   -- both       in two cells   (SK-Loop or V-Loop)
   -( a ' b )                  -->  ( -a AND -b )   -- both       in two cells   (SK-Loop or V-Loop)

   =( a | b )                  -->  (  a XOR  b )   -- candidates in one cell
   -( a | b )                  -->  ( -a AND -b )   -- candidates in one cell

_
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

PreviousNext

Return to General