Continuous multiple inference loop?

Advanced methods and approaches for solving Sudoku puzzles

Continuous multiple inference loop?

Postby doduff » Fri Jun 02, 2006 9:48 pm

Here is a puzle from the top50000 which I got of some other site.

Code: Select all
 *-----------*
 |.6.|...|..9|
 |...|7.1|2..|
 |..3|.2.|...|
 |---+---+---|
 |.54|3..|...|
 |8..|.1.|..2|
 |...|..9|86.|
 |---+---+---|
 |...|.4.|3..|
 |..6|5.8|...|
 |7..|...|.1.|
 *-----------*


 *-----------*
 |.6.|8..|..9|
 |...|761|2..|
 |..3|92.|...|
 |---+---+---|
 |654|382|...|
 |8..|61.|..2|
 |...|4.9|86.|
 |---+---+---|
 |...|14.|3..|
 |..6|5.8|.2.|
 |7..|2..|.1.|
 *-----------*

 
 *-----------------------------------------------------------------------------*
 | 1245    6       1257    | 8       35      345     | 1457    457     9       |
 | 459     489     589     | 7       6       1       | 2       3458    3458    |
 | 145     1478    3       | 9       2       45      | 14567   4578    145678  |
 |-------------------------+-------------------------+-------------------------|
 | 6       5       4       | 3       8       2       | 179     79      17      |
 | 8       379     79      | 6       1       57      | 45      345     2       |
 | 123     1237    127     | 4       57      9       | 8       6       35      |
 |-------------------------+-------------------------+-------------------------|
 | 259     289     2589    | 1       4       67      | 3       5789    5678    |
 | 134     134     6       | 5       379     8       | 479     2       47      |
 | 7       34      589     | 2       39      36      | 4569    1       4568    |
 *-----------------------------------------------------------------------------*


There is a seemingly continuous multiple inference loop here:

Image

[r8c5]=7=[r6c5](-7-[r5c6]-5-[r3c6]-4-[r1c6])=5=[r1c5]-5-[r1c6]-3-[r9c6]-6-[r6c6]-7-[r8c5] => [r1c1367]<>5 ?

The weak(-5) inference in row 1 wants to be a strong(3) inference it seems like, but this would destroy continuity, if this is continuous that is.

Any thoughts?

It seems like no eliminations can be made from this loop. Using the rule for double implication chains, I want to eliminate the 5's from row 1, and although this is a valid elimination, does the loop above allow me to do so?
doduff
 
Posts: 32
Joined: 29 May 2006

Postby RW » Fri Jun 02, 2006 10:30 pm

When uncertain, the question you should ask yourself is: If r1c1, r1c3, r1c6 or r1c7=5, would it cause a contradiction when I try to fill the mentioned cells? If the answer is yes, then the elimination is valid. If the answer is no, then you cannot eliminate the candidates unless you expand your loop to other cells. I had no problem assigning the value 5 to all of the four cells (one at a time of course) and then fill in the cells you mentioned in your loop without causing any contradictions => eliminations are not valid.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby doduff » Sat Jun 03, 2006 12:14 am

AH.. thats a good check. Thanks.
doduff
 
Posts: 32
Joined: 29 May 2006

Postby daj95376 » Sat Jun 03, 2006 4:07 am

Code: Select all
*-----------------------------------------------------------------------------*
 | 1245    6       1257    | 8       35      345     | 1457    457     9       |
 | 459     489     589     | 7       6       1       | 2       3458    3458    |
 | 145     1478    3       | 9       2       45      | 14567   4578    145678  |
 |-------------------------+-------------------------+-------------------------|
 | 6       5       4       | 3       8       2       | 179     79      17      |
 | 8       379     79      | 6       1       57      | 45      345     2       |
 | 123     1237    127     | 4       57      9       | 8       6       35      |
 |-------------------------+-------------------------+-------------------------|
 | 259     289     2589    | 1       4       67      | 3       5789    5678    |
 | 134     134     6       | 5       379     8       | 479     2       47      |
 | 7       34      589     | 2       39      36      | 4569    1       4568    |
 *-----------------------------------------------------------------------------*

