Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Nice Loop: use cell twice?
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
kyriako

Joined: 12 Jun 2008
Posts: 16
:
Location: Germany

Items
PostPosted: Sat Jun 14, 2008 6:41 pm    Post subject: Nice Loop: use cell twice? Reply with quote

Hello Sudoku Friends,

when snaking around a Sudoku, it may happen that you hit a cell which is already being used by the loop. Is it allowed to use it a second time and continue?
Does it make sense at all?

Guenter(Kyriakos).
Back to top
View user's profile Send private message
Steve

Joined: 12 Apr 2006
Posts: 12
:

Items
PostPosted: Sat Jun 14, 2008 7:28 pm    Post subject: Reply with quote

Yiasou!

As far as the logic is concerned, no difficulty arises if a nice chain crosses itself, using a node (or nodes) several times. If you think about it, you can go round a continuous nice loop as often as you like without disturbing its meaning.

Whether it is helpful is another matter: I do not think any fresh elimination will arise as opposed to dealing with each sub-loop separately.

Steve
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Sun Jun 15, 2008 1:22 pm    Post subject: Reply with quote

I just posted possible examples here. They provide additional eliminations and seem to be valid (to me at least). Whether they are sensible (or useful) is another question.
Back to top
View user's profile Send private message
kyriako

Joined: 12 Jun 2008
Posts: 16
:
Location: Germany

Items
PostPosted: Sun Jun 15, 2008 6:31 pm    Post subject: one more question Reply with quote

Yassu and thank you Steve for the explanation.

Would you suggest to examine the continuous sub-loop first before going ahead?

I have still another question, which you have probably already answered with your comment:
in the samples that I have seen so far, the traces form either kind of a "loop" or they
cross each other. Is it allowed to use a unit(like a row) several times?

Hello hobiwan and thank you for the samples.

I'm not familiar with this kind of code: what is the meaning of a character
in a cell, e.g. "b34" ?

Guenter(Kyriakos).
Back to top
View user's profile Send private message
Steve

Joined: 12 Apr 2006
Posts: 12
:

Items
PostPosted: Sun Jun 15, 2008 6:53 pm    Post subject: Reply with quote

The three I checked are valid right enough. However, I doubt if, properly speaking, they made any additional elimination.

Take the second loop marked with two asterisks for the third grid. It runs:

r3c9 =4= r3c5 -4- r6c5 =4= r5c6 =6= r5c7 -6- r1c7 =6= r1c2 =7= r7c2 =8= r7c1 =6= r7c5 -6- r4c5 =6= r5c6 =4= r1c6 -4- r1c8 =4= r3c9

You rightly conclude that r3c9 contains 4.

Now extract its middle loop

r5c6 =6= r5c7 -6- r1c7 =6= r1c2 =7= r7c2 =8= r7c1 =6= r7c5 -6- r4c5 =6= r5c6

This places 6 in r5c6. As for the rest of the loop, whether you use the head

r3c9 =4= r3c5 -4- r6c5 =4= r5c6

or the tail

r5c6 =4= r1c6 -4- r1c8 =4= r3c9

6 in r5c6 places 4 in r3c9.

There is a sort of equation, I suppose: long loop + singles = short loop + singles.

Steve
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Sun Jun 15, 2008 8:30 pm    Post subject: Re: one more question Reply with quote

kyriako wrote:
I'm not familiar with this kind of code: what is the meaning of a character
in a cell, e.g. "b34" ?

I think you refer to the original post by daj95376. The letters only mark the cells affected by the chain writen underneath so you can follow it more easily.

Steve wrote:
There is a sort of equation, I suppose: long loop + singles = short loop + singles.

You have a point there Very Happy
Back to top
View user's profile Send private message
Steve

Joined: 12 Apr 2006
Posts: 12
:

Items
PostPosted: Sun Jun 15, 2008 10:07 pm    Post subject: Reply with quote

Günter

I spent so long transferring my previous note from the word processing program to the text box that your last post beat me to it and I have only just noticed it.

I am not certain I understand your fears but I’m pretty sure they’re groundless. Perhaps it will help to go back to basics. Take a small part of a chain, say

-1- r1c1 -2- r1c9 when written in nice loop notation.

