Are all of these simple nice loops?

Advanced methods and approaches for solving Sudoku puzzles

Are all of these simple nice loops?

Postby flip » Tue Mar 07, 2006 4:37 pm

This thread is started in response to a request by Jeff http://forum.enjoysudoku.com/posting.php?mode=quote&p=22463.
Jeff wrote:I am quite surprised you were able to find so many simple nice loops in this grid; perhaps after a few ALSs. I haven't completely solved this one yet. Would you like to open a new thread and post your full solution for us?

Jeff, I feel uneasy that you do not see many nice loops, so I'll appreciate it if you and the other Nice Guys can check my interpretation. I am sure about the implications, but maybe they are not all nice loops according to your definition.
Maybe I have to go back to school on this:) .
There are 10 simple loops (longest 6 links), 7 ALSs and 1 unique rectangle (type 1).
The rest is very basic (singles, locked candidates and 1 naked pair). I think the trick to solving this puzzle lies in finding the right ALSs.
If anyone who reads this is still working on this puzzle or wants to try it first, he should stop reading now.
Code: Select all
 *-----------*
 |1.8|4..|5..|
 |...|..7|..2|
 |...|...|...|
 |---+---+---|
 |.2.|.9.|..7|
 |.6.|.5.|.89|
 |9..|.1.|.4.|
 |---+---+---|
 |...|...|...|
 |5..|6..|...|
 |..4|..3|9.8|
 *-----------*

  1*     379    8*        4*      236   269       5*      3679    36
  346    3459   3569      13589   368   7*        13468   1369    2*
  23467  34579  235679    123589  2368  125689    134678  13679   1346
  348    2*     135       38      9*    468       136     1356    7*
  347    6*     137       237     5*    24        123     8*      9*
  9*     3578   357       2378    1*    268       236     4*      356
  23678  13789  123679    125789  2478  124589    123467  123567  13456
  5*     13789  12379     6*      2478  12489     12347   1237    134
  267    17     4*        1257    27    3*        9*      12567   8*

locked candidates 1: square-1 row-3 digit=2
locked candidates 2: square-1 col-2 digit=4
locked candidates 2: square-2 col-5 digit=3
locked candidates 2: square-2 col-5 digit=6
locked candidates 1: square-4 col-3 digit=1
locked candidates 1: square-5 col-6 digit=4
locked candidates 1: square-5 col-4 digit=7
locked candidates 1: square-6 col-7 digit=2

[r6c6]=6=[r4c6]=4=[r4c1]=8=[r6c2]-8-[r6c6] => [r6c6]<>8
  1*     379    8*        4*     236   29       5*      3679    36
  36     3459   3569      1589   368   7*       13468   1369    2*
  2367   34579  235679    1589   368   1589     134678  13679   1346
  348    2*     135       38     9*    468      136     1356    7*
  347    6*     137       237    5*    24       123     8*      9*
  9*     3578   357       2378   1*    268      236     4*      356
  23678  13789  23679     12589  2478  12589    13467   123567  13456
  5*     13789  2379      6*     2478  1289     1347    1237    134
  267    17     4*        125    27    3*       9*      12567   8*

[r7c4]-8-[r6c4]=8=[r6c2]-8-[r4c1]=8=[r7c1]-8-[r7c4] => [r7c4]<>8
  1*     379    8*        4*     236   29       5*      3679    36
  36     3459   3569      1589   368   7*       13468   1369    2*
  2367   34579  235679    1589   368   1589     134678  13679   1346
  348    2*     135       38     9*    468      136     1356    7*
  347    6*     137       237    5*    24       123     8*      9*
  9*     3578   357       2378   1*    26       236     4*      356
  23678  13789  23679     12589  2478  12589    13467   123567  13456
  5*     13789  2379      6*     2478  1289     1347    1237    134
  267    17     4*        125    27    3*       9*      12567   8*

