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   

Building inference chains/nice loops
Goto page Previous  1, 2, 3  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
nukefusion

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Thu Jul 30, 2009 12:16 pm    Post subject: Reply with quote

Hmm, I'm having a bit of trouble here (again Embarassed) understanding how I'm going to construct a loop using BFS. I've constructed the graph, but due to the nature of BFS it seems like it becomes impossible to complete a loop back to the starting vertex as, if I'm using the colour technique, by the time I get a few levels into the search, all of the child vertices of level 1 have been coloured black.
Please excuse my dodgy sketch, scanned in from my notepad:



This is my example undirected graph. If I start at node 1 (on level 1), on the first level, nodes 2 and 3 are discovered. On the next level Node 4 is discovered, but because all child edges of 2 and 3 have already been found, there's no path back to the starting vertex because nodes 2 and 3 have now been coloured black.

I think there's a major flaw here in my understanding of how this is supposed to work!
Back to top
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Fri Jul 31, 2009 12:58 am    Post subject: Reply with quote

Matt,

The loop that you've sketched is a continuous loop that may or may not cause any direct elimination of the z-target. Instead, it may (or may not) allow eliminations along the two weak-linked legs: 1-2 and 4-3 provided it fits certain criteria. I use the following table from Myth Jellies for AIC loops:
Code:
// Strong Inference (SI):  ~A =>  B
// Weak   Inference (WI):   A => ~B

// Strong Link (SL):  e.g., ( bilocation  []=n=[] ) or ( bivalue cell  m-[]-n )
// Weak   Link (WL):  e.g., ( peers       []-n-[] ) or ( ?-value cell  m=[]=n )

// Sudopedia:  a SL can be used for SI or WI, but a WL can only be used for WI

// Myth Jellies' Alternating Inference Chain (AIC):  SI, WI, (alternating until) SI
//    -- bidirectional   (a chain consisting of an odd number of SL's is an AIC)


// Code:
// [cell]   =>   starting cell
// [peer]   =>   a peer cell of [cell]
// [!rcb]   =>   a cell that's not [cell], nor a peer of [cell]

// 1) [cell]=n= ... =n=[peer]-n-[cell] -- continuous loop w/side-effect eliminations

// 2) [cell]=n= ... =m=[peer]-m-[cell] -- [cell] <> m
//
// 3) [cell]=n= ...          =m=[cell] -- continuous loop w/side-effect eliminations
//                                        [cell] =  mn   is one side-effect

// 4) [cell]=n= ...          =n=[cell] -- [cell] =  n

// 5) [cell]=n= ...          =n=[!rcb] -- (peers_of_[cell] AND peers_of_[!rcb]) <> n

// 6) [cell]-n- ...          =n=[cell] -- continuous loop w/side-effect eliminations
//                                        ronk doesn't think it's viable

// 7) [cell]-n- ... =m=[peer]-m-[cell] -- continuous loop w/side-effect eliminations
//                                        [cell] must be bivalue {mn}

// 8) [cell]-n- ... =n=[peer]-n-[cell] -- [cell] <> n

// 9) [cell]-n- ...          =m=[cell] -- [cell] <> n

I'm pretty sure I copied this directly from some really early post, but I can't remember the exact location. What I do remember is that there are omissions and/or errors somewhere, but I can't remember exactly where. I'll have to carefully check my 9 tests and 9 NL elimination cases to see what's amiss. I think it's something to do with what constitutes a side-effect elimination, and the fact that tests 1-5 are conducted against the entries at level 1. But I need to confirm this.

So, back to your question:

The only way you can locate such loops is to use DFS instead of BFS. Then you would have discovered 4 before ever encountering 3, and the chain might be 1-2=4-3=1 provided the required strong links are true.

One of the major differences between nrczt chains and AIC/NL is that nrczt doesn't utilize loops. One of the most persuasive arguments against loops (other than the fact that they must be reversible and zt promotions excludes that as a possibility) is that since a circle has no end, you can effectively slice the loop at all the appropriate points and find equivalent eliminations using non-looping chains.