Setting [r6c5]=5 leads to a cascade of singles that solve the puzzle. Unfortunately, setting [r6c5]=7 and getting a contradiction is outside my reach. Ack!
Last edited by daj95376 on Wed Sep 13, 2006 5:41 am, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby doduff » Sat Jun 03, 2006 6:19 am

I have tried so many different chains. They are all so long and complicated. I feel like there should be come reasonable chain that I can get something out of. I just can't find it!!!!

I played with r6c5 for a long time and came up with only continuous loops that lead to no eliminations or single chains that lead nowhere and can't be connected in any obvious way(to me at least).

Maybe some one will grace me with a next step!
doduff
 
Posts: 32
Joined: 29 May 2006

Here is a possible solution

Postby Carcul » Sun Jun 04, 2006 10:57 am

Code: Select all
 *------------------------------------------------------*
 | 1245  6     1257 | 8  35   345 | 1457   3457  9      |
 | 459   489   589  | 7  356  1   | 2      3458  34568  |
 | 145   1478  3    | 9  2    456 | 14567  4578  145678 |
 |------------------+-------------+---------------------|
 | 6     5     4    | 3  8    2   | 179    79    17     |
 | 8     379   79   | 6  1    57  | 45     345   2      |
 | 123   1237  127  | 4  57   9   | 8      6     35     |
 |------------------+-------------+---------------------|
 | 259   289   2589 | 1  4    67  | 3      5789  5678   |
 | 134   134   6    | 5  379  8   | 479    2     47     |
 | 7     34    589  | 2  369  36  | 4569   1     4568   |
 *------------------------------------------------------*

1. [r2c5]=6=[r2c9]=3=[r6c9]=5=[r6c5](-5-[r2c5])-5-[r1c5]
-3-[r2c5], => r2c5<>3,5.

2. [r89c7]-4-[r5c7]=4=[r5c8]=3=[r6c9]=5=[r6c5]=7=[r8c5]
-7-[r8c9]-4-[r89c7], => r8c7/r9c7<>4.

3. [r6c2]=2=[r7c2]-2-[r7c3]=2|7=[r5c3]-7-[r6c2], => r6c2<>7.

4. [r3c7]=6=[r9c7]-6-[r7c9]=6=[r7c6]=7=[r5c6]-7-[r5c2]=7=
[r3c2]-7-[r3c7], => r3c7<>7.

5. [r2c9]=3=[r6c9]=5=[r6c5]=7=[r5c6]-7-[r5c2]=7=[r3c2]=8=
[r2c23]-8-[r2c9], => r2c9<>8.

6. [r1c1]=2=[r1c3]=1=[r6c3]=7=[r6c5]=5=[r1c5]-5-[r1c13],
=> r1c1/r1c3<>5.

7. [r1c78]-5-[r2c9]=5=[r6c9]-5-[r6c5]=5=[r1c5]-5-[r1c78],
=> r1c7/r1c8<>5.

8. [r7c9]=6=[r7c6]=7=[r5c6](=5=[r5c78]-5-[r6c9]=5=[r2c9]
-5-[r2c3])-7-[r5c3]-9-[r2c3]-8-[r9c3]=8=[r9c9]-8-[r7c9],
=> r7c9<>8.

9. =4=[r2c2]-{Nice Loop: [r9c3]-8-[r7c2]=8=[r3c2]-8-[r3c9]
=8=[r9c9]-8-[r9c3]}-8-[r9c3]=8=[r9c9]=4=[r9c2]-4-[r2c2],
=> r2c2<>4.

10. [r7c2]-9-[r7c1]=9=[r2c1]=4=[r1c1]=2=[r1c3]-2-[r7c3]=2|7=[r5c3]
=9=[r5c2]-9-[r7c2], => r7c2<>9.

11. [r7c3]=2|7=[r5c3]=9=[r5c2]-9-[r2c2]-8-[r7c2]-2-[r7c3],
=> r3c2<>8; r7c1<>2.

12. [r3c8]=8=[r7c8]-8-[r7c2]-2-[r7c3]=2|7=[r5c3]-7-[r5c2]=7=
[r3c2]-7-[r3c8], => r3c8<>7.

13. [r4c8]=9=[r7c8]-9-[r7c1]=9=[r2c1]=4=[r1c1]-4-[r1c8]-7-
[r4c8], => r4c8<>7.