als A=2368@{r1c5,r2c5,r3c5} B=12589@{r2c4,r3c4,r7c4,r9c4} rc=8 c=2
    eliminate 2@r7c5 2@r8c5 2@r9c5
als C=2478@{r7c5,r8c5,r9c5} B=12589@{r2c4,r3c4,r7c4,r9c4} rc=2 c=8
    eliminate 8@r2c5 8@r3c5
  1*     379    8*        4*    236   29       5*      3679    36
  36     3459   3569      1589  368   7*       13468   1369    2*
  2367   34579  235679    1589  368   1589     134678  13679   1346
  348    2*     135       38    9*    468      136     1356    7*
  347    6*     137       237   5*    24       123     8*      9*
  9*     3578   357       2378  1*    26       236     4*      356
  23678  13789  23679     1259  2478  12589    13467   123567  13456
  5*     13789  2379      6*    2478  1289     1347    1237    134
  267    17     4*        125   27    3*       9*      12567   8*

naked single: 7@r9c5, 1@r9c2
hidden single: 2@r1c5 in col-5
naked single: 9@r1c6
hidden single: 9@r7c4 in square-8
locked candidates 2: square-2 col-4 digit=1
locked candidates 2: square-3 row-1 digit=6
locked candidates 2: square-8 col-5 digit=8
naked pair: 36 in row-2

unique rectangle 1: r2c5-r3c5-r2c1-r3c1 eliminate 3@r3c1 6@r3c1
  1*     37     8*        4*    2*  9*     5*     367     36
  36     459    59        158   36  7*     148    19      2*
  2367   34579  235679    158   36  58     13478  1379    134
  348    2*     135       38    9*  468    136    1356    7*
  347    6*     137       237   5*  24     123    8*      9*
  9*     3578   357       2378  1*  26     236    4*      356
  23678  378    2367      9*    48  125    13467  123567  13456
  5*     3789   2379      6*    48  12     1347   1237    134
  26     1*     4*        25    7*  3*     9*     256     8*

als A=2367@{r1c2,r2c1,r3c1} B=26@{r9c1} rc=26
    eliminate 3@r3c2 7@r3c2 3@r3c3 7@r3c3 6@r7c1
als A=367@{r1c2,r2c1} B=267@{r3c1,r9c1} rc=67
    eliminate 3@r3c2 7@r3c2 3@r3c3 7@r3c3 2@r7c1
als A=34579@{r1c2,r2c2,r2c3,r3c2} B=2367@{r2c1,r3c1,r9c1} rc=37
    eliminate 5@r3c3 7@r3c3 9@r3c3 2@r7c1 6@r7c1
  1*     37     8*        4*    2*  9*     5*     367     36
  36     459    59        158   36  7*     148    19      2*
  27     34579  235679    158   36  58     13478  1379    134
  348    2*     135       38    9*  468    136    1356    7*
  347    6*     137       237   5*  24     123    8*      9*
  9*     3578   357       2378  1*  26     236    4*      356
  23678  378    2367      9*    48  125    13467  123567  13456
  5*     3789   2379      6*    48  12     1347   1237    134
  26     1*     4*        25    7*  3*     9*     256     8*

[r4c8]-1-[r2c8]-9-[r2c3]-5-[r4c3]=5=[r4c8] => [r4c8]<>1
  1*   37    8*      4*    2*  9*     5*     367     36
  36   459   59      158   36  7*     148    19      2*
  27   459   26      158   36  58     13478  1379    134
  348  2*    135     38    9*  468    136    1356    7*
  347  6*    137     237   5*  24     123    8*      9*
  9*   3578  357     2378  1*  26     236    4*      356
  378  378   2367    9*    48  125    13467  123567  13456
  5*   3789  2379    6*    48  12     1347   1237    134
  26   1*    4*      25    7*  3*     9*     256     8*