I've coded all three techniques and from numerous benchmarks against standard large or hard collections (royle17, top50000, top10000, gsf-puzzle30/33, tarek-pearly6000, top1465...), it has been repeatedly shown that nrczt is intrinsically more powerful than AIC/NL when you use the same group extensions for all three. The zt promotions apparently provide additional solution paths that the other techniques don't discover.

However, nrczt notation and chains are nowhere near as ubiquitous in use or practice on these various sudoku forums as AIC/NL, so you should decide which approach you want to commit to. Unless you want to code all three...

Cheers,
Paul
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Fri Jul 31, 2009 5:02 am    Post subject: Reply with quote

Paul: Your entry is from an old posting of mine. Here's my current notes file based on NL notation. The scenarios that start with an assignment are probably not necessary. I'm converting over to constructing chains from a strong links table because I can construct grouped entries (like ERI) easier.

Code:
===== ===== =====   Basic Chain Terminology and Notation   ===== ===== =====


Strong Link (SL):  e.g., ( bilocation   [a]=n=[b]  ) or ( bivalue cell  m-[c]-n )
Weak   Link (WL):  e.g., ( peers        [d]-n-[e]  ) or ( ?-value cell  m=[f]=n )


bilocation    [a]=n=[b] :  if [a] is not 'n', then [b] is     'n'
bivalue cell  m-[c]-n   :  if [c] is not 'm', then [c] is     'n'

peers         [d]-n-[e] :  if [d] is     'n', then [e] is not 'n'
?-value cell  m=[f]=n   :  if [f] is     'm', then [f] is not 'n'


Strong Inference (SI):  ~A =>  B
Weak   Inference (WI):   A => ~B


Sudopedia:  a SL can be used for SI or WI, but a WL can only be used for WI


Myth Jellies' Alternating Inference Chain (AIC):  SI, WI, (alternating until) SI
   -- bidirectional
   -- if the endpoints are the same cell & candidate,  a discontinuous AIC loop
   -- if a WI can connect  the same cell & candidate,  a    continuous AIC loop

Expanded      Alternating Inference Chain (AIC):  WI, SI, (alternating until) WI
   -- bidirectional


[cell]   =>   starting cell
[peer]   =>   a peer cell of [cell]
[othr]   =>   a cell that's not [cell]

A) [cell]=n= ... =n=[othr]          => ( peers([cell]) AND peers([othr]) ) <> n
B) [cell]=n= ... =n=[peer]-n-[cell]    continuous loop

C) [cell]=n= ... =m=[peer]          => [peer] <> n
D) [cell]=n= ... =m=[peer]-m-[cell] => [cell] <> m

E) [cell]=n= ...          =m=[cell] => [cell] =  mn
F) [cell]=n= ...          =n=[cell] => [cell] =   n

G) [cell]-n- ...          =n=[cell] => converse of (A) -- NOP

H) [cell]-n- ...          -m-[cell]    continuous loop if [cell] is bivalue {m,n}

I) [cell]-n- ... =n=[peer]-n-[cell] => [cell] <> n

J) [cell]-n- ...          =m=[cell] => [cell] <> n   reversed ...
   [cell]=n= ... =m=[peer]-m-[cell] => [cell] <> m   same as (D), but (J) catches
                                                     grouped missed by (D)
_________________________________________________________________________________

Matt: If I understand your diagram correctly, you are encountering a very common situation where there are multiple paths from a starting point to some later point. You'll need to keep track of the details in each node if you plan to handle continuous loops -- a mistake I made in my current implementation. For your example, here are the nodes/chains for your graph:

Code:
                 1
            12       13
      124                 134

This works (for me) using BFS.


Last edited by daj95376 on Fri Jul 31, 2009 6:29 am; edited 1 time in total
Back to top
View user's profile Send private message
nukefusion

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Fri Jul 31, 2009 6:22 am    Post subject: Reply with quote

