gsf's "A Ternary Monoid for Sudoku Coloring"

Advanced methods and approaches for solving Sudoku puzzles

Re: gsf's "A Ternary Monoid for Sudoku Coloring"

Postby Obi-Wahn » Wed May 23, 2007 10:49 am

gsf wrote:
rep'nA wrote:why are these "the" seven tri-cycles...? What doesn't work, for instance, with

Code: Select all
       (0)
       / \ 
      1   3
     /     \
    *---2---*       


this is a mirror image of one of the 7 tri-cycles, so it does work
the ones that don't work (provide eliminations or assignments) are 111, 222, 333,
and tri-cycles with any 0-edges -- I fixed the note to emphasize this, thanks

I don't see that this is a mirror image. The tri-cycle in your list provides another information on another vertex:
Code: Select all
        (1)     
        / \     
       2   3     
      /     \   
     *---1---*   

        123     

Actually this combination is the only tri-cycle that provides information for two of its vertices.
So I think you either have to make it 8 tri-cycles (plus mirror images) that provide coloring information or you may put it this way:
Code: Select all
         *       
        / \     
       1   2     
      /     \   
    (0)--3--(1) 

        123     


Or maybe you think of mirroring like in Physics not only as space inversion (Parity P) but also as possible charge conjugation (C), exchanging 1-edges <=> 2-edges and also coloring information (0) <=> (1)?
In this case your tri-cycles may be CP invariant.:)

But then you need only 4 information-yielding tri-cycles and can derive the others by "charge conjugation".

Thinking further about it, you need only the leftmost tri-cycles in your list and can derive the others be replacing any of the 1- or 2-edges by a 3-edge.

BTW, it is not true that the 333 tri-cycle doesn't provide any coloring information, it provides every coloring information. So it would prove for any of its vertices that it must and must not have the color in question, which is a contradiction.
Actually, the 133, 233 and 333 tri-cycles are impossible for a valid puzzle or in other words would prove a puzzle to be unsolvable.
User avatar
Obi-Wahn
 
Posts: 63
Joined: 05 January 2007
Location: Darmstadt, Germany

Re: gsf's "A Ternary Monoid for Sudoku Coloring"

Postby gsf » Wed May 23, 2007 2:05 pm

Obi-Wahn wrote:
gsf wrote:
rep'nA wrote:why are these "the" seven tri-cycles...? What doesn't work, for instance, with

Code: Select all
       (0)
       / \ 
      1   3
     /     \
    *---2---*       


this is a mirror image of one of the 7 tri-cycles, so it does work
the ones that don't work (provide eliminations or assignments) are 111, 222, 333,
and tri-cycles with any 0-edges -- I fixed the note to emphasize this, thanks

I don't see that this is a mirror image. The tri-cycle in your list provides another information on another vertex:
Code: Select all
        (1)     
        / \     
       2   3     
      /     \   
     *---1---*   

        123     


appently mirrors got in the way of me telling the difference between (0) and (1) in the two diagrams
I'll update the post by keeping the 7 tri-cycles and adding (0) and (1) where appropriate
BTW, it is not true that the 333 tri-cycle doesn't provide any coloring information, it provides every coloring information. So it would prove for any of its vertices that it must and must not have the color in question, which is a contradiction.
Actually, the 133, 233 and 333 tri-cycles are impossible for a valid puzzle or in other words would prove a puzzle to be unsolvable.

another good point that I will add
thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: gsf's "A Ternary Monoid for Sudoku Coloring"

Postby gsf » Wed May 23, 2007 3:19 pm

Obi-Wahn wrote:Actually, the 133, 233 and 333 tri-cycles are impossible for a valid puzzle or in other words would prove a puzzle to be unsolvable.

133 and 233 are valid and accounted for in the diagrams
333 is the only invalid one
I updated the original post and made a comment about the 10 possible tri-cycles
7 with assignments/eliminations, 2 (111 222) with no assignments/eliminations, and 1 (333) impossible for valid sudoku
I also added a comment about 1-edge and 2-edge being complements and the complementary relationships in the diagrams
thanks again
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: gsf's "A Ternary Monoid for Sudoku Coloring"

Postby Obi-Wahn » Wed May 23, 2007 6:29 pm

gsf wrote:133 and 233 are valid and accounted for in the diagrams

I was in a hurry when I posted this, I knew I should think about it in more detail.

Every 3-edge can represent both a 1-edge or a 2-edge. So:
Code: Select all
       (0)                   (0)                *                 *
       / \                   / \               / \               / \
      3   3     includes    1   1     and     1   2     and     2   1
     /     \               /     \           /     \           /     \
   (1)--2--(1)            *---2---*         *---2--(1)       (1)--2---*


Your list is correct now. Good work.:!:

I just found that rep'nA already saw the contradiction in the 333 tri-cycle but thought that his interpretation was wrong.
rep'nA wrote:I suppose what makes me most skeptical of my interpretation is the clearly nonsensical situation that occurs when the tri-cycles multiply to 3. For then you should simultaneously be able to deduce that the vertex is and is not the induced subgraph color.

But he's right.:idea:
If you start at a vertex in a tri-cycle and use the multiplication table on the three adjecent edges, there are 4 possible results:
If the result is 0 it's inconclusive (*).
If it's 1 the vertex cannot be the induced subgraph color (0).
If it's 2 the vertex must be the induced subgraph color (1).
And if it's 3 we have a contradiction.
User avatar
Obi-Wahn
 
Posts: 63
Joined: 05 January 2007
Location: Darmstadt, Germany

Re: gsf's "A Ternary Monoid for Sudoku Coloring"

Postby gsf » Wed May 30, 2007 6:31 am

Obi-Wahn wrote:I just found that rep'nA already saw the contradiction in the 333 tri-cycle but thought that his interpretation was wrong.
rep'nA wrote:I suppose what makes me most skeptical of my interpretation is the clearly nonsensical situation that occurs when the tri-cycles multiply to 3. For then you should simultaneously be able to deduce that the vertex is and is not the induced subgraph color.

But he's right.:idea:
If you start at a vertex in a tri-cycle and use the multiplication table on the three adjecent edges, there are 4 possible results:
If the result is 0 it's inconclusive (*).
If it's 1 the vertex cannot be the induced subgraph color (0).
If it's 2 the vertex must be the induced subgraph color (1).
And if it's 3 we have a contradiction.

that's a great observation
apologies to rep'nA for not seeing this in the original post
the note has been updated
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Ruud » Tue Aug 14, 2007 10:31 am

Hey, it worked:D
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby re'born » Tue Aug 14, 2007 10:57 am

Ruud wrote:Hey, it worked:D

OMG. Fantastic job Ruud (and anonymous board administrator). Thanks a million.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby ravel » Tue Aug 14, 2007 7:16 pm

Thanks Ruud,

i always suspected that it should be possible, but no one knew how to:)
ravel
 
Posts: 998
Joined: 21 February 2006

Previous

Return to Advanced solving techniques