locked candidates 1: square-6 col-7 digit=1
[r6c9]-6-[r6c6]=6=[r4c6]=8=[r3c6]=5=[r7c6]-5-[r7c9]=5=[r6c9] => [r6c9]<>6
  1*   37    8*      4*    2*  9*     5*    367     36
  36   459   59      158   36  7*     48    19      2*
  27   459   26      158   36  58     3478  1379    134
  348  2*    135     38    9*  468    136   356     7*
  347  6*    137     237   5*  24     123   8*      9*
  9*   3578  357     2378  1*  26     236   4*      356
  378  378   2367    9*    48  125    3467  123567  13456
  5*   3789  2379    6*    48  12     347   1237    134
  26   1*    4*      25    7*  3*     9*    256     8*

als A=356@{r4c8,r6c9} B=3468@{r4c1,r4c4,r4c6} rc=6 c=3
    eliminate 3@r4c7
  1*   37    8*      4*    2*  9*     5*    367     36
  36   459   59      158   36  7*     48    19      2*
  27   459   26      158   36  58     3478  1379    134
  348  2*    135     38    9*  468    136   356     7*
  347  6*    137     237   5*  24     123   8*      9*
  9*   3578  357     2378  1*  26     236   4*      35
  378  378   2367    9*    48  125    3467  123567  13456
  5*   3789  2379    6*    48  12     347   1237    134
  26   1*    4*      25    7*  3*     9*    256     8*

[r6c2]=8=[r4c1]-8-[r4c6]=8=[r3c6]=5=[r7c6]-5-[r7c9]=5=[r6c9]-5-[r6c2] => [r6c2]<>5
  1*   37    8*      4*    2*  9*     5*    367     36
  36   459   59      158   36  7*     48    19      2*
  27   459   26      158   36  58     3478  1379    134
  348  2*    135     38    9*  468    16    356     7*
  347  6*    137     237   5*  24     123   8*      9*
  9*   3578  357     2378  1*  26     236   4*      35
  378  378   2367    9*    48  125    3467  123567  13456
  5*   3789  2379    6*    48  12     347   1237    134
  26   1*    4*      25    7*  3*     9*    256     8*

locked candidates 2: square-1 col-2 digit=5
naked single: 9@r2c3, 1@r2c8
hidden single: 1@r3c4 in square-2, 9@r3c8 in square-3,
hidden single: 9@r8c2 in square-7, 8@r8c5 in row-8
naked single: 4@r7c5
[r7c9]-3-[r3c9]-4-[r3c2]-5-[r3c6]=5=[r7c6]=1=[r7c9] => [r7c9]<>3
  1*   37   8*      4*    2*  9*     5*    367    36
  36   45   9*      58    36  7*     48    1*     2*
  27   45   26      1*    36  58     3478  9*     34
  348  2*   135     38    9*  468    16    356    7*
  347  6*   137     237   5*  24     123   8*     9*
  9*   378  357     2378  1*  26     236   4*     35
  378  378  2367    9*    4*  125    367   23567  1356
  5*   9*   237     6*    8*  12     347   237    134
  26   1*   4*      25    7*  3*     9*    256    8*

[r1c9]-3-[r3c9]-4-[r3c2]-5-[r3c6]=5=[r7c6]=1=[r7c9]=6=[r1c9] => [r1c9]<>3
  1*   37   8*      4*    2*  9*     5*    367    36
  36   45   9*      58    36  7*     48    1*     2*
  27   45   26      1*    36  58     3478  9*     34
  348  2*   135     38    9*  468    16    356    7*
  347  6*   137     237   5*  24     123   8*     9*
  9*   378  357     2378  1*  26     236   4*     35
  378  378  2367    9*    4*  125    367   23567  156
  5*   9*   237     6*    8*  12     347   237    134
  26   1*   4*      25    7*  3*     9*    256    8*