Thanks for your invaluable input again people. I'd pretty much come to the same conclusion Paul; that DFS was the requirement for finding loops and I've just implemented that last night. For finding chains I think I'll stick with using my BFS routine on the same matrix.

It is my intention to eventually implement all flavours of loop/chain that I can. That's going to be a lot easier now I've got a common set of classes that I can build them all from. I'm only really concentrating on Nice Loops at the moment as they seem to be the most common. To be honest, I'll probably end up leaving nrczt until last, although they're the flavour I'm most looking forward to coding.

Im interested in what you said here daj95376:

Quote:

This works (for me) using BFS. A loop occurs when an existing entry is added to make a new node; e.g., 1245674 or 134891.


I tried to get it to work using BFS, but, if your using a colour flag for each visited vertex and a matrix as described in the previous posts all of the paths back have been visited by the time you got a few levels into the search. Taking your example above 134891, node 9 would have already been visited by the time you'd got to 8, so the path back is cut off. I'm curious as to how you've got this to work.
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Fri Jul 31, 2009 6:33 am    Post subject: Reply with quote

nukefusion wrote:
Im interested in what you said here daj95376:

Quote:

This works (for me) using BFS. A loop occurs when an existing entry is added to make a new node; e.g., 1245674 or 134891.


I tried to get it to work using BFS, but, if your using a colour flag for each visited vertex and a matrix as described in the previous posts all of the paths back have been visited by the time you got a few levels into the search. Taking your example above 134891, node 9 would have already been visited by the time you'd got to 8, so the path back is cut off. I'm curious as to how you've got this to work.

I deleted the "A loop occurs" part of my message because it didn't accurately describe what I was thinking. Ignore it!
Back to top
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Fri Jul 31, 2009 1:14 pm    Post subject: Reply with quote

daj95376 wrote:
Paul: Your entry is from an old posting of mine.

Daj95376,

My bad for not retaining the author and exact thread, and my congratulations on both the original content and your addendum. It has been my field-guide for AIC chain location and classification and I lucked out by stumbling across it while in the early process of writing chaining algorithms.

So, back to the question of whether or not you can detect loops while using a coloring table/list with BFS. The answer is (drum roll), "Yes you can by maintaining the child/parent tracking table!" In the Boost BFS documentation, it's the p[x] vector. I don't use the distance vector, d[x] since I maintain the complete path with each queue entry and the very first variable of the queue is the current height. I should have been clear in my prior post that BFS can be used, but it's definitely easier to do this in DFS since you have a decent chance of not needing to use the following algorithm for detecting loops with "in use" colored vertices.

So, if you correctly maintain the parent vector and you detect that a parent has already been used, then you know that you have a potential loop. The p[x] vector can track the already used parent back to the z-target with a small loop:
Code:

    pp := parent to backtrack
    while (pp != z_vertex)
      pp := p[pp];

If you store each pp vertex, you'll have the entire chain (backwards) leading to the z_vertex. It works because:
1) By using the coloring vector you guarantee that any given vertex has exact one path back.
2) By using the parent vector you guarantee that you can reconstruct all paths back to the z_vertex (z-target).

This works identically for both BFS and DFS for detecting loops back to the z-target. It should be obvious how to modify it to backtrack to any given level 1 candidate by storing the level in the parent vector. And don't forget that you still need to validate that the backwards path is reversible and can be "tagged" on as a valid extension to your current path to construct a loop. Also be aware that not all loops/chains are productive. If you terminate the BFS/DFS search because you found a potential loop, you may be exiting prematurely. DFS is pretty easy to re-enter, but BFS, less so and you'll need to have special re-entry logic wrapping the normal queue initialization.

I don't use this technique for nrczt (since we ignore loops), but Denis has defined something termed a lasso. Basically the lasso concept is that any chain which "looped" back to any prior candidate AND the usage was mismatched (ie. trying to use a parent at an even level when it had previously been found at an odd level - true vs false - or trying to use a parent at an odd level when it had previously been found at an even level - false vs true) was invalid and the z-target could be eliminated. Otherwise, it was just skipped since it was already "in use".

