Rambling

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

Postby Draco » Thu Sep 18, 2008 5:16 pm

daj95376 wrote:Hello Draco,

Yes, your forcing chain does the job very nicely. Did you consider converting it into:

Code: Select all
8-[r6c3]-3-[r5c2]=3=[r5c8]=2=[r5c5]-2-[r4c5]-8 => [r4c12]<>8

To me, the above AIC chain is a forcing chain based on the bivalue candidates in [r6c3] -- or the bivalue candidates in [r4c5].

Hi Danny,

I like NL but frequently mess up the conversion, so I've shied away from writing my chains that way. And the AIC notation you used is one that always leaves me blinking and scratching my head; some day I'll have to sit down and get them both straight.

I had to run the forcing chain from r6c3 before I could clearly follow your AIC (until I saw it graphically, my brain was missing the rather obvious r6c3=8 => r4c12<>8). Thanks for the translation:)

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

Postby ronk » Thu Sep 18, 2008 6:02 pm

Code: Select all
8-[r6c3]-3-[r5c2]=3=[r5c8]=2=[r5c5]-2-[r4c5]-8 => [r4c12]<>8

Singles, the above NL, and then more singles.

Draco, very nice find. I doubt there is a more elegant solution to be found for this puzzle.

daj95376, is that the same "short chain" you found before posting the puzzle:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Thu Sep 18, 2008 10:48 pm

ronk wrote:daj95376, is that the same "short chain" you found before posting the puzzle:?:

Yes ... and No. That's not an easy question to answer.

I have my solver configured to ignore chains with equivalent eliminations after the first. This works okay except that I miss catching W-Wings and W-Chains over regular chains sometimes.

When I posted this puzzle, I also had my solver configured to absorb earlier chains if their eliminations were a subset of the eliminations of a later chain. This sometimes resulted in shorter chains being eliminated. The following chains were the shortest (reported) that cracked the puzzle.

Code: Select all
 -5r5c9  8r5c9  8r6c3  3r5c2  5r4c2  [chain__5] <> 5 [r4c78],[r5c2]
 -8r4c5  2r4c5  2r5c8  3r5c2  8r6c3  [chain__5] <> 8 [r4c12]

I then decided that I didn't want to eliminate shorter chains whose eliminations were subsets of longer chains. This resulted in this chain being the shortest that cracks the puzzle.

Code: Select all
  5r5c2  8r5c9  8r6c3  3r5c2         [chain__9] <> 5 [r5c2]
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Draco » Thu Sep 18, 2008 11:16 pm

daj95376 wrote:... resulted in this chain being the shortest that cracks the puzzle.

Code: Select all
  5r5c2  8r5c9  8r6c3  3r5c2         [chain__9] <> 5 [r5c2]

Hi Danny,

I must be misunderstanding something in your notation. My best attempt at translating your notation to the simpler forcing chain list I grok gives me:
Code: Select all
5    4     178  | 28  6  128  | 178     9      3   
2    168   18   | 3   7  9    | 14568   14568  4568
3678 13678 9    | 4   5  18   | 1678    168    2   
----------------+-------------+--------------------
78   578   6    | 9   28 3    | 2458    2458   1   
1    358   4    | 6   28 7    | 9       2358   58 
9    2     38   | 1   4  5    | 368     368    7   
----------------+-------------+--------------------
3678 9     2378 | 258 1  2468 | 234568  234568 4568
368  1368  1238 | 258 9  2468 | 1234568 7      4568
4    168   5    | 7   3  268  | 1268    1268   9   

r5c2=5
r5c9=8
r6c3=8 (what eliminated the 8's from r4c12 or the rest of c3?)
r5c2=3
ergo r5c2<>5

I must be misreading or improperly decoding your notation... or perhaps I am using the wrong PM grid for the starting point? Pls advise, and thanks in advance for your patience:)

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

Postby hobiwan » Fri Sep 19, 2008 1:17 am