naked single: 6@r1c9
-[r2c4]-8-[r2c7]=8=[r3c7]=7=[r3c1]=2=[r9c1]-2-[r9c4]-5-[r2c4]-
  => [r3c7]<>3,[r3c7]<>4,[r9c8]<>2
  1*   37   8*      4*    2*  9*     5*    37     6*
  36   45   9*      58    36  7*     48    1*     2*
  27   45   26      1*    36  58     3478  9*     34
  348  2*   135     38    9*  468    16    356    7*
  347  6*   137     237   5*  24     123   8*     9*
  9*   378  357     2378  1*  26     236   4*     35
  378  378  2367    9*    4*  125    367   23567  15
  5*   9*   237     6*    8*  12     347   237    134
  26   1*   4*      25    7*  3*     9*    256    8*

[r6c9]-3-[r3c9]-4-[r3c2]-5-[r3c6]=5=[r7c6]-5-[r7c9]=5=[r6c9] => [r6c9]<>3
  1*   37   8*      4*    2*  9*     5*   37     6*
  36   45   9*      58    36  7*     48   1*     2*
  27   45   26      1*    36  58     78   9*     34
  348  2*   135     38    9*  468    16   356    7*
  347  6*   137     237   5*  24     123  8*     9*
  9*   378  357     2378  1*  26     236  4*     35
  378  378  2367    9*    4*  125    367  23567  15
  5*   9*   237     6*    8*  12     347  237    134
  26   1*   4*      25    7*  3*     9*   56     8*

naked single: 5@r6c9, naked single: 1@r7c9
hidden single: 5@r4c3 in square-4, 1@r5c3 in square-4
hidden single: 1@r4c7 in square-6, 1@r8c6 in square-8
als A=236@{r4c8,r5c7} B=256@{r9c4,r9c8} rc=6 c=2
    eliminate 2@r5c4
  1*   37   8*      4*    2*  9*     5*   37     6*
  36   45   9*      58    36  7*     48   1*     2*
  27   45   26      1*    36  58     78   9*     34
  348  2*   5*      38    9*  468    1*   36     7*
  347  6*   1*      237   5*  24     23   8*     9*
  9*   378  37      2378  1*  26     236  4*     5*
  378  378  2367    9*    4*  25     367  23567  1*
  5*   9*   237     6*    8*  1*     347  237    34
  26   1*   4*      25    7*  3*     9*   56     8*

[r4c8]-3-[r1c8]-7-[r3c7]-8-[r3c6]=8=[r4c6]=6=[r4c8] => [r4c8]<>3
  1*   37   8*      4*    2*  9*     5*   37     6*
  36   45   9*      58    36  7*     48   1*     2*
  27   45   26      1*    36  58     78   9*     34
  348  2*   5*      38    9*  468    1*   36     7*
  347  6*   1*      37    5*  24     23   8*     9*
  9*   378  37      2378  1*  26     236  4*     5*
  378  378  2367    9*    4*  25     367  23567  1*
  5*   9*   237     6*    8*  1*     347  237    34
  26   1*   4*      25    7*  3*     9*   56     8*

naked single: 6@r4c8, 5@r9c8, 2@r9c4, 5@r7c6, 8@r3c6, 5@r2c4
naked single: 4@r2c2, 8@r2c7, 5@r3c2, 7@r3c7, 3@r1c8, 7@r1c2
naked single: 2@r3c1, 6@r3c3, 3@r2c1, 6@r2c5, 3@r3c5, 4@r3c9
naked single: 4@r4c6, 8@r4c1, 3@r4c4, 7@r5c4, 4@r5c1, 2@r5c6
naked single: 3@r5c7, 3@r6c2, 7@r6c3, 8@r6c4, 6@r6c6, 2@r6c7
naked single: 7@r7c1, 8@r7c2, 6@r7c7, 2@r7c8, 3@r7c3, 2@r8c3
naked single: 4@r8c7, 7@r8c8, 3@r8c9, 6@r9c1,

Thanks in anticipation, flip
flip
 
Posts: 17
Joined: 08 January 2006

Re: Are all of these simple nice loops?