Even though lassos have been replaced with whips (a more advanced technique for detecting invalid chains), I have retained my lasso code because my implementation of whips is really slow compared to the lasso check. By using the two strong/weak parent bitmaps instead of the usual coloring table you can simply test the bit of the desired bitmap to see if it is set (grey/black - no difference for us) or not set (white - unused). These bitsets are used by braids as complete truth/false-hood tables at the end of the tree walk for determining certain types of network collisions, so they are a nice substitute for the coloring vector.

Hope this helps,
Paul
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Fri Jul 31, 2009 4:06 pm    Post subject: Reply with quote

Paul: I'm glad that my notes file on chains was of use to you. Until I managed to put together the strong/weak inference/links templates, NL chains weren't clear to me. Eureka notation with consistent use of "=" and "-" for strong and weak inference, respectively, really solidified chains.

===== ===== ===== ===== ===== Just rambling here.

If your nodes are "chains" as I indicated above, then you don't have to deal with backtracking because each node contains all of the information you need. In this case, your BFS "graph" is a circular linked-list where you remove the oldest chain/entry and add a new chain/entry for each new link that can be added to the chain/entry removed. Every time a chain/entry is removed, you check to see if it generates any eliminations.
Back to top
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Fri Jul 31, 2009 7:11 pm    Post subject: Reply with quote

daj95376 wrote:
... In this case, your BFS "graph" is a circular linked-list where you remove the oldest chain/entry and add a new chain/entry for each new link that can be added to the chain/entry removed. Every time a chain/entry is removed, you check to see if it generates any eliminations.

This doesn't sound like the standard BFS/DFS algorithms that I'm familiar with. Could you show in pseudo-code how this works? If you remove the oldest entries from a circular linked-list, wouldn't those be the lower levels? Or are you describing the standard BFS FIFO queue? I guess I'm confused by the usage of "node" to represent something other than a vertex, which is just one of the 729 possible candidates in a sudoku puzzle.

Cheers,
Paul
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Fri Jul 31, 2009 9:14 pm    Post subject: Reply with quote

PIsaacson wrote:
daj95376 wrote:
... In this case, your BFS "graph" is a circular linked-list where you remove the oldest chain/entry and add a new chain/entry for each new link that can be added to the chain/entry removed. Every time a chain/entry is removed, you check to see if it generates any eliminations.

This doesn't sound like the standard BFS/DFS algorithms that I'm familiar with. Could you show in pseudo-code how this works? If you remove the oldest entries from a circular linked-list, wouldn't those be the lower levels? Or are you describing the standard BFS FIFO queue? I guess I'm confused by the usage of "node" to represent something other than a vertex, which is just one of the 729 possible candidates in a sudoku puzzle.

I'm not fluent with all of the names associated with data structures. However, a BFS FIFO queue sounds like what I'm describing.

To me, a node is just a piece of information. The node can be stored in any number of data structures depending on the needs of the programmer. In my case, I'm storing chain information in each node.

Here's how Matt's graph would be handled in the BFS FIFO queue:

add "1"
remove "1" and add "12" and then add "13"
remove "12" and add "124"
remove "13" and add "134"
...

Here, "1" can represent a vertex as you've described, or it can represent an index into a strong links table. The interpretation of "12" would follow accordingly.

In the case of a strong links table, grouped and specialized strong links can easily be managed. In this case, "12" would represent two strong links joined by a weak link between the two table entries. Additional fields are present for bookeeping purposes, but I'm only giving an overview. Note: this approach trivially supports an AIC description of the final chain.

An example that Matt provided earlier.

[R1C2]=6=[R9C2]=8=[R9C5]

Strong link table entries:

Code:
1) [R1C2]=6=[R9C2]
2) [R9C2]=8=[R9C5]

Chain segment "12" would join the two strong link entries through the weak link:

Code:
6=[R9C2]=8