This is just shorthand for two statements:
(1) If r1c1 does not contain 1, r1c9 does not contain 2:
(2) If r1c9 contains 2, r1c1 does not.
The fact that these statements can be made depends entirely on the grid. They are not affected by anything else. In particular, they are unaltered whether or not r1c1 appears elsewhere in the chain you build up around it. As far as I am concerned there is only one rule for chains: join the links logically and nothing else matters.

If this doesn’t set your mind at ease, perhaps you could provide an example of a chain with which you feel uncomfortable and I shall try to do better.

Steve
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sun Jun 15, 2008 10:58 pm    Post subject: Re: one more question Reply with quote

kyriako wrote:
I'm not familiar with this kind of code: what is the meaning of a character
in a cell, e.g. "b34" ?

It's not uncommon for someone to post a pencil mark (PM) grid and then mark the cells used. Sometimes the cells are marked with asterisks (*), and sometimes the cells are marked as groups (no example), and sometimes the cells are marked in the order they are processed (abcd) -- as in my grid.
Back to top
View user's profile Send private message
kyriako

Joined: 12 Jun 2008
Posts: 16
:
Location: Germany

Items
PostPosted: Mon Jun 16, 2008 6:34 pm    Post subject: Thank you Reply with quote

Hello Steve and hobiwan,

Thank you for your hints. I will study the samples thoroughly. This will sure give me more certainty on the subject. In any case, I find the nice loop strategy fascinating.

Regards,
Guenter(Kyriakos)
Back to top
View user's profile Send private message
Henk

Joined: 13 Nov 2005
Posts: 105
:

Items
PostPosted: Fri Jun 20, 2008 9:23 pm    Post subject: Reply with quote

Hi,

If you are really interrested in nice loops (and other forcing chains) you should try this puzzle. Just try to find as many as you can, its has lots of them.
..1...5..8..4.5..32.......6..6.9.4..4..231..8..8.4.3..6.......99..1.3..4..2...1..

Code:

 . . 1 | . . . | 5 . .
 8 . . | 4 . 5 | . . 3
 2 . . | . . . | . . 6
-------+-------+------
 . . 6 | . 9 . | 4 . .
 4 . . | 2 3 1 | . . 8
 . . 8 | . 4 . | 3 . .
-------+-------+------
 6 . . | . . . | . . 9
 9 . . | 1 . 3 | . . 4
 . . 2 | . . . | 1 . .


 37     34679  1      | 36789  2678   26789  | 5      24789  27   
 8      679    79     | 4      1267   5      | 279    1279   3     
 2      34579  34579  | 3789   178    789    | 789    14789  6     
----------------------+----------------------+----------------------
 1357   12357  6      | 578    9      78     | 4      1257   1257 
 4      579    579    | 2      3      1      | 679    5679   8     
 157    12579  8      | 567    4      67     | 3      125679 1257 
----------------------+----------------------+----------------------
 6      134578 3457   | 578    2578   2478   | 278    23578  9     
 9      578    57     | 1      25678  3      | 2678   25678  4     
 357    34578  2      | 56789  5678   46789  | 1      35678  57   


To be more specific; there is a chain you need that runs through 1 cell three times at this point!

Code:

 . . 1 | . . . | 5 . .
 8 . . | 4 . 5 | . . 3
 2 5 . | . . . | . . 6
-------+-------+------
 . . 6 | . 9 . | 4 . .
 4 . . | 2 3 1 | . . 8
 . . 8 | . 4 . | 3 . .
-------+-------+------
 6 1 . | . 5 . | . . 9
 9 . . | 1 . 3 | . . 4
 . . 2 | . . . | 1 . .


 37    469   1     | 3689  68    2689  | 5     489   27   
 8     679   79    | 4     1267  5     | 279   12    3   
 2     5     34    | 3789  178   789   | 789   1478  6   
-------------------+-------------------+-------------------
 135   237   6     | 578   9     78    | 4     27    1257
 4     79    579   | 2     3     1     | 679   5679  8   
 157   29    8     | 567   4     67    | 3     29    157 
-------------------+-------------------+-------------------
 6     1     34    | 78    5     24    | 278   238   9   
 9     78    57    | 1     267   3     | 2678  25678 4   
 357   3478  2     | 689   678   46789 | 1     3678  57   