Draco wrote:
Code: Select all
r5c2=5
r5c9=8
r6c3=8 (what eliminated the 8's from r4c12 or the rest of c3?)
r5c2=3
ergo r5c2<>5

r5c9=8 means r6c78<>8 which makes r6c3 a hidden single in line 6.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby hobiwan » Fri Sep 19, 2008 1:30 am

ronk wrote:
Code: Select all
8-[r6c3]-3-[r5c2]=3=[r5c8]=2=[r5c5]-2-[r4c5]-8 => [r4c12]<>8

Singles, the above NL, and then more singles.

Draco, very nice find. I doubt there is a more elegant solution to be found for this puzzle.

I seriously have to start questioning my chaining code, because it often gives me unnecessary complicated solutions. I had that elimination as
Code: Select all
Almost Locked Set XY-Chain: A=r4c5 - {28}, B=r5c5 - {28}, C=r5c9 - {58}, D=r5c2,r6c3 - {358}, RCs=2,5,8, X=8 => r4c12<>8

which should have been more or less draco's chain backwards (with one ALS at the end):
Code: Select all
8- r4c5 -2- r5c5 -8- r5c8 -5- ALS:r4c2,r5c3 -8 => r4c12<>8


Incidentally the same elimination can be made with an ALS move:
Code: Select all
Almost Locked Set XY-Wing: A=r4c5 - {28}, B=r6c3 - {38}, C=r5c259 - {2358}, Y,Z=2,3, X=8 => r4c12<>8
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby hobiwan » Fri Sep 19, 2008 2:08 am

daj95376 wrote:
Code: Select all
  5r5c2  8r5c9  8r6c3  3r5c2         [chain__9] <> 5 [r5c2]

Same problem here: I really should get this as a Discontinuous Grouped Nice Loop
Code: Select all
r5c2 -5- r5c9 -8- r6c78 =8= r6c3 =3= r5c2 => r5c2<>5

but instead what I get is the more complicated
Code: Select all
r5c2 -5- r5c9 -8- ALS:r6c78 -3- r5c8 =3= r5c2 => r5c2<>5


Consequently this is what I get as the "shortest" chain to crack the puzzle:
Code: Select all
3- r6c3 -8- ALS:r12c3 -7- ALS:r2389c2 -3 => r5c2<>3


-- sigh --
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby daj95376 » Fri Sep 19, 2008 9:09 am

Draco wrote:I must be misreading or improperly decoding your notation... or perhaps I am using the wrong PM grid for the starting point?

I'm sorry that my solver's abbreviated output was difficult to follow. It only lists initial eliminations for chains and networks. Remember, my solution is a chain and not a network. Therefore, only logical links are used to reach the conclusion. The key to this chain is the contradiction where assigning a cell one value leads to that cell also having to be another value.

Code: Select all
  5r5c2              8r5c9               8r6c3              3r5c2   [chain__9] <> 5 [r5c2]

 [r5c2]=5 [r5c9]<>5 [r5c9]=8 [r6c78]<>8 [r6c3]=8 [r6c3]<>3 [r5c2]=3            => [r5c2]<>5

                    | - hobiwan's explanation - |
___________________________________________________________________________________________
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Fri Sep 19, 2008 9:56 am

daj95376 wrote:I then decided that I didn't want to eliminate shorter chains whose eliminations were subsets of longer chains. This resulted in this chain being the shortest that cracks the puzzle.

Code: Select all
  5r5c2  8r5c9  8r6c3  3r5c2         [chain__9] <> 5 [r5c2]

Definitely shorter. Translated to NL notation that's ...

r5c2 -5- r5c9 -8- r6c78 =8= r6c3 =3= r5c2 ==> r5c2<>5

... which has three strong inferences instead of four as in Draco's ...

r4c12 -8- r6c3 -3- r5c2 =3= r5c8 =2= r5c5 -2- r4c5 -8- r4c12 => r4c12<>8

I have this (poor excuse for a) chain finder which agrees with [edit: yours] being the shortest. I misinterpreted its output before my earlier post.
Last edited by ronk on Fri Sep 19, 2008 6:33 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Draco » Fri Sep 19, 2008 10:19 am

daj95376 wrote:
Draco wrote:I must be misreading or improperly decoding your notation... or perhaps I am using the wrong PM grid for the starting point?

I'm sorry that my solver's abbreviated output was difficult to follow. It only lists initial eliminations for chains and networks. Remember, my solution is a chain and not a network. Therefore, only logical links are used to reach the conclusion. The key to this chain is the contradiction where assigning a cell one value leads to that cell also having to be another value.

Code: Select all
  5r5c2              8r5c9               8r6c3              3r5c2   [chain__9] <> 5 [r5c2]

 [r5c2]=5 [r5c9]<>5 [r5c9]=8 [r6c78]<>8 [r6c3]=8 [r6c3]<>3 [r5c2]=3            => [r5c2]<>5

                    | - hobiwan's explanation - |
___________________________________________________________________________________________


Thank you and hobiwan both for clarifying!

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

Postby daj95376 » Tue Dec 30, 2008 6:46 am

This puzzle is from Mike Barker's zoo contributions.

Code: Select all
 +-----------------------+
 | 2 . . | . . . | 9 . . |
 | . . 8 | . 4 9 | . . . |
 | . 1 . | . . . | 7 8 . |
 |-------+-------+-------|
 | 7 9 . | 1 . . | 8 5 . |
 | . . . | . 6 . | . . . |
 | . . . | 9 . . | . . 2 |
 |-------+-------+-------|
 | 8 2 . | . . 3 | . . . |
 | . . 3 | . 8 . | . 4 7 |
 | . 4 . | 6 . . | 1 . . |
 +-----------------------+

 +--------------------------------------------------------------+
 |  2     357   45    |  378   1     578   |  9     6     345   |
 |  6     357   8     |  37    4     9     |  35    2     1     |
 |  34    1     9     |  23    235   6     |  7     8     345   |
 |--------------------+--------------------+--------------------|
 |  7     9     26    |  1     23    4     |  8     5     36    |
 |  134   358   245   |  2378  6     578   |  34    17    9     |
 |  134   358   456   |  9     35    578   |  346   17    2     |
 |--------------------+--------------------+--------------------|
 |  8     2     1     |  4     7     3     |  56    9     56    |
 |  9     6     3     |  5     8     1     |  2     4     7     |
 |  5     4     7     |  6     9     2     |  1     3     8     |
 +--------------------------------------------------------------+
 # 49 eliminations remain

There are a number of chains present in this PM, but I'm only interested in these two.

Code: Select all
         [r2c7]-5-[r3c9]=5=[r3c5]=2=[r4c5]=3=[r4c9]-3-[r13c9]=3=[r2c7]           =>  [r2c7]<>5

[r2c2]=5=[r2c7]-5-[r3c9]=5=[r3c5]=2=[r4c5]=3=[r4c9]-3-[r13c9]=3=[r2c7]-3-[r2c2]  =>  [r2c2]<>3

______________________________________________________________________________________________

The first chain will crack the puzzle, but its presence in the second chain is what caught my attention. The second chain allows two different values to be assigned to cell [r2c7] without any contradiction in the logic -- I think. Is the second chain a valid chain?

(My apologies if I've asked a similar question previously. Swiss cheese for memory anymore.)
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby hobiwan » Tue Dec 30, 2008 8:29 am

daj95376 wrote:The second chain allows two different values to be assigned to cell [r2c7] without any contradiction in the logic -- I think. Is the second chain a valid chain?

Since (in my understanding of) a chain every step depends only on the step before it the chain is IMO valid.

Whether it makes sense is another question. It reminds me of the discussion in the ultimate fish thread about a degeneration clause: Your first chain causes r2c7=3 which implies r2c2<>3, the second chain is therefore redundant.

Besides you don't assign two different values to r2c7, you only prove that your initial assumption (r2c2=3) produces a contradiction in r2c7. Seen as a forcing chain, the second chain should probably stop the second time it hits r2c7 (mine doesn't too).
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Tue Dec 30, 2008 11:42 am

This single AIC, which has no weak inferences (links) at the chain ends ...
Code: Select all
(5)r2c2 = (5)r2c7 - (5)r3c9 = (5-2)r3c5 = (2-3)r4c5 = (3)r4c9 - (3)r13c9 = (3)r2c7 => r2c2<>3, r2c7<>5

... is equivalent to this pair of nice loops:
Code: Select all
         r2c2 =5= r2c7 -5- r3c9 =5= r3c5 =2= r4c5 =3= r4c9 -3- r13c9 =3= r2c7 -3- r2c2 => r2c2<>3

r2c7 -5- r2c2 =5= r2c7 -5- r3c9 =5= r3c5 =2= r4c5 =3= r4c9 -3- r13c9 =3= r2c7          => r2c7<>5

But short and elegant, they're not.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Tue Dec 30, 2008 2:11 pm

hobiwan wrote:Your first chain causes r2c7=3 which implies r2c2<>3, the second chain is therefore redundant.

Yes.

ronk: Your answer hits at the core of what I was trying to reconcile. I've seen storm_norm post chains like the first below. I was looking for examples to help me decide which of the next two chains would be appropriate to support the scenario with two eliminations. Your Eureka chain answers more than I asked. Thanks!

Code: Select all
[cell]   =>   starting cell
[peer]   =>   a peer cell of [cell]

[cell]=n= ... =m=[peer]           =>             [peer]<>n   (ala storm_norm)

Code: Select all
[cell]=n= ... =m=[peer]           =>  [cell]<>m, [peer]<>n   (possibility #1)

-or-

[cell]=n= ... =m=[peer]-m-[cell]  =>  [cell]<>m, [peer]<>n   (possibility #2)

Thanks to both of you for confirming that a chain may have contradicting statements and still be valid.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Tue Dec 30, 2008 2:54 pm

daj95376 wrote:Thanks to both of you for confirming that a chain may have contradicting statements and still be valid.

Although I used the AIC and nice loop terms, I think that contradiction makes it a lasso, ala Denis Berthier. Using another analogy, the structure is like the frame of a badminton racket ... with the r2c2 to r2c7 segment being the handle.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to General