14. [r6c1]=2=[r1c1]=4=[r2c1]-4-[r2c8]=4=[r5c8]=3=[r5c2]
-3-[r6c1], => r6c1<>3.

15. [r6c5]-7-[r6c3]=7|4=[r1c1]-4-[r1c7]-1-[r4c7]-7-[r8c7]=7=
[r8c5]-7-[r6c5], => r6c5<>7 and the puzzle is solved.

In step "9" I have used an Almost Nice Loop.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Jeff » Sun Jun 04, 2006 1:06 pm

Previous post deleted due to incorrect strong link drawn.
Thanks Carcul.

Here is another one:

Image
Last edited by Jeff on Mon Jun 05, 2006 4:00 am, edited 2 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Sun Jun 04, 2006 1:13 pm

Hi Jeff.

Nice to see you around here. Just to note that, in your b/b plot, the strong link "[r1c3]=1=[r5c3]" is wrong: it should be "[r1c3]=1=[r6c3]".

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby doduff » Fri Jun 09, 2006 3:42 am

Thanks for the help.

I found some cool chains. Here is one I am particularly proud of, but don't know how would be the best way to notate it.

Code: Select all
State if the puzzle:
 
 *--------------------------------------------------------------------*
 | 1245   6      127    | 8      35     345    | 1457   457    9      |
 | 459    489    589    | 7      6      1      | 2      3458   358    |
 | 145    178    3      | 9      2      45     | 14567  4578   15678  |
 |----------------------+----------------------+----------------------|
 | 6      5      4      | 3      8      2      | 17     9      17     |
 | 8      379    79     | 6      1      57     | 45     345    2      |
 | 123    1237   127    | 4      57     9      | 8      6      35     |
 |----------------------+----------------------+----------------------|
 | 259    289    2589   | 1      4      67     | 3      578    5678   |
 | 134    134    6      | 5      379    8      | 79     2      47     |
 | 7      34     58     | 2      39     36     | 569    1      4568   |
 *--------------------------------------------------------------------*



============

Chains:

If [r2c9]=3 => [r6c9]=5 => [r379c9]<>5

If [r2c9]=5 => [r379c9]<>5

If [r2c9]=8 => [r2c123]<>8 and is locked on 459 => [r136c1]<>45 and is locked on 123 => [r6c9]<>3 and is thus 5 so [r379c9]<>5

So [r379c9]<>5

============

Maybe write like this:

[r379c9]-5-[r6c9]-3-[r2c9]-{ANL:[r2c9]-5-[(r6c9)]-3-[ALS:r5c78]=3=[r5c2]-3-[almostALS:r136c1]=3|8=[ALS:r2c123]-8-[r2c9]}-5-[r379c9] => [r79c9]<>5

Where there is an almost almost locked set in there. Does that notation make sense?

I have since found a few more loops but still need about 9 more eliminations to match Carcul's solution.

Now let me ask this: Carcul, how do you go about finding your chains? Do you have any special techniques that you would like to share?

Thanks,Joe
doduff
 
Posts: 32
Joined: 29 May 2006

Postby Carcul » Fri Jun 09, 2006 8:35 am

Hi Doduff.

I am pleased to see that finally someone decided to try to use the ANL concept. However, you use it in a somewhat confusing fashion and it is more simple to write the deduction without the ANL. Check this:

[r379c9]-5-[r6c9](-3-[r2c9])-3-[r1236c1|r2c23]=3|8=[r2c23]-8-[r2c9]-5-
-[r379c9], => r3c9/r7c9/r9c9<>5.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby daj95376 » Fri Jun 09, 2006 9:16 am

If you allow chains to resolve Naked/Hidden Singles, then the original puzzle can be solved as follows.

Code: Select all
r4c5    =  8     Hidden Single
r4c1    =  6     Hidden Single
r4c6    =  2     Hidden Single
r6c4    =  4     Naked  Single
r1c4    =  8     Naked  Single
r5c4    =  6     Naked  Single
r3c4    =  9     Naked  Single
r9c4    =  2     Naked  Single
r7c4    =  1     Naked  Single
    b6  -  179   Naked  Triple
    b7  -  134   Hidden Triple