Henk
_________________
Generate and solve Sudoku puzzles with Into Sudoku!
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Sat Jun 21, 2008 6:06 pm    Post subject: Reply with quote

Henk wrote:
To be more specific; there is a chain you need that runs through 1 cell three times at this point!

I can't check your triple crossing loop (I just changed my code to disable crossings Smile) but that grid solves nicely without:

My solver needs two finned fish, two nice loops, an UR1 and an xy-chain.
Back to top
View user's profile Send private message
kyriako

Joined: 12 Jun 2008
Posts: 16
:
Location: Germany

Items
PostPosted: Sat Jun 21, 2008 7:02 pm    Post subject: Nice Loop implementation Reply with quote

Thank you Friends,

Henk, I will have a look at your puzzle. Thank you.

hobiwan, what kind of solver do you use?

Meanwhile, I have included this strategy in my own solver.
Free download here:
http://homepages.compuserve.de/meinelg

Regards,
Kyriakos.
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Sun Jun 22, 2008 8:22 pm    Post subject: Re: Nice Loop implementation Reply with quote

kyriako wrote:
hobiwan, what kind of solver do you use?

My own (written in java, supports all the usual suspects except coloring, chains with grouped links or als and more sophisticated things like kraken).
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sat Jun 28, 2008 7:10 pm    Post subject: Reply with quote

Henk wrote:
To be more specific; there is a chain you need that runs through 1 cell three times at this point!

I must be missing your point about need. A combination of running my old/new solvers, and manually filtering the output in steps, produces this solution.

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

Code:
   c3    Naked  Triple                   <> 579  [r3c3],[r7c3]
   c8b3  Locked Candidate 1              <> 1    [r4c8],[r6c8]
 r6  b5  Locked Candidate 1              <> 6    [r6c8]
 r58     X-Wing                          <> 5    [r4c8],[r6c8],[r9c8]
         XYZ-Wing [r2c7]/[r1c9]+[r2c3]   <> 7    [r2c8]
   c37   X-Wing    finned                <> 9    [r2c8]   (optional)

Code:
 +-----------------------------------------------------------------------+
 |  37     34679  1      |  36789  2678   26789  |  5      24789  27     |
 |  8      679    79     |  4      1267   5      |  279    12     3      |
 |  2      5      34     |  3789   178    789    |  789    14789  6      |
 |-----------------------+-----------------------+-----------------------|
 |  1357   237    6      |  578    9      78     |  4      27     1257   |
 |  4      79     579    |  2      3      1      |  679    5679   8      |
 |  157    279    8      |  567    4      67     |  3      279    1257   |
 |-----------------------+-----------------------+-----------------------|
 |  6      1      34     |  78     5      2478   |  278    2378   9      |
 |  9      78     57     |  1      2678   3      |  2678   25678  4      |
 |  357    3478   2      |  6789   678    46789  |  1      3678   57     |
 +-----------------------------------------------------------------------+

Code:
  7r2c5  7r1c12 2r1c9  2r2c5                       <> 7  [r2c5]
  7r1c5  2r1c9  2r7c6  4r7c3  3r3c3  7r1c1 -7r1c5  <> 7  [r1c5]

 -7r7c7  7r7c4  7r3c5  1r2c5  2r1c56 7r1c9         <> 7  [r2c7],[r9c9]

 r2  b1  Locked Candidate 2                        <> 7  [r1c12]
         Singles


Last edited by daj95376 on Sun Jun 29, 2008 10:30 pm; edited 1 time in total
Back to top
View user's profile Send private message
kyriako

Joined: 12 Jun 2008
Posts: 16
:
Location: Germany

Items
PostPosted: Sun Jun 29, 2008 8:13 pm    Post subject: Nice Loop: use cell twice? Reply with quote

Hello daj95376,

meanwhile I handle the situation of hitting an occupied cell by stepping back and branching elsewhere. If this doesn't end up successfully, the program would step further back, finally landing at the cell in question, from where it proceeds in a different direction.
This way, I believe, I cover all possibilities without too many unnecessary links.

Perhaps a silly question:
the code that you present here, have you typed it manually or is there a program producing this kind of code?

Guenter(Kyriakos).
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron