Nice Loop Question (again)

Advanced methods and approaches for solving Sudoku puzzles

Nice Loop Question (again)

Postby hobiwan » Sat Dec 13, 2008 3:13 am

While playing around with tareks ER=8.8 puzzle from the "Maximum number of clues..." thread I stumbled over the following nice Nice Loops:

Code: Select all
Original Puzzle
..9.52..3.2.93..5.5.367.9.2..52.9.3493..45.2.1427.359..5...72.9.9..2..652..5963..


After some steps:
.---------------------.--------------.----------------------.
| 4678  *1678    9    | 18  5    2   |  4678   *1478   3    |
| 4678   2     *-1678 | 9   3    148 | *14678   5     *1678 |
| 5     *18      3    | 6   7    148 |  9      *148    2    |
:---------------------+--------------+----------------------:
| 678    678     5    | 2   168  9   |  167     3      4    |
| 9      3       678  | 18  4    5   |  1678    2      1678 |
| 1      4       2    | 7   68   3   |  5       9      68   |
:---------------------+--------------+----------------------:
| 368    5       1468 | 34  18   7   |  2      *148    9    |
| 378    9       1478 | 34  2    18  |  478     6      5    |
| 2     *-178    1478 | 5   9    6   |  3      *1478  *178  |
'---------------------'--------------'----------------------'

Grouped Discontinuous Nice Loop
r9c2 -1- r9c9 =1= r79c8 -1- r13c8 =1= r2c79 -1- r2c3 =1= r13c2 -1- r9c2 => r9c2<>1

Grouped Discontinuous Nice Loop
r2c3 -1- r13c2 =1= r9c2 -1- r9c9 =1= r79c8 -1- r13c8 =1= r2c79 -1- r2c3 => r2c3<>1



Both Nice Loops use exactly the same cells but lead to two different discontinuities, allowing two different eliminations.

The only other way I could find to do both eliminations in one step was:
Finned Mutant Whale: 1 r1378c79 r29c8b268 fr1c2 fr3c2 fr7c3 fr8c3 => r2c3,r9c2<>1
(of course some people here wouldnt allow that because each elimination can be done by a Finned Franken Swordfish, eg:
Finned Franken Swordfish: 1 r78b3 c38b8 fr2c7 fr2c9 => r2c3<>1 and
Finned Franken Swordfish: 1 r38b9 c68b7 fr3c2 fr9c9 => r9c2<>1)

Is there a way to combine the two Nice Loops into one to do both eliminations in one step?
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Re: Nice Loop Question (again)

Postby aran » Sat Dec 13, 2008 3:50 am

hobiwan wrote:While playing around with tareks ER=8.8 puzzle from the "Maximum number of clues..." thread I stumbled over the following nice Nice Loops:
Code: Select all
Original Puzzle
..9.52..3.2.93..5.5.367.9.2..52.9.3493..45.2.1427.359..5...72.9.9..2..652..5963..

After some steps:
.---------------------.--------------.----------------------.
| 4678  *1678    9    | 18  5    2   |  4678   *1478   3    |
| 4678   2     *-1678 | 9   3    148 | *14678   5     *1678 |
| 5     *18      3    | 6   7    148 |  9      *148    2    |
:---------------------+--------------+----------------------:
| 678    678     5    | 2   168  9   |  167     3      4    |
| 9      3       678  | 18  4    5   |  1678    2      1678 |
| 1      4       2    | 7   68   3   |  5       9      68   |
:---------------------+--------------+----------------------:
| 368    5       1468 | 34  18   7   |  2      *148    9    |
| 378    9       1478 | 34  2    18  |  478     6      5    |
| 2     *-178    1478 | 5   9    6   |  3      *1478  *178  |
'---------------------'--------------'----------------------'

Grouped Discontinuous Nice Loop r9c2 -1- r9c9 =1= r79c8 -1- r13c8 =1= r2c79 -1- r2c3 =1= r13c2 -1- r9c2 => r9c2<>1
Grouped Discontinuous Nice Loop r2c3 -1- r13c2 =1= r9c2 -1- r9c9 =1= r79c8 -1- r13c8 =1= r2c79 -1- r2c3 => r2c3<>1

Both Nice Loops use exactly the same cells but lead to two different discontinuities, allowing two different eliminations.

The only other way I could find to do both eliminations in one step was:
Finned Mutant Whale: 1 r1378c79 r29c8b268 fr1c2 fr3c2 fr7c3 fr8c3 => r2c3,r9c2<>1
(of course some people here wouldnt allow that because each elimination can be done by a Finned Franken Swordfish, eg:
Finned Franken Swordfish: 1 r78b3 c38b8 fr2c7 fr2c9 => r2c3<>1 and
Finned Franken Swordfish: 1 r38b9 c68b7 fr3c2 fr9c9 => r9c2<>1)