(As I described in an earlier breakdown of this chain segment.)
Back to top
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Sat Aug 01, 2009 4:39 am    Post subject: Reply with quote

Daj...,

Okay, I think we are on the same page but with different semantics. Your node sounds exactly like my queue entry which contains the current path under consideration. I use the term node to specifically refer to a single vertex in the adjacency matrix, but again that's just semantics. And I believe my adjacency matrix is equivalent to your strong links table plus a weak links table and group links table.

Thanks for the clarification.
Paul
Back to top
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Tue Aug 04, 2009 1:31 am    Post subject: Reply with quote

The sample BFS pascal code in an earlier post contains several references to the variable "sw_braids" which enables code that is used to perform network-like nrczt chains. The best way I can describe this is to have you imagine the entire tree stemming from some z-target candidate. Every even level contains all the various "truths" generated by the BFS tree walk. Every odd level contains all the various "false-hoods". In the code, if the sw_braids is non-zero, then all the "truths" are collected into the "vx_stack" array with "vx_count" tallying the number of entries.

Now for the network like part of this: Normally, the "any prior candidate" is defined by just those in the current path. But, in the case of braids, this can be any prior candidate in the entire tree. Since BFS is a level by level operation, this means that all level N candidates see all the true/false conditions from all the prior N-1 levels. If you have read any of Denis Berthier's explanations of zt promotions, you may begin to appreciate the fact the you can now consider ALL the prior truths in the tree for zt processing instead of just those even levels within the current path. As a side bonus, if you save the "vx_weak", "vx_strong" and "vx_parent" arrays and process a mutually exclusive set of z-target candidates (think of the two nrc candidates in a bi-value cell for example), you can logically and all the vx_weak arrays to test for concensus of eliminations, you can logically and all the vx_strong arrays to test for concensus of assignments, and you can use the vx_parent arrays to reconstruct any path needed for displaying network inference chains from any given end-point candidate back to the z-target.

This braids-like processing is not an exact implementation of Denis Berthier's nrczt-braids, but it is so much more powerful than anything else I have coded to date that I'm pretty jazzed about it. The bad news is that because the networked chains are not reversible, I'm not sure that it could be used in AIC/NL unless you tossed out loops. But if you do that, then you might as well just completely convert to nrczt since once you give up loops, you might as well take full advantage of zt processing.

I believe I promised this elsewhere, but I really need to document my implementation of nrczt braids and demonstrate what it can do. So, some may consider me an nrczt zealot. To which I say, "What's your point???" Smile

Cheers,
Paul
Back to top
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Tue Aug 04, 2009 5:05 am    Post subject: Reply with quote

For those who want to play around with nrczt and nrczt-(pseudo)-braids, I've uploaded my test project pascal code. You need Free Pascal 2.2.4 to recompile.

Download and unzip into a directory: http://pisaacson.fileave.com/Sudoku/sudoku.zip
The object is present, but it may not work since it was compiled under 64-bit Vista (sorry about that). I think it's a 32-bit application, but I won't swear by it.

Syntax is confusing and undocumented, but try something like the following:

sudoku -bv -Xprln -N32 -G9 -B < collection.in > collection.log

For a single grid in PM form use:

sudoku -bv -Xprln -N32 -G9 -B -P < pm_grid.in > pm_grid.log

