
View previous topic :: View next topic 
Author 
Message 
 nukefusion
 Joined: 27 Jun 2009  Posts: 22  :   Items 

Posted: Thu Jul 30, 2009 12:16 pm Post subject: 


Hmm, I'm having a bit of trouble here (again ) 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 


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

Posted: Fri Jul 31, 2009 12:58 am Post subject: 


Matt,
The loop that you've sketched is a continuous loop that may or may not cause any direct elimination of the ztarget. Instead, it may (or may not) allow eliminations along the two weaklinked legs: 12 and 43 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/sideeffect eliminations
// 2) [cell]=n= ... =m=[peer]m[cell]  [cell] <> m
//
// 3) [cell]=n= ... =m=[cell]  continuous loop w/sideeffect eliminations
// [cell] = mn is one sideeffect
// 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/sideeffect eliminations
// ronk doesn't think it's viable
// 7) [cell]n ... =m=[peer]m[cell]  continuous loop w/sideeffect 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 sideeffect elimination, and the fact that tests 15 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 12=43=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 nonlooping chains.
I've coded all three techniques and from numerous benchmarks against standard large or hard collections (royle17, top50000, top10000, gsfpuzzle30/33, tarekpearly6000, 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 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

Posted: Fri Jul 31, 2009 5:02 am Post subject: 


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:
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 


 nukefusion
 Joined: 27 Jun 2009  Posts: 22  :   Items 

Posted: Fri Jul 31, 2009 6:22 am Post subject: 


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 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

Posted: Fri Jul 31, 2009 6:33 am Post subject: 


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 


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

Posted: Fri Jul 31, 2009 1:14 pm Post subject: 


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 fieldguide 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 ztarget 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 (ztarget).
This works identically for both BFS and DFS for detecting loops back to the ztarget. 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 reenter, but BFS, less so and you'll need to have special reentry 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 ztarget 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/falsehood 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 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

Posted: Fri Jul 31, 2009 4:06 pm Post subject: 


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 linkedlist 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 


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

Posted: Fri Jul 31, 2009 7:11 pm Post subject: 


daj95376 wrote:  ... In this case, your BFS "graph" is a circular linkedlist 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 pseudocode how this works? If you remove the oldest entries from a circular linkedlist, 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 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

Posted: Fri Jul 31, 2009 9:14 pm Post subject: 


PIsaacson wrote:  daj95376 wrote:  ... In this case, your BFS "graph" is a circular linkedlist 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 pseudocode how this works? If you remove the oldest entries from a circular linkedlist, 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:
(As I described in an earlier breakdown of this chain segment.) 

Back to top 


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

Posted: Sat Aug 01, 2009 4:39 am Post subject: 


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 


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

Posted: Tue Aug 04, 2009 1:31 am Post subject: 


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 networklike nrczt chains. The best way I can describe this is to have you imagine the entire tree stemming from some ztarget candidate. Every even level contains all the various "truths" generated by the BFS tree walk. Every odd level contains all the various "falsehoods". In the code, if the sw_braids is nonzero, 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 N1 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 ztarget candidates (think of the two nrc candidates in a bivalue 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 endpoint candidate back to the ztarget.
This braidslike processing is not an exact implementation of Denis Berthier's nrcztbraids, 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???"
Cheers,
Paul 

Back to top 


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

Posted: Tue Aug 04, 2009 5:05 am Post subject: 


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 64bit Vista (sorry about that). I think it's a 32bit 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 pseudobraids 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 


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

Posted: Thu Aug 06, 2009 12:11 pm Post subject: Documenting Nice Loops and Chains 


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 enduser 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 


 nukefusion
 Joined: 27 Jun 2009  Posts: 22  :   Items 

Posted: Tue Aug 11, 2009 9:43 am Post subject: 


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 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

Posted: Tue Aug 11, 2009 10:13 pm Post subject: Re: Documenting Nice Loops and Chains 


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 miniunit  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 




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