Postby Jeff » Tue Mar 07, 2006 5:38 pm

flip wrote:Jeff, I feel uneasy that you do not see many nice loops, so I'll appreciate it if you and the other Nice Guys can check my interpretation.

Congratulations, Flip for you are one hell of a Nice Guy indeed.:D Your simple nice loops are spot on and I am sure other Nice Guys would agree to this too. I know exactly the level of satisfaction you felt, being able to crack such a difficult puzzle digit by digit, as I have been there and done that. Would you consider exploring further into grouped nice loops, multiple nice loops and almost pattern nice loops?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby vidarino » Tue Mar 07, 2006 5:49 pm

One question.

[r4c8]-3-[r1c8]-7-[r3c7]-8-[r3c6]=8=[r4c6]=6=[r4c8] => [r4c8]<>3


Is that really a Nice Loop? The deduction is fine, but isn't it really a Single Implication Chain that ends up in a conflict (no 6 in R4)?

A "pure" Nice Loop, as far as I have gathered, either;
- starts and ends in the same digit with one strong link and one weak link (continuous; elim along weak edges)
- starts and ends on a bivalue cell with different candidate weak links (continuous; elim along weak edges)
- starts and ends with weak links of same candidate (discontinuous; elim candidate from start/endpoint)
- starts and ends with strong links of same candidate (discontinous; fix candidate at start/endpoint)

The above chain doesn't fit any of these, though.

Also, it's a bit funny that this was posted now, by the way, because I just added support for (what I ended up calling) Simple Implication Chains, precisely like the quoted one above, to my solver just two days ago.:)

Note again that I'm not questioning the deduction, just the name. (And I might very well be wrong.):)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby Jeff » Tue Mar 07, 2006 6:17 pm

vidarino wrote:[r4c8]-3-[r1c8]-7-[r3c7]-8-[r3c6]=8=[r4c6]=6=[r4c8] => [r4c8]<>3
Is that really a Nice Loop? The deduction is fine, but isn't it really a Single Implication Chain that ends up in a conflict (no 6 in R4)?

Hi Vidar, This is a type of simple nice loops alright. It appears that you have missed out theorem 2 and theorem 5 in the nice loop description here.
vidarino wrote:- starts and ends in the same digit with one strong link and one weak link (continuous; elim along weak edges)
- starts and ends on a bivalue cell with different candidate weak links (continuous; elim along weak edges)

This is theorem 1, but I think you have missed out something here. This is not how a continuous loop is defined. In fact, a continuous loop should not have a start nor an end. The term "continuous" implies that the nice loop propagation rules are observed continuously in a cyclic manner. The deduction modes are fine though.

vidarino wrote:- starts and ends with weak links of same candidate (discontinuous; elim candidate from start/endpoint)

This is Theorem 4.

vidarino wrote:- starts and ends with strong links of same candidate (discontinuous; fix candidate at start/endpoint)

This is Theorem 3.

BTW, these deductions are equally valid for other more advanced loops.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ravel » Tue Mar 07, 2006 6:44 pm

Great, flip, and thanks for the fine ALS excercises (i am really not good in spotting them).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby vidarino » Tue Mar 07, 2006 6:47 pm

Jeff wrote:Hi Vidar, This is a type of simple nice loops alright. It appears that you have missed out theorem 2 and theorem 5 in the nice loop description here.


Ah, indeed I have. Well, #2 I was aware of, but #5 seems to have evaded me completely. But I will allow myself to take a tiny sprinkle of pride in that I thought of #5 by myself. Yes, I said tiny. ;-)

In fact, a continuous loop should not have a start nor an end. The term "continuous" implies that the nice loop propagation rules are observed continuously in a cyclic manner. The deduction modes are fine though.


Very true, my bad. In my defense, though, I'm a computer guy, so I was thinking about it the way a computer solver would, namely "pick a node and try to construct a continuous loop that leads back here".