r8c8    =  2     Hidden Single
r9c2    =  4     [r9c2]=3 => [r5c3]=EMPTY
r8      -  13    Naked  Pair
r9c6    =  3     [r9c6]=6 => [r9]=INVALID
r9c5    =  9     [r9c5]=6 => [c7]=INVALID
                 trivial from here


If you only allow chains to resolve Naked Singles, then the original puzzle can be solved as follows.

Code: Select all
r4c5    =  8     Hidden Single
r4c1    =  6     Hidden Single
r4c6    =  2     Hidden Single
r6c4    =  4     Naked  Single
r1c4    =  8     Naked  Single
r5c4    =  6     Naked  Single
r3c4    =  9     Naked  Single
r9c4    =  2     Naked  Single
r7c4    =  1     Naked  Single
    b6  -  179   Naked  Triple
    b7  -  134   Hidden Triple
r8c8    =  2     Hidden Single
r9c5    <> 3     [r9c5]=3 => [r9]=INVALID
r9c5    =  9     [r9c5]=6 => [c7]=INVALID
r8c7    =  9     Hidden Single
r4c8    =  9     Hidden Single
r2c5    =  6     Hidden Single
    b2  -  3     Locked Candidate (1)
r5c3    =  9     [r5c3]=7 => [r8c1]=EMPTY
  c3    -  58    Naked  Pair
r7c3    =  2     Naked  Single
r1c1    =  2     Hidden Single
r6c2    =  2     Hidden Single
r9c6    =  3     [r9c6]=6 => [c3]=INVALID
                 trivial from here
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby doduff » Fri Jun 09, 2006 4:42 pm

Ah... That is a much batter way to denote it. I think the shorter the notation, then the better the chain.

Carcul wrote:[r379c9]-5-[r6c9](-3-[r2c9])-3-[r1236c1|r2c23]=3|8=[r2c23]-8-[r2c9]-5-
-[r379c9], => r3c9/r7c9/r9c9<>5.


Although I did group my cells just slightly 'differently'. -[r136c1|r2c123]=3|8=[r2c123]- instead of -[r1236c1|r2c23]=3|8=[r2c23]- but they are equivalent in some sense. I guess if one can avoid using an almost nice loop, then that should be the case. An almost nice loop should be used if it makes the chain clearer. I did feel that there was something funny about the way I did it.

Here is another use of an almost nice loop, but this one is way long and I kind of lucked out that it worked. I was going for an eliminations somewhere else, but found an error in my reasoning, but luckily it was fixed by changing only 3 links.

Code: Select all
 The state of the puzzle:
 *-----------------------------------------------------------*
 | 1245  6     127   | 8     35    345   | 147   47    9     |
 | 459   489   589   | 7     6     1     | 2     3458  35    |
 | 145   178   3     | 9     2     45    | 156   4578  1678  |
 |-------------------+-------------------+-------------------|
 | 6     5     4     | 3     8     2     | 17    9     17    |
 | 8     379   79    | 6     1     57    | 45    345   2     |
 | 123   1237  127   | 4     57    9     | 8     6     35    |
 |-------------------+-------------------+-------------------|
 | 259   289   2589  | 1     4     67    | 3     578   678   |
 | 134   134   6     | 5     379   8     | 79    2     47    |
 | 7     34    58    | 2     39    36    | 569   1     468   |
 *-----------------------------------------------------------*


The 'Loop':
[r3c9](-7-[r8c9]-4-[ALS:r8c12]=4=[r9c2])-7-[r4c9]=7=[r4c7]-7-[r8c7]-9-[r9c7]=9=[r9c5]=3=[r9c6]=6=[r7c6]=7=[r5c6]=5=[r6c5]-{ANL:[r6c3]=7=[r6c2]-7-[r3c2]=7=[r1c3]=1=[r6c3]}-2-[r16c3]=2=[r7c3]-2-[r7c2]=2=[r6c2]=7=[r6c3]=1=[r1c3]-1-[ALS:r1c7|r1c8]-7-[r3c9] => [r3c9]<>7

Basically what I did was test each 3 in [r9c356]. Feel free to go through this loop and write it better too!

Thanks for the help!

daj: What do you mean by "only allowing chains to resolve naked/hidden singles"?
doduff
 
Posts: 32
Joined: 29 May 2006


Return to Advanced solving techniques