Logical Tracking of Eliminations ???

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

Logical Tracking of Eliminations ???

Postby daj95376 » Tue Oct 28, 2008 5:17 am

Code: Select all
 *-----------*
 |.1.|5..|4..|
 |3..|...|.9.|
 |..4|.9.|.5.|
 |---+---+---|
 |4..|3..|.15|
 |..1|.5.|.3.|
 |...|..8|2..|
 |---+---+---|
 |2..|..3|...|
 |.53|26.|.47|
 |...|7..|.21|
 *-----------*

 *--------------------------------------------------------------------*
 | 679    1      2679   | 5      3      67     | 4      8      26     |
 | 3      678    5      | 468    27     1467   | 17     9      26     |
 | 678    2678   4      | 68     9      1267   | 17     5      3      |
 |----------------------+----------------------+----------------------|
 | 4      6789   26789  | 3      27     67     | 69     1      5      |
 | 679    2679   1      | 469    5      2467   | 69     3      8      |
 | 5      3      69     | 69     1      8      | 2      7      4      |
 |----------------------+----------------------+----------------------|
 | 2      478    78     | 1      48     3      | 5      6      9      |
 | 1      5      3      | 2      6      9      | 8      4      7      |
 | 689    4689   689    | 7      48     5      | 3      2      1      |
 *--------------------------------------------------------------------*

This Eureka! chain was presented in the DailySudoku forum as a way of getting around the use of XY/XYZ-Wings in the puzzle.

storm_norm wrote:(2-7)r4c5=(7)r2c5-(7)r2c7=(7-1)r3c7=(1-2)r3c6=(2)r3c2-(2)r5c2=(2)r5c6-(2)r4c5; r4c5 <> 2

However, it also presents an opportunity for me to raise a question. If you only perform the chain through these steps,

Code: Select all
(2-7)r4c5=(7)r2c5-(7)r2c7=(7-1)r3c7=(1-2)r3c6

then you have logically eliminated (2) from every cell in [b2]. Why can't the chain be ended here?

I'm not implying that actual eliminations should be performed and used as in a forcing network. I'm proposing that it should be acceptable to track eliminations without performing them, and then be able to use this information if all cells in a house/unit are logically eliminated for a candidate.

(I have this nagging feeling that I asked this question quite awhile back. If so, then my apologies ... and what was the answer?)
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Logical Tracking of Eliminations ???

Postby ronk » Tue Oct 28, 2008 5:33 am

daj95376 wrote:This Eureka! chain was presented in the DailySudoku forum as a way of getting around the use of XY/XYZ-Wings in the puzzle.
storm_norm wrote:(2-7)r4c5=(7)r2c5-(7)r2c7=(7-1)r3c7=(1-2)r3c6=(2)r3c2-(2)r5c2=(2)r5c6-(2)r4c5; r4c5 <> 2

However, it also presents an opportunity for me to raise a question. If you only perform the chain through these steps,
Code: Select all
(2-7)r4c5= (7)r2c5-(7)r2c7=(7-1)r3c7=(1-2)r3c6

then you have logically eliminated (2) from every cell in [b2]. Why can't the chain be ended here?

You can, with a liittle modification.

(7)r4c5 = (7)r2c5 - (7)r2c7 = (7-1)r3c7 = (1-2)r3c6 = (2)r5c6 ==> r4c5<>2, r5c6<>7

