FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Building inference chains/nice loops Goto page Previous  1, 2, 3          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message leeo Joined: 24 Jun 2009 Posts: 6 : Location: USA NW Items Posted: Fri Aug 21, 2009 12:59 pm    Post subject: Re: Documenting Nice Loops and Chains daj95376 wrote: I'm accustomed to working with chains and rarely rely on loops -- They are, of course, the exact same concept, and yes, from the persepective of chains, the "loop" notation is extraneous. I started with the following very lucid artice [look up "nice loops in sudoku", this board does not permit me to post the link], which did give me a "loopy" perspective. This does suggest one idea for improvement: search through the building chain for all "cross innersection" moves. These can be expressed as loops, but it then does make it easier to find elimination moves. Back to top nukefusion Joined: 27 Jun 2009 Posts: 22 : Items Posted: Wed Sep 09, 2009 12:05 pm    Post subject: Ok, I wonder if anyone can help here. If I'm understanding everything correctly, any nice loop can be represented by an equivalent AIC. Take this nice loop example below. Can anyone please tell me what the equivalent AIC is? I've got stuck trying to figure it out. Last edited by nukefusion on Wed Sep 09, 2009 6:25 pm; edited 1 time in total Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Wed Sep 09, 2009 4:50 pm    Post subject: Your puzzle can be solved with singles, but you stopped halfway through to ask about a chain that doesn't make any sense to me. Would you please list and explain the individual connections! Back to top nukefusion Joined: 27 Jun 2009 Posts: 22 : Items Posted: Wed Sep 09, 2009 5:14 pm    Post subject: daj95376 wrote: Your puzzle can be solved with singles, but you stopped halfway through to ask about a chain that doesn't make any sense to me. Would you please list and explain the individual connections! I'm kind of glad it doesn't make any sense to you, because it doesn't make sense to me either. This example of a nice loop is generated by a piece of software you can download from the internet. Using it you can view all of the available steps, at any given time. I realize the puzzle itself can be solved using just singles, but nevertheless this nice loop, according to the software, is valid and available immediately after you open the puzzle (regardless of whether it would ever be useful in real life). So I guess that's my question, is it valid? And if so, how does it translate into an AIC, because I couldn't work it out (which kind of puts a damper on the understanding I thought I had about AIC's) Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Wed Sep 09, 2009 9:14 pm    Post subject: I think that I've manged to understand what it's doing. I hope you understand Eureka notation because I don't use NL notation anymore. Code:  *--------------------------------------------------------------------*  | 1468   3      7      | 2      58     9      | 68     1456   146    |  | 1468   9      145    | 158    578    1378   | 368    2      13467  |  | 18     158    2      | 4      6      1378   | 389    13579  1379   |  |----------------------+----------------------+----------------------|  | 2      8      9      | 5689   1      4      | 7      369    369    |  | 3      7      149    | 69     29     2      | 5      8      2469   |  | 5      6      49     | 3      2789   278    | 1      49     249    |  |----------------------+----------------------+----------------------|  | 7      1245   8      | 19     249    6      | 239    139    1239   |  | 19     12     6      | 19     3      5      | 4      179    8      |  | 149    124    3      | 7      2489   128    | 269    169    5      |  *--------------------------------------------------------------------* Here's the chain as a discontinuous nice loop in WI-based AIC. It makes all of the arrows point at each other. Code: (2)r7c2 - (2=1)r8c2 - (1=9)r8c1 - (9=1)r8c4 - (1=2)r8c2 - (2)r7c2; => r7c2 <> 2 _______________________________________________________________________________ I prefer to use the SI-based AIC. It translates into the <19> Naked Pair elimination. Code:                       (1=9)r8c1 - (9=1)r8c4                      ; => r8c2 <> 1 _______________________________________________________________________________ Bottom Line: Always perform basic techniques before searching for a chain! Back to top nukefusion Joined: 27 Jun 2009 Posts: 22 : Items Posted: Thu Sep 10, 2009 6:05 am    Post subject: Thanks for your reply daj95376. I don't know what WI/SI is but I understand the notation. Is it valid to reuse the candidates 1/2 in R8C2 at another point in the loop? I think that's what has caused my confusion here. Back to top PIsaacson Joined: 17 Jan 2006 Posts: 47 : Location: Campbell, CA Items Posted: Thu Sep 10, 2009 6:34 am    Post subject: nukefusion wrote: Is it valid to reuse the candidates 1/2 in R8C2 at another point in the loop? Not with nrc chains. The prior conjugate pair strong link (2=1)r8c2 prohibits the later conjugate pair strong link (1=2)r8c2. This produces an nrc whip which basically states that any prior "truth" (right hand side of the conjugate pairs) cannot be contradicted by some later discovered truth. I've never seen nice-loops implementations that take advantage of this, mainly because of the reversibility problem. If you consider prior "truths" during chain generation, then you obviously get into conditions where the chain quickly becomes non-reversible. That's why nrc chains don't have anything equivalent to continuous loops. Cheers, Paul Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Thu Sep 10, 2009 4:14 pm    Post subject: PIsaacson wrote: nukefusion wrote: Is it valid to reuse the candidates 1/2 in R8C2 at another point in the loop? Not with nrc chains. The prior conjugate pair strong link (2=1)r8c2 prohibits the later conjugate pair strong link (1=2)r8c2. This produces an nrc whip which basically states that any prior "truth" (right hand side of the conjugate pairs) cannot be contradicted by some later discovered truth. I've never seen nice-loops implementations that take advantage of this, mainly because of the reversibility problem. If you consider prior "truths" during chain generation, then you obviously get into conditions where the chain quickly becomes non-reversible. That's why nrc chains don't have anything equivalent to continuous loops. My answer is in addition to what Paul wrote. The biggest problem I had/have with chains is that they are not suppose to have a "memory" of previous eliminations in the chain. Otherwise, they're a network. However, this lack of "memory" doesn't apply to cells being visited. Otherwise, infinite loops would exist. (Does this qualify as an oxymoron?) Being a WI-based AIC and a discontinuous nice loop, is what makes this chain appear to be unorthodox, IMO. Some definitions and history. Code: SI: Strong Inference WI: Weak   Inference When Myth Jellies introduced the AIC, it was based of an SI being first: Code: ( SI WI ) ... SI If you use his definition and elimination logic, then all you need is ... Code:           (2=1)r8c2 - (1=9)r8c1 - (9=1)r8c4 - (1=2)r8c2;          => r79c2 <> 2 _______________________________________________________________________________ ... and the loop stops when it returns to the same cell. At this point, eliminations can be derived. (Note: there are two eliminations!) Now, many people like to make the elimination(s) an obvious part of the chain. So, they turn the chain into a WI-based AIC by assuming that the eliminations are true at the front and concluding that they aren't at the end. (I call this a contradiction chain -- a very old name that's no longer used by others.) Code: ( WI SI ) ... WI Code: (2)r7c2 - (2=1)r8c2 - (1=9)r8c1 - (9=1)r8c4 - (1=2)r8c2 - (2)r7c2; => r7c2 <> 2 _______________________________________________________________________________ This lets a chain enter and leave a cell ... and to (sometimes) return later to enter and leave the same cell. This gives it the appearance of a whip, but I only use the term whip to imply a more complicated scenario. In the case of this chain, only one SI-based AIC elimination is initially assumed true ... and so only one elimination is derived as false. I haven't used WI-based AICs in a long time, but I have recently been known to list them as an alternative view of my SI-based AICs. Note: Since a WI-based AIC already starts and ends with the elimination cell(s), I consider the conclusion to be self-evident and often drop the (redundant) specific declaration of elimination(s). Code: (2)r7c2 - (2=1)r8c2 - (1=9)r8c1 - (9=1)r8c4 - (1=2)r8c2 - (2)r7c2 _______________________________________________________________________________ Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Programming sudoku All times are GMT Goto page Previous  1, 2, 3 Page 3 of 3   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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   Powered by phpBB © 2001, 2005 phpBB Group Igloo Theme Version 1.0 :: Created By: Andrew Charron