Contrary "17" Puzzles

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

Postby daj95376 » Mon Jun 02, 2008 10:49 pm

hobiwan wrote:Forcing Net Contradiction in [c9] => [r3c9]<>9
[r3c9]=9(=>[r456c9]<>9=>[r4c8]=9=>[r9c8]<>9=>[r9c8]=5=>[r9c4]<>5)...
...(=>[r456c9]<>9=>[r4c8]=9=>[r4c2]<>9)=>[r3c7]<>9=>[r7c7]=9=>[r7c2]<>9=>[r6c2]=9...
...(=>[r5c3]<>9)=>[r6c4]<>9=>[r6c4]=7=>[r9c4]<>7=>[r9c4]=9(=>[r8c5]<>9=>[r8c5]=6=>[r6c5]<>6)=>...
...[r9c4]<>7=>[r9c6]=7=>[r9c6]<>2=>[r6c6]=2=>[r6c6]<>6=>[r5c6]=6=>[r5c6]<>9=>[r5c9]=9

Ahhh!!!

Code: Select all
                                            r9c4=9 r8c5=6
                                          /               \
r3c9=9 r4c8=9 r9c8=5 r7c7=9 r6c2=9 r6c4=7                   r5c6=6 [r5]~9 => [r3c9]<>9
                                          \               /
                                            r9c6=7 r6c6=2
______________________________________________________________________________________
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby hobiwan » Tue Jun 03, 2008 7:12 am

daj95376 wrote:Ahhh!!!

Code: Select all
                                            r9c4=9 r8c5=6
                                          /               \
r3c9=9 r4c8=9 r9c8=5 r7c7=9 r6c2=9 r6c4=7                   r5c6=6 [r5]~9 => [r3c9]<>9
                                          \               /
                                            r9c6=7 r6c6=2
______________________________________________________________________________________


Certainly a valid net that leads to the same elimination, but not the one I had in mind. There really is a notation problem with complicated nets. I admit, that the spelled out version I posted is hard to read, but on the other hand, which parts of the net should be spelled out and which not? A last try:

Code: Select all
Forcing Net Contradiction in [c9]:
[r3c9]=9 [r7c7]=9 [r6c2]=9(1) [r6c4]=7 [r9c6]=7 [r6c6]=2 [r5c6]=6(2) [r5c9]=9(3)

(1): r3c9=9 r4c8=9 r4c2<>9
(2): r3c9=9 r4c8=9 r9c8=5 r9c4<>5 and r6c4=7 r9c4<>7 =>
     r9c4=9 r8c5=6 r6c5<>6
(3): r6c2=9 r5c3<>9

(I noticed I had an error in the original abbreviated version: r9c4=9 does not belong to the main chain; also my net is too long: your end with [r5]~9 ist shorter than my [c9]~9)

Perhaps a complete but readable version would be:
Code: Select all
r3c9=9 (r4c8=9 r4c2<>9) (r4c8=9 r9c8=5 r9c4<>5) r7c7=9 r6c2=9 (r5c3<>9) r6c4=7 (r9c4=9 r8c5=6 r6c5<>6) r9c6=7 r6c6=2 r5c6=6 r5c9=9
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Tue Jun 03, 2008 1:21 pm

#47416
Code: Select all
.7....3.....61.......2.8...2...5....4.....7........18....4...62..1.......3.......

daj95376's starting pencilmarks here
Code: Select all
 8     7     2     | 59    49    459   | 3     1     6
 59    4     59    | 6     1     3     | 2     7     8
 1     6     3     | 2     7     8     | 59    459   49
-------------------+-------------------+------------------
 2    B189  B789   | 13    5     49-7  | 6     49    349
 4    B15   B569   | 13    8    A69    | 7     2     359
 3    B59    569-7 |A79    2469  24679 | 1     8     459
-------------------+-------------------+------------------
 7     589   589   | 4     3     1     | 59    6     2
 569   2     1     | 8     69    569   | 4     3     7
 569   3     4     | 579   269   25679 | 8     59    1

1a) ALS xz-rule: A = {r5c6,r6c4} = {679}; B = {r456c2,r45c3} = {156789}; x,z=6,7; r4c6,r6c3<>7
1b) singles
Code: Select all
 8     7     2     | 59    49    459   | 3     1     6
 59    4     59    | 6     1     3     | 2     7     8
 1     6     3     | 2     7     8     | 59    459   49
-------------------+-------------------+------------------
 2     8     7     | 1     5    B49    | 6    b49    3
 4     1     569   | 3     8     69    | 7     2     59
 3    a59    569   | 7-9   246-9 2467-9| 1     8     459
-------------------+-------------------+------------------
 7    A59    8     | 4     3     1     |a59    6     2
 569   2     1     | 8     69    569   | 4     3     7
 569   3     4     | 579   269   25679 | 8    A59    1