The -B flag enables pseudo-braids and the -N32 -G9 limits nrczt chains to 16 conjugate pairs and ALS groups with upto 9 candidates. You can play around with AHS/AALS/ADLS by using various combinations of -H9 -Z9 -D9 (or -H4 -Z4 -D4 or -H6 -Z3 -D7 ... you'll figure it out if you look at sudoku.pas and understand getopt command line processing).

Let me know if you find any bugs. The -b flag enforces checking all assignments/eliminations against a DLX solution, and if there is any error, the step number will be preceeded by a '-' which is subtle, but pretty obvious if you issue 'grep "^\-" file.log'. I highly recommend installing cygwin or mingw if you want to use any of my programs. I'm not sure if it will actually work without one or the other -- haven't tried it...

As with all my test engines, I don't claim that this is a complete solver. It contains lots of other techniques that are debugged including a version of my ALS engine, but it's meant mostly to find all the possible nrczt chains or braids. The fact that it actually burns through lots of difficult puzzles is, while interesting, not its main purpose.

Have fun,
Paul
Back to top
View user's profile Send private message
leeo

Joined: 24 Jun 2009
Posts: 6
:
Location: USA NW

Items
PostPosted: Thu Aug 06, 2009 12:11 pm    Post subject: Documenting Nice Loops and Chains Reply with quote

It may help the discussion to realize that there are two problems in constructing line loops: The first is validating the a particular nice loop setup, the second is finding the nice loops that are valid. If you focus on the first problem, the end-user can find the required loop after some experimentation.

.6.2..........5.17.......92.8....2......9...4.....1......8....3.5.......9.1.7....

here is the result after one hidden pair: _[_-28_]_ <b5> r5c6 r6c5 and
and two box claims, one on a row and one on a column: rb bc claims: [6] _r23c7_ <bc> r56789c7 [8] _r8c13_ <br> r8c789

Code:

c001
Sudoku box
134578 ````6 `345789 | ````2 `1348 34789 | `3458 `3458 ``58
``2348 `2349 ``23489 | `3469 `3468 ````5 | `3468 ````1 ```7
134578 `1347 ``34578 | 13467 13468 34678 | 34568 ````9 ```2
---------------------+-------------------+------------------
134567*````8 `345679*| 34567 `3456+`3467 | ````2 `3567<1569>
123567 `1237 ``23567 | `3567 ````9 ```28 | 13578*35678 ```4
234567 23479 2345679 | 34567 ```28 ````1 | 35789 35678 5689
---------------------+-------------------+------------------
``2467 ``247 ```2467 | ````8 12456 `2469 | 14579 24567 ```3
234678 ````5 `234678 | 13469 12346 23469 | `1479 `2467 `169*
`````9 ``234 ``````1 | `3456 ````7 `2346 | ``458 24568 `568


If I attempt to start a chain from r4c9, the program highlights all of the strong links available from there. Then I just pick one of them to continue looking....

r4c9 =1= r4c1

There are no compatible strong links from r4c1, but the program points out two valid weak links:

Code:

c001
134578+````6 `345789 | ````2 `1348 34789 | `3458 `3458 ``58
``2348 `2349 ``23489 | `3469 `3468 ````5 | `3468 ````1 ```7
134578 `1347 ``34578 | 13467 13468 34678 | 34568 ````9 ```2
---------------------+-------------------+------------------
<134567>```8 `345679 | 34567 `3456 `3467 | ````2 `3567[1569]
123567 `1237+``23567 | `3567 ````9 ```28 | 13578 35678 ```4
234567 23479 2345679 | 34567 ```28 ````1 | 35789 35678 5689
---------------------+-------------------+------------------
``2467 ``247 ```2467 | ````8 12456 `2469 | 14579 24567 ```3
234678 ````5 `234678 | 13469 12346 23469 | `1479 `2467 `169
`````9 ``234 ``````1 | `3456 ````7 `2346 | ``458 24568 `568


now on picking one of them, I see a valid strong link from here.

r4c9 =1= r4c1 -1- r5c2

Code:

c001
134578 ````6 `345789 | ````2 `1348 34789 | `3458 `3458 ``58
``2348 `2349 ``23489 | `3469 `3468 ````5 | `3468 ````1 ```7
134578 `1347*``34578 | 13467 13468 34678 | 34568 ````9 ```2
---------------------+-------------------+------------------
[134567]```8 `345679 | 34567 `3456 `3467 | ````2 `3567[1569]
123567 <1237>``23567 | `3567 ````9 ```28+| 13578+35678 ```4
234567 23479 2345679 | 34567 ```28 ````1 | 35789 35678 5689
---------------------+-------------------+------------------
``2467 ``247 ```2467 | ````8 12456 `2469 | 14579 24567 ```3
234678 ````5 `234678 | 13469 12346 23469 | `1479 `2467 `169
`````9 ``234 ``````1 | `3456 ````7 `2346 | ``458 24568 `568


proceeding in this fashion, I can usually tie a chain like this into a nice loop - in this case a discontinuous nice loop:

=1= r4c9 =1= r4c1 -1- r1c1 =1= r1c5 -1- r7c5 =1= r7c7 -1- r8c9 =1=

This proves that r4c9 has 1 as its only valid solution, and, indeed, from that point singles are enough to solve.

= = =

Here are the 'simplifying assumptions' that I take to make these constructions possible:

<> if I chose any element already in the chain, the program discards any "abandonded tail", and attempts to close a nice loop. There is an "undo" facility if the loop is not what I have in mind.

<> The loop finds all of the compatible strong links from the tail node cell, and lists all of them. There is a provision for "weakening the last strong link", where the last strong link is replaced with all compatible weak links; or even employing a strong link as a weak link. If there are not any strong links, the program finds all compatible weak links.

<> a useful utility is to reverse the direction of the generated chain, thus to add items to the front which becomes the back of the chain. If I'm 'stuck' somewhere, this helps prevent a lot of backtracking.

= = =

now, currently the nodes are single cells. I am in the process of permitting nodes to be more than one cell. One difficulty I have is how to identify all of the strong links from a group of cells. It first is required to determine which house is shared with all of the selected cells and the last node on the chain. - This thorny problem leaves me stuck, and required overtime in my day job consumes all of my energy for now. --Lee
Back to top
View user's profile Send private message
nukefusion

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Tue Aug 11, 2009 9:43 am    Post subject: Reply with quote

Although still not quite finished I'm pretty sure I've coded all of the bits and pieces now that I need to find nice loops. After revisiting Denis Bethiers book a few times though I've started to shift my concentration onto the various chains he mentions in his book, including nrczt chains.

To that end, thanks for posting your examples Paul. I intend to attempt my own implementation of nrczt chains in the near future and it will be interesting to compare approaches.

Finally, I've come to the conclusion that nice loops seem like an awful lot of faffing around, if, as Denis states, similar eliminations can be acheived by simply using various chains instead.
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Tue Aug 11, 2009 10:13 pm    Post subject: Re: Documenting Nice Loops and Chains Reply with quote

leeo wrote:
proceeding in this fashion, I can usually tie a chain like this into a nice loop - in this case a discontinuous nice loop:

=1= r4c9 =1= r4c1 -1- r1c1 =1= r1c5 -1- r7c5 =1= r7c7 -1- r8c9 =1=

= = =

now, currently the nodes are single cells. I am in the process of permitting nodes to be more than one cell. One difficulty I have is how to identify all of the strong links from a group of cells. It first is required to determine which house is shared with all of the selected cells and the last node on the chain. - This thorny problem leaves me stuck, and required overtime in my day job consumes all of my energy for now.

I'm accustomed to working with chains and rarely rely on loops -- especially discontinuous loops. Below, the part in red is a notational correction to show the loop is discontinuous. It's seldom used. The part in dark red is extraneous. And the part in blue is an AIC that's logically sufficient to determine that [r8c9]<>1.

-1- r4c9 =1= r4c1 -1- r1c1 =1= r1c5 -1- r7c5 =1= r7c7 -1- r8c9 =1=

From what you say, you're currently working with bilocation, and maybe bivalue, cells to form chains. There are many other forms of strong links. Start with a mini-unit -- the intersection of a row/column with a box. Assume that a value is false in that intersection. Grouped and specialized strong links can be formed this way. You can build a table of strong links thusly.

A chain segment can then be formed by joining two strong links through a weak inference. The process continues to form longer chains. Sometimes, even continuous loops result during the weak inference step.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Goto page Previous  1, 2, 3  Next
Page 2 of 3

 
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