The viewpoint that a unit (row, column, box) is void of a digit value is considered "crashing the puzzle" ... and generally frowned upon.:( Ditto if a cell is void of all candidates.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Pat » Tue Oct 28, 2008 6:27 am

daj95376 wrote:
Code: Select all
 *--------------------------------------------------------------------*
 | 679    1      2679   | 5      3      67     | 4      8      26     |
 | 3      678    5      | 468    27     1467   | 17     9      26     |
 | 678    2678   4      | 68     9      1267   | 17     5      3      |
 |----------------------+----------------------+----------------------|
 | 4      6789   26789  | 3      27     67     | 69     1      5      |
 | 679    2679   1      | 469    5      2467   | 69     3      8      |
 | 5      3      69     | 69     1      8      | 2      7      4      |
 |----------------------+----------------------+----------------------|
 | 2      478    78     | 1      48     3      | 5      6      9      |
 | 1      5      3      | 2      6      9      | 8      4      7      |
 | 689    4689   689    | 7      48     5      | 3      2      1      |
 *--------------------------------------------------------------------*

    (2-7)r4c5=(7)r2c5-(7)r2c7=(7-1)r3c7=(1-2)r3c6
    then we have eliminated 2 from every cell in b2

yes, daj95376, the logic is obviously valid
    if r2c5 = 7
    then the 7 for c7 is in r3,
    so the 1 for that row is in b2,
    leaving no 2 in that box — impossible; hence r2c5 not 7
it seems to me that this is considered "Forcing Net"
( rather than "Forcing Chains" )
— but i could be wrong
    ( and i certainly cannot comment on the notation )
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Postby daj95376 » Tue Oct 28, 2008 6:39 am

ronk: Thanks for your perspective.

Pat: Yes, I've decided that my viewpoint does fall within the definition of a forcing net. However, the tighter constraints may qualify it as a sub-type of SIN.

I'm not sure where to go with it. I will probably have to add a module to my solver to see if this logic would contribute anything after traditional chains by being simpler to track than all eliminations in a traditional SIN.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Tue Oct 28, 2008 6:53 am

daj95376 wrote:I'm not sure where to go with it. I will probably have to add a module to my solver to see if this logic would contribute anything after chains but before SINs.

Since you've implemented chains, your solver should already be finding these eliminations ... with two nice loops. Of course, it may find something else first that destroys the chain.

one aic:
(7)r4c5 = (7)r2c5 - (7)r2c7 = (7-1)r3c7 = (1-2)r3c6 = (2)r5c6 ==> r4c5<>2, r5c6<>7

two nice loops:
r4c5 =7= r2c5 -7- r2c7 =7= r3c7 =1= r3c6 =2= r5c6 -2- r4c5 ==> r4c5<>2

r5c6 -7- r4c5 =7= r2c5 -7- r2c7 =7= r3c7 =1= r3c6 =2= r5c6 ==> r5c6<>7

As you can see, the nice loop POV adds a weak inference to one or the other of the ends of the AIC.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Tue Oct 28, 2008 8:39 am

My chains routine is incomplete when it comes to loops. I do not record intermediate eliminations in my chains.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Logical Tracking of Eliminations ???

Postby hobiwan » Tue Oct 28, 2008 9:48 am

daj95376,

I would write this as contradiction chain in two steps:

r4c5=2 => r2c5<>2
r4c5=2=> r2c5=7 => r3c7=7 => r3c6=1 => r3c6<>2
Contradiction in b2 => r4c5<>2

In Nice Loop Notation:

r4c5 -2- r2c5 => r2c5<>2
r4c5 =7= r2c5 -7- r2c7 =7= r3c7 -1- r3c6 => r3c6<>2

Since every step depends only on the step before it, I would classify it as chain and not as net. But if you write it in one step, as you did, it would probably be a net.

ronk wrote:(7)r4c5 = (7)r2c5 - (7)r2c7 = (7-1)r3c7 = (1-2)r3c6 = (2)r5c6 ==> r4c5<>2, r5c6<>7

It looks like the last bastion of nice loop notation is crumbling:D

Let me step in:
r4c5 =7= r2c5 -7- r2c7 -1- r2c6 =1= r3c6 =2= r5c6 => r4c5<>2, r5c6<>7
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Re: Logical Tracking of Eliminations ???

Postby ronk » Tue Oct 28, 2008 10:05 am

hobiwan wrote:Let me step in:
r4c5 =7= r2c5 -7- r2c7 -1- r2c6 =1= r3c6 =2= r5c6 => r4c5<>2, r5c6<>7

Sorry, but the loop part of the nice loop term means that either ...
  1. the leftmost and rightmost nodes are the same, or
  2. the leftmost and rightmost nodes overlap.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Logical Tracking of Eliminations ???

Postby hobiwan » Tue Oct 28, 2008 11:41 am

ronk wrote:
hobiwan wrote:Let me step in:
r4c5 =7= r2c5 -7- r2c7 -1- r2c6 =1= r3c6 =2= r5c6 => r4c5<>2, r5c6<>7

Sorry, but the loop part of the nice loop term means that either ...
  1. the leftmost and rightmost nodes are the same, or
  2. the leftmost and rightmost nodes overlap.

I was referring to the notation part of nice loop notation. The move itself is of course not a nice loop, but an AIC, that combines two nice loops.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby storm_norm » Wed Oct 29, 2008 12:58 pm

I don't normally start off AIC's with weak inferences. if anything, its clearer in my mind when I can start off with strong inferences so that I can make eliminations without coming back around to the cell I started in.

not sure how you see it, but I see it as connecting a x-wing/cycle with a useless skyscraper and a little strong link on 1, which is enough for me to make the elimination. since it works in both directions I was quite happy.:D
storm_norm
 
Posts: 85
Joined: 27 February 2008

Postby Mage » Thu Oct 30, 2008 12:38 am

storm_norm wrote:I don't normally start off AIC's with weak inferences. if anything, its clearer in my mind when I can start off with strong inferences so that I can make eliminations without coming back around to the cell I started in.

not sure how you see it, but I see it as connecting a x-wing/cycle with a useless skyscraper and a little strong link on 1, which is enough for me to make the elimination. since it works in both directions I was quite happy.:D

All this stuff looks quite complicated to me.

An AIC starts and ends with a strong link. See Myth Jellies initial definition :
http://forum.enjoysudoku.com/viewtopic.php?t=3865

This very simple chain will do the job :
(7)r2c7 = (7)r3c7 - (1)r3c7 = (1)r3c6 - (2)r3c6 = (2)r2c5
==> r2c5<>7 (and r2c7<>2)

Mage
Mage
 
Posts: 17
Joined: 20 March 2006
Location: France


Return to General