2a) multi-coloring: r6c456 -9- r6c2 =9= r7c2 -9- r7c7 =9= r9c8 -9- r4c8 =9= r4c6 -9- r6c456 ==> r6c456<>9
2b) singles
3) locked candidates: (9)b5\c6 ==> r18c6<>9
Code: Select all
 8   7   2   | 5-9 49 *45  | 3   1   6
 59  4   59  | 6   1   3   | 2   7   8
 1   6   3   | 2   7   8   | 59  459 49
-------------+-------------+------------
 2   8   7   | 1   5  *49  | 6  *49  3
 4   1   569 | 3   8   69  | 7   2   59
 3   59  569 | 7   46  2   | 1   8   459
-------------+-------------+------------
 7   59  8   | 4   3   1   | 59  6   2
 59  2   1   | 8   69  56  | 4   3   7
 6   3   4   |*59  2   7   | 8  *59  1

4a) b/b chain: r1c4 =5= r1c6 =4= r4c6 =9= r4c8 -9- r9c8 =9= r9c4 -9- r1c4 ==> r1c4<>9
4b) singles to end
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Tue Jun 03, 2008 5:58 pm

hobiwan wrote:There really is a notation problem with complicated nets.

After reviewing Jeff's thread on Forcing Chains, and reviewing Sudopedia's article on Forcing Nets, I hope the following is a more accurate way to present my original contradiction network for #47416.

Code: Select all
 +-----------------------------------------------------------------------+
 |  8      7      2      |  59     49     459    |  3      1      6      |
 |  59     4      59     |  6      1      3      |  2      7      8      |
 |  1      6      3      |  2      7      8      |  59     459    49     |
 |-----------------------+-----------------------+-----------------------|
 |  2      189    789    |  13     5      479    |  6      49     349    |
 |  4      15     569    |  13     8      69     |  7      2      359    |
 |  3      59     5679   |  79     2469   24679  |  1      8      459    |
 |-----------------------+-----------------------+-----------------------|
 |  7      589    589    |  4      3      1      |  59     6      2      |
 |  569    2      1      |  8      69     569    |  4      3      7      |
 |  569    3      4      |  579    269    25679  |  8      59     1      |
 +-----------------------------------------------------------------------+

Code: Select all
r3c9=9 (r5c9<>9) r3c8=4 r9c8=5 (r9c1<>5) r8c6=5 (r1c6<>5) r2c1=5 r2c3=9 ...

                    r6c4=7
           /               \
... r5c6=9                   contradiction!  =>  r3c9<>9
           \               /
             r1c6=4 r4c6=7

The critical side-effect eliminations are contained in parentheses; and there are two implication streams from the same assumption that lead to a contradiction. Each stream is the same through r5c6=9.

As for how I manually replay a solution:

Code: Select all
9r3c9 4r3c8 5r9c8 5r8c6 5r2c1 9r2c3 9r5c6 4r1c6 [b5]~7

Code: Select all
1) Start up Simple Sudoku and uncheck Edit Menu -> Block Invalid Moves
2) Actually perform the assignments listed from my solver
   (each assignment should appear to be valid because of side-effect eliminations)
3) When the grid becomes invalid, then the original assignment is deemed invalid

Actually: (each assignment ...) should be (each assignment except the first ...).

[Edit: corrected a typo for elimination in r9c1 and dropped r8c1<>5 as a side-effect elimination]
Last edited by daj95376 on Tue Jun 03, 2008 8:09 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby hobiwan » Tue Jun 03, 2008 6:39 pm

ronk wrote:1a) ALS xz-rule: A = {r5c6,r6c4} = {679}; B = {r456c2,r45c3} = {156789}; x,z=6,7; r4c6,r6c3<>7


ronk, do you search for all ALS xz in the grid (for a certain elimination) or do you stop after you found the first step? If you search for all, what are your sorting criteria?
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby hobiwan » Tue Jun 03, 2008 6:55 pm

daj95376 wrote:
Code: Select all
r3c9=9 (r5c9<>9) r3c8=4 r9c8=5 (r9c1<>1) r8c6=5 (r1c6,r8c1<>5) r2c1=5 r2c3=9 ...

                    r6c4=7
           /               \
... r5c6=9                   contradiction!  =>  r3c9<>9
           \               /
             r1c6=4 r4c6=7

I had no trouble following your net before, I am just struggeling to find a nice presentation. I think the above is a good compromise between completeness and readability. I originally modelled my solver output after Jeffs thread too, but the result was an unreadable monster. Leaving out the "=>" and "[]" makes it much easier, and leaving out the "<>"-steps (except for ends of branches) is a good thing too.

I probably still would write your net as two seperate nets, but only because I don't want to code the branching for non fixed spaced fonts:D . Unfortunately this has a drawback too: When I search for chains/nets I take only the solutions with the shortest chains. That makes my solver discard your net in favour of mine, because the two seperate chains are longer than the one. Well, I think I have spent enough time with chains and nets for now (coding them, not using them)...
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Tue Jun 03, 2008 7:38 pm

hobiwan wrote:
ronk wrote:1a) ALS xz-rule: A = {r5c6,r6c4} = {679}; B = {r456c2,r45c3} = {156789}; x,z=6,7; r4c6,r6c3<>7
do you search for all ALS xz in the grid (for a certain elimination) or do you stop after you found the first step?

My solver's ALS-xz search begins with the smallest (fewest total cells in sets A & B) and stops as soon as it finds one. In this particular puzzle it found two smaller ones which didn't contribute to the ultimate solution path, so I discarded them.

For any given size, I think the search is non-exhaustive.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Tue Jun 03, 2008 8:11 pm

ronk wrote:My solver's ALS-xz search begins with the smallest (fewest total cells in sets A & B) and stops as soon as it finds one.
My solver goes for smallest sets (seperate size) so 3+3 will be found before 4+1 & 4+4 before 5+3. Total cells seems to be better:(:idea:

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby hobiwan » Wed Jun 04, 2008 6:18 am

ronk wrote:My solver's ALS-xz search begins with the smallest (fewest total cells in sets A & B) and stops as soon as it finds one. In this particular puzzle it found two smaller ones which didn't contribute to the ultimate solution path, so I discarded them.

For any given size, I think the search is non-exhaustive.


What about:

Almost Locked Set XZ-Rule: A=[r2457c3] - {56789}, B=[r5c6],[r6c4] - {679}, X=6, Z=7 => [r4c6],[r6c3]<>7
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Wed Jun 04, 2008 5:56 pm

hobiwan wrote:
ronk wrote:For any given size, I think the search is non-exhaustive.

What about:

Almost Locked Set XZ-Rule: A=[r2457c3] - {56789}, B=[r5c6],[r6c4] - {679}, X=6, Z=7 => [r4c6],[r6c3]<>7

Certainly smaller, which is why I wrote my search is non-exhaustive.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby hobiwan » Wed Jun 04, 2008 8:56 pm

ronk wrote:Certainly smaller, which is why I wrote my search is non-exhaustive.


Sorry, misunderstanding on my part.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Wed Jun 04, 2008 9:14 pm

hobiwan wrote:
ronk wrote:Certainly smaller, which is why I wrote my search is non-exhaustive.

Sorry, misunderstanding on my part.

No problem, maybe that'll motivate me to upgrade.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Thu Jun 05, 2008 12:26 am

How about:

Code: Select all
7= r6c3 =6= r5c3 -6- r5c6 -9- r6c4 -7- r6c3   =>  r6c3<>7

and ignore all of the extraneous cells.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Thu Jun 05, 2008 3:43 am

daj95376 wrote:How about:

Code: Select all
7= r6c3 =6= r5c3 -6- r5c6 -9- r6c4 -7- r6c3   =>  r6c3<>7

and ignore all of the extraneous cells.

Better yet. Using the original pencilmarks then, this puzzle may be solved with 4 (non-singles) steps using a total of 11 strong inferences.

1a) b/b chain: r6c3 =6= r5c3 -6- r5c6 -9- r6c4 -7- r6c3 ==> r6c3<>7
1b) singles
2a) multi-coloring: r6c456 -9- r6c2 =9= r7c2 -9- r7c7 =9= r9c8 -9- r4c8 =9= r4c6 -9- r6c456 ==> r6c456<>9
2b) singles
3) locked candidates: (9)b5\c6 ==> r18c6<>9
4a) b/b chain: r1c4 =5= r1c6 =4= r4c6 =9= r4c8 -9- r9c8 =9= r9c4 -9- r1c4 ==> r1c4<>9
4b) singles to end

I see that as more elegant than a single net that uses a similar number of strong inferences. If that single net used considerably fewer strong inferences, however, I'd probably have to vote for the net.

The strong inference counts from the above: 3, 3, 1, 4
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Thu Jun 05, 2008 5:24 am

ronk wrote:I see that as more elegant than a single net that uses a similar number of strong inferences. If that single net used considerably fewer strong inferences, however, I'd probably have to vote for the net.

Very true. The puzzle does not need a contradiction net. I went off on a tangent because hobiwan mentioned looking for a single-step solution to cracking the puzzle. Then we got balled up in notation.

It seems to me that your (2a) could be replaced with a finned Franken Jellyfish. And, my solver chose an XY-Chain for (4a).

Thanks for putting us back on track!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Previous

Return to General