Anyway, thanks a lot for clearing things up.:)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby Carcul » Tue Mar 07, 2006 8:50 pm

Hi Flip.

Congratulations. Very elegant solution you got there. Good job.

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

Postby flip » Wed Mar 08, 2006 6:53 pm

Jeff wrote:Would you consider exploring further into grouped nice loops, multiple nice loops and almost pattern nice loops?

I am definitely going to explore the extensions to simple nice loops. I have experimented to a limited extent with grouped x-cycles.

Jeff, thanks for checking the nice loops (Carcul and others too). Also thanks to you and Carcul for elevating the nice loop technique to its current level. Your posts are required reading. Please keep up the good work.

Following the discussion above on nice loop theorems, here is a very interesting position where nice loops can be found as examples for all five theorems. The puzzle is from your post on multiple nice loops here, so you may have noticed this before.

This position is really amazing because several nice loops can be found for each of the theorems. In fact, I suspect that the total number of simple nice loops possible at this position is quite large. I know of at least 20, but it may be double this. This makes a very good exercise, there are so many that they should be easy to find:) .
The theorem 1 and 2 examples are 2 different loops, but they eliminate the same candidate.
The theorem 1 & 2 example is a pretty little loop requiring both of these theorems.
Code: Select all
 
  Theorem 1
    =[r3c3]=1=[r3c5]=8=[r9c5]=6=[r9c3]=4=[r3c3]=   => [r9c3]<>9
  Theorem 2
    -[r1c1]=4=[r1c6]-4-[r3c6]-7-[r9c6]-9-[r9c1]-4-[r1c1]=   => [r9c3]<>9
  Theorem 1 & 2
    =[r1c4]=7=[r1c7]=9=[r5c7]-9-[r5c3]-1-[r3c3]=1=[r3c5]=8=[r1c4]=
      => [r1c7]<>8,[r5c9]<>9
  Theorem 3
    [r6c9]=1=[r5c9]=3=[r5c5]=5=[r1c5]=1=[r1c1]-1-[r6c1]=1=[r6c9] => [r6c9]<>9
  Theorem 4
    [r5c9]-9-[r5c3]-1-[r3c3]=1=[r3c5]=8=[r3c7]-8-[r5c7]-9-[r5c9] => [r5c9]<>9
  Theorem 5
    [r9c3]=4=[r3c3]-4-[r3c6]-7-[r9c6]-9-[r9c3] => [r9c3]<>9
    14  3*  2*     78  15   45    789  68  69
    5*  7*  8*     2*  9*   6*    3*   1*  4*
    6*  9*  14     3*  18   47    78   5*  2*
    28  5*  7*     9*  23   1*    4*   68  36
    28  6*  19     4*  235  25    89   7*  139
    19  4*  3*     6*  7*   8*    5*   2*  19
    3*  8*  69     5*  26   29    1*   4*  7*
    7*  2*  5*     1*  4*   3*    6*   9*  8*
    49  1*  469    78  68   79    2*   3*  5*

Please feel free to correct any nice loop errors.
Regards, flip
flip
 
Posts: 17
Joined: 08 January 2006

Postby Jeff » Wed Mar 08, 2006 7:38 pm

flip wrote:Following the discussion above on nice loop theorems, here is a very interesting position where nice loops can be found as examples for all five theorems. The puzzle is from your post on multiple nice loops here, so you may have noticed this before.

This position is really amazing because several nice loops can be found for each of the theorems. In fact, I suspect that the total number of simple nice loops possible at this position is quite large. I know of at least 20, but it may be double this. This makes a very good exercise, there are so many that they should be easy to find:) .

Hi Flip, You are right; this puzzle has quite a lot of nice loops to be identified that I had made it an exercise here.:D

Under the same thread, Carcul had provided 2 solutions for this puzzle. I think this one is the most elegant.

My solution is posted here.
Jeff
 
Posts: 708
Joined: 01 August 2005


Return to Advanced solving techniques