Is there a way to combine the two Nice Loops into one to do both eliminations in one step?


nice continuous loop : (1): r13c2=r9c2-r9c89=r7c8-r13c8=r2c79-r2c3=r13c2 =><1> r2c3, r9c2
aran
 
Posts: 334
Joined: 02 March 2007

Re: Nice Loop Question (again)

Postby hobiwan » Sat Dec 13, 2008 9:08 am

aran wrote:nice continuous loop : (1): r13c2=r9c2-r9c89=r7c8-r13c8=r2c79-r2c3=r13c2 =><1> r2c3, r9c2

You start with r13c2<>1 and end with r13c2=1. Thats a discontinuity in my book (although I am not exactly sure about the consequences: one of r13c2 has to be 1? - that would make your eliminations correct, only as Discontinous Nice Loop).
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Re: Nice Loop Question (again)

Postby aran » Sat Dec 13, 2008 9:22 am

hobiwan wrote:
aran wrote:nice continuous loop : (1): r13c2=r9c2-r9c89=r7c8-r13c8=r2c79-r2c3=r13c2 =><1> r2c3, r9c2

You start with r13c2<>1 and end with r13c2=1. Thats a discontinuity in my book (although I am not exactly sure about the consequences: one of r13c2 has to be 1? - that would make your eliminations correct, only as Discontinous Nice Loop).

You're right. "Dis" was missing !
The loop shows that 1 is true over the group r13c2 and hence the eliminations follow
aran
 
Posts: 334
Joined: 02 March 2007

Re: Nice Loop Question (again)

Postby hobiwan » Sun Dec 14, 2008 3:02 am

Tanks for your answer. I didnt realize that a Discontinuous Nice Loop starting with a group node can eliminate candidates in more than one cell.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby Pat » Sun Dec 14, 2008 3:49 am

hobiwan,

i understand your concern about the 2-step solution
    ( your 2nd NL ==> r2c3 not 1,
    which in turn gives r9c2 not 1
    )
however, in my view aran's NL is also a 2-step solution
    (1): r13c2=r9c2-r9c89=r7c8-r13c8=r2c79-r2c3=r13c2
    ==> 1 is in r13c2,

    which in turn gives (2nd step)
    the exclusions in the box (r2c3) and in the column (r9c2)
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Re: Nice Loop Question (again)

Postby ronk » Sun Dec 14, 2008 3:59 am

Pat wrote:in my view aran's NL is also a 2-step solution

[edit: Maybe], but it is only one nice loop.

hobiwan wrote:I didn't realize that a Discontinuous Nice Loop starting with a group node can eliminate candidates in more than one cell.

I'm curious, other than naked and hidden singles, does your solver currently make placements:?:

[edit: Not wishing to be party to a 1-step vs 2-step controversy, reply to Pat slightly rephrased.]
Last edited by ronk on Sun Dec 14, 2008 8:05 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Sun Dec 14, 2008 6:42 am

This is a poor example to split hairs over because either chain elimination leads to a Locked Candidate 1 that performs the second elimination. That said ...

Pat and ronk agree that aran's discontinuous loop is really two steps because it forces an assignment ... and the eliminations must be viewed as a second step. To me, it's a sorry Sudoku day when an assignment can't claim its eliminations.:(
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby aran » Sun Dec 14, 2008 7:44 am

daj95376 wrote:This is a poor example to split hairs over because either chain elimination leads to a Locked Candidate 1 that performs the second elimination. That said ...

Pat and ronk agree that aran's discontinuous loop is really two steps because it forces an assignment ... and the eliminations must be viewed as a second step. To me, it's a sorry Sudoku day when an assignment can't claim its eliminations.:(


Could we agree that it is a two part process : a step and a consequence.
The consequence (the eliminations resulting from the NL step) not really meriting the more noble title of step:)
aran
 
Posts: 334
Joined: 02 March 2007

Re: Nice Loop Question (again)

Postby hobiwan » Sun Dec 14, 2008 7:54 pm

ronk wrote:I'm curious, other than naked and hidden singles, does your solver currently make placements:?:

Only in Forcing Chains/Nets when the original assumption <>x is proven to be false. The analogous case with Nice Loops eliminates all other candidates in the target cell, leaving a Naked Single (code was written much earlier than Forcing Chains and it seemed to be more clear when displayed in my GUI).

My interest in this was not a one step/two step discussion but to learn whether I should change my chaining code to allow group nodes as starting points (in the above example not really necessary).
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Re: Nice Loop Question (again)

Postby Draco » Tue Dec 16, 2008 10:57 am

hobiwan wrote:
ronk wrote:I'm curious, other than naked and hidden singles, does your solver currently make placements:?:

Only in Forcing Chains/Nets when the original assumption <>x is proven to be false. The analogous case with Nice Loops eliminates all other candidates in the target cell, leaving a Naked Single (code was written much earlier than Forcing Chains and it seemed to be more clear when displayed in my GUI).

My interest in this was not a one step/two step discussion but to learn whether I should change my chaining code to allow group nodes as starting points (in the above example not really necessary).

To split another hair: is your original assumption case for forcing chains/nets really a placement? It seems to me that it is another elimination (eliminate the starting value). Now anytime you eliminate one member of a b/b pair then you create a single; it is unclear to me how that differs from placing singles.

It is certainly less general than a case where, say, some other technique just happens to eliminate one of a b/b pair, creating a single (since forcing chains/nets -- at least as I think you practice them -- always start with a b/b pair). But to me it is still just an elimination... that happens to result in a single popping up (either open or hidden).

Or perhaps I misunderstand what is meant by placement:?:

Cheers...

- drac
[edit - fixed typos]
Draco
 
Posts: 143
Joined: 14 March 2008

Re: Nice Loop Question (again)

Postby ronk » Tue Dec 16, 2008 11:37 am

Draco wrote:To split another hair: is your original assumption case for forcing chains/nets really a placement?
[...]
Or perhaps I misunderstand what is meant by placement:?:

An assumption may be either a trial assertion of a candidate, or a trial negation. If trial assertion leads to a contradiction, then that trial candidate may be eliminated. If negation leads to a contradiction, that candidate becomes a "placement."

A placement may also result from logical deduction, rather than an assumption.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

retraction

Postby Pat » Thu Dec 18, 2008 2:03 am


        apologies to all
        for my foolish comment
hobiwan presented a solution using 2 NLs
and asked for a solution using just 1 NL;
which aran did provide (as ronk immediately told me).


the number of "steps" was never an issue.
however, since i did raise the question of the number of "steps",
i must also retract that part of my comment.

for anyone who might care for the details --

  1. hobiwan's solution is just 1 step (not 2) --
    he uses 2 NLs,
    both available at the same time.
  2. the only 2-step solution
    is my version
    (which uses only 1 of his NLs,
    postponing the 2nd exclusion to the next step).
  3. and my serious mistake
    was the claim that aran's NL is a 2-step solution.
    in fact his NL proves that r13c2 (a cluster of 2 cells) does contain 1;
    the relevant exclusions (certainly part of this "step") are --
      exclude 1 in any cell which "sees" all cells of the cluster
      (i.e. exclude both in the box and in the column).
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Postby daj95376 » Thu Dec 18, 2008 3:26 am

Pat: Thanks for the clarification!

ronk: I'm sorry that I misunderstood your initial reply. I should have known better!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Nice Loop Question (again)

Postby hobiwan » Sat Dec 20, 2008 3:21 am

Draco wrote:It is certainly less general than a case where, say, some other technique just happens to eliminate one of a b/b pair, creating a single (since forcing chains/nets -- at least as I think you practice them -- always start with a b/b pair). But to me it is still just an elimination... that happens to result in a single popping up (either open or hidden).

Or perhaps I misunderstand what is meant by placement:?:

I've been away for a few days...

I start with everything that can produce eliminations/placements. An example from a different state of the puzzle I posted above:
Code: Select all
.-------------------.---------------.--------------------.
| *4678   167  9    | *18  5     2  |  467    47    3    |
| *4-6-7  2    67   |  9   3    *18 | *14678  5     167  |
|  5      18   3    |  6   7     4  |  9      18    2    |
:-------------------+---------------+--------------------:
|  678    678  5    |  2   168   9  |  167    3     4    |
|  9      3    678  |  18  4     5  |  167    2     1678 |
|  1      4    2    |  7   68    3  |  5      9     68   |
:-------------------+---------------+--------------------:
|  368    5    1468 |  34  18    7  |  2      148   9    |
|  37     9    147  |  34  2     18 |  478    6     5    |
|  2      78   1478 |  5   9     6  |  3      1478  17   |
'-------------------'---------------'--------------------'

Discontinuous Nice Loop r2c1 =4= r2c7 =8= r2c6 -8- r1c4 =8= r1c1 =4= r2c1 => r2c1<>6, r2c1<>7

The chain says "if r2c1<>4 then r2c1=4", which means that 4 can be placed immediatly in r2c1 (without the detour my solver makes).

Due to the inconsistency in my solver code I mentioned above I get the placement directly (using exactly the same cells) if I search for Forcing Chains instead of Nice Loops:
Code: Select all
Forcing Chain Contradiction in r2c1 => r2c1=4
  r2c1<>4 r2c7=4 r2c6=8 r1c1=8 r2c1=4
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Next

Return to Advanced solving techniques