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 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: Wed Jul 22, 2009 1:59 pm    Post subject: Building inference chains/nice loops Reply with quote

Hi everyone,

I'm currently trying to understand how to go about building an inference chain and eventually a nice loop and I could really do with some of your imput please.

I'm planning on starting out by building a BB plot of some sort (a list of all bivalue cells and conjugate pairs).

Then I will be looking for a suitable starting cell, by that I mean preferably one with 3+ candidates and a strong link to another cell via a conjugate pair.

The problem is that I'm not sure what the best process is from there. What criteria should I use when determining which is the next node? Should I look for strong links (bi-local units) first, then weak links (bi-value units) if I can't find one?

Does anybody else have any experience of building inference chains/nice loops and what the best practices are?

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

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Wed Jul 22, 2009 4:59 pm    Post subject: Reply with quote

[Withdrawn]

Last edited by daj95376 on Mon Jul 27, 2009 7:34 am; edited 1 time in total
Back to top
View user's profile Send private message
PIsaacson

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

Items
PostPosted: Thu Jul 23, 2009 3:29 pm    Post subject: Reply with quote

nukefusion,

I've coded Denis Berthier's nrczt chains as well as Myth Jellies AIC chains and niceloops and I'm on about the 4th or 5th generation for each. I'm going to base my recommendations on nrczt chains, but most of it is directly usable for AIC or niceloops, you just need some changes in testing for exit conditions.

1) Think of the sudoku grid as a 3d puzzle using row/col/number coordinates for each candidate. This gives you a 9x9x9 3d perspective of the 729 possible candidates.

2) Think of the 729 candidates as possibly linking to any of the other 729 candidates. This gives you a starting structure for establishing the parent/child or left-hand/right-hand linking needed for generating a chain. I generate a list containing the following structure in C/C++
Code:

typedef struct
{
    short    lh_vx;    // parent or left-hand vertex d1*81+r1*9+c1
    short    rh_vx;    // child or right-hand vertex d2*81+r2*9+c2
    short    linkage;  // strong/weak/group-strong/group-weak 4 types of links (group used for ALS/GSL/ER/AUR etc)
    short    group;    // used to identify the specific group (0 = RC, 1 = RN, 2 = CN, 3 = BN, 4 = ALS, 5 = AALS...)
} nrc_t;

For standard b/b nrc linkages, walk the grid cell by cell. For each cell that contains multiple candidates, generate all the possible nrc relationship. Eg. r1c1 {123}

d1 = 0 r1 = 0 c1 = 0 d2 = 1 r2 = 0 c2 = 0 lh_vx = 0 rh_vx = 81, linkage = weak_link, group = type_rc (rc space)
d1 = 0 r1 = 0 c1 = 0 d2 = 2 r2 = 0 c2 = 0 lh_vx = 0 rh_vx = 192, linkage = weak_link, group = type_rc (rc space)
d1 = 1 r1 = 0 c1 = 0 d2 = 0 r2 = 0 c2 = 0 lh_vx = 81, rh_vx = 0, linkage = weak_link, group = type_rc (rc space)
d1 = 1 r1 = 0 c1 = 0 d2 = 2 r2 = 0 c2 = 0 lh_vx = 81, rh_vx = 192, linkage = weak_link, group = type_rc (rc space)
d1 = 2 r1 = 0 c1 = 0 d2 = 0 r2 = 0 c2 = 0 lh_vx = 192, rh_vx = 0, linkage = weak_link, group = type_rc (rc space)
d1 = 2 r1 = 0 c1 = 0 d2 = 1 r2 = 0 c2 = 0 lh_vx = 192, rh_vx = 81, linkage = weak_link, group = type_rc (rc space)

This single cell generates 6 nrc entries from the RC space POV. You need to do this for all the RC/RN/CN/BN spaces and set the linkage to strong_link on bi-local/bi-value conditions.

3) The nrc list can be extended using groups (ALSs etc.) and all you need to do is consider that regardless of what group technique is used, they can all be reduced to multiple nrc entries. Later you will use the combined lh_vx/rh_vx to extract the exact group information from the correct group table. For example, when I generate ALS group entries I locate and ALS, then I find a left-hand candidate that when true, will become an RCC (restricted common candidate) and cause the ALS to convert to a Locked Set. Then I see if the newly formed LS causes any eliminations. If it does, then these candidates become the right-hand candidates. I flag the linkage as a group-weak-link since it's based on the lh true condition. I use the lh/rh pair as the key into an ALS lookup table to reconstruct the group id when displaying the chain. By treating all group extensions in a similar fashion the actual search code can be very compact since it only deals with lh/rh nrc candidates and the linkages for generating chains.

4) Now that you have your nrc list, you need to convert it into a graph adjacency matrix so that you can use either a standard BFS (breadth first) or DFS (depth first) search algorithm. I use a simple 729x728 matrix with a counter for the number of edges (children) posted for each parent vertex. In C/C++
Code:

typedef struct
{
    short    vx;          // child vertex
    char     linkage;     // linkage type
    char     group;       // group type
} edge_t;

typedef struct
{
    int      n_edges;     // count of child vertices
    edge_t   edge[728];   // maximum possible number of children - cannot link to yourself (check for this!)
} vertex_t;

typedef struct
{
    vertex_t vertex[729]; // maximum possible number of parents
} graph_t;

typedef struct
{
    bitset<729> vx_linked[729]; // used for quick linkage testing
} vxlinks_t;

Simply initialize the graph->vertex[n].n_edges to zero and use the nrc list to add the edges. As a helper structure, also maintain the simple 729x729 vx_links bitsets by initializing to all zeros and setting the correct entry to 1 (true) for each edge stored. This will be helpful for quickly testing certain exit conditions later on.

5) If you've built the graph adjacency matrix correctly, you can use a really standard BFS/DFS algorithm for generating chains simply and quickly. BFS requires a slightly modified queue structure since you'll need to carry the entire path (chain) in each queue entry. DFS is slighty easier to handle since you only need a single stack entry for storing the current path (chain). I have a special queue class that I wrote in C/C++ that is very efficient even for very deep paths of 127 levels. Using BFS and some nrczt techniques for quickly determining exit criteria, I rarely go deeper than 24 levels, or 12 conjugate pairs.

6) It's time to discuss alternating links, conjugate pairs, z targets and how to pick a good starting candidate. If you've read Myth Jellies AIC thread, then you should have an understanding that all chains are based on alternating stong and weak links. Denis Berthier's nrczt chains treats them as conjugate links with a left-hand implicit false and a right-hand true for presentation. You'll need to pick one of AIC/niceloop/eureka/nrczt for your display method, but not to worry, because the internals for chain generation are identical. So, now you have to pick a start vertex (z target in Denis's terminology) for the BFS/DFS algorithms. I usually walk the grid and start by testing for bi-value/bi-local conditions, then tri-value/tri-local conditions etc. That way, if you reduce a bi-value/local, you know you have a naked/hidden single, so you can drop down to lower logic (unless you want to find all possible chains which I usually do since the BFS/DFS is extremely fast in C/C++).

7) Okay, now for some actual code. Here's my BFS in pascal:
Code:

function grid_t.nrc_bfs (ve : edge_t) : integer;

var
  n, l, level, cn, nc, zt, x1, x2, vp : integer;
  vc : edge_t;
  label next_edge;

begin
  vx_queue.reset ();
  vx_queue.push (nrc_stack);

  while (vx_queue.pop (nrc_stack)) do
    begin
      vp := nrc_stack.e[nrc_stack.l].v;
      cn := vx_graph.vertex[vp].n_edges;
      level := nrc_stack.l;
      l := level and 1;

      for nc := 0 to cn-1 do
        begin
          vc := vx_graph.vertex[vp].edge[nc];

          if (vc.v = z_vertex) then
            begin
              continue;
            end;

          nrc_stack.l := level+1;
          nrc_stack.e[nrc_stack.l] := vc;
          x1 := vc.v;

          if (l = 1) then
            begin
              if (vc.t <> strong_link) then
                begin
                  if (vc.t <> weak_link) then
                    goto next_edge;

                  zt := nrc_promote (nrc_stack, level);
                  nrc_promotions[zt] += 1;
                  if (zt = 0) then
                    goto next_edge;

                  vc.t := zt;
                  nrc_stack.e[nrc_stack.l].t := zt;

                  if (zt = z_whip) or (zt = t_whip) or (zt = zt_whip) then
                    begin
                      nrc_return := 1;
                      exit (level+1);
                    end;
                end;

              if (sw_braids = 0) then
                begin
                  n := 0;
                  while (n < level) do
                    begin
                      x2 := nrc_stack.e[n].v;
                      if (vx_links[x2, x1] = true) then
                        begin
                          nrc_return := 2;
                          exit (level+1)
                        end;
                      n += 2;
                    end;
                end
              else
                begin
                  for n := 0 to vx_count-1 do
                    begin
                      x2 := vx_stack[n];
                      if (vx_links[x2, x1] = true) then
                        begin
                          nrc_return := 2;
                          exit (level+1)
                        end;
                    end;
                end;

              if (vx_links[vc.v, z_vertex] = true) then
                exit (level+1);
            end;
         
          if (l = 1) then
            begin
              if (vx_weak[vc.v] = true) then
                begin
                  nrc_return := 3;
                  exit (level+1);
                end;
              if (vx_strong[vc.v] = true) then
                begin
                  continue;
                end;
              vx_strong[vc.v] := true;

              if (sw_braids <> 0) then
                begin
                  vx_stack[vx_count] := vc.v;
                  inc (vx_count);
                  if (vx_count >= high (vx_stack)) then
                    begin
                      setlength (vx_stack, high (vx_stack) + 513);
                    end;
                end;
            end
          else
            begin
              if (vx_strong[vc.v] = true) then
                begin
                  nrc_return := 4;
                  exit (level+1);
                end;
              if (vx_weak[vc.v] = true) then
                begin
                  continue;
                end;
              vx_weak[vc.v] := true;
            end;

          if (nrc_stack.l < nrc_max) then
            begin
              vx_parent[vc.v] := vp;
              vx_queue.push (nrc_stack);
            end;

        next_edge:
          continue;

        end;
    end;

    exit (-1);
end;


8) Okay, so it isn't commented very well. Actually it isn't commented at all, but then I know what it's doing so it makes sense to me. If you google "boost bfs" you'll see the basis for the bfs algorithm. I'm using two bitsets (vx_strong and vx_weak) to implement the color vector and also to detect whether or not there is a discrepancy in usage (vertex being used in both a true and false condition is invalid). These bitsets also allow for skipping re-exploring of vertices that are already in progress or done just like the color vector. I only use the parent vector for braids, but you'd have to read all of Denis Berthier's threads on braids for this to make much sense. Suffice it to say that nrczt braids allows for solving really really hard sudoku puzzles.

If you have specific questions on the code or want the whole mess, PM me and I'll zip it up and e-mail you a copy.

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

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Thu Jul 23, 2009 6:40 pm    Post subject: Reply with quote

daj95376 wrote:
I hope you get some very informative replies!!!


Well it doesn't get much more informative than this. Thanks for your input people, it's a great help.

Paul, once again I am absolutely astounded at the detail, time and thought put into your replies. Thank you. It's going to take me a while to digest this one; it looks like there's everything I could possibly need in there! I'm sure I'm not the only one who will benefit from this thread.

Cheers!

Matt.
Back to top
View user's profile Send private message
PIsaacson

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

Items
PostPosted: Thu Jul 23, 2009 8:50 pm    Post subject: Reply with quote

Matt,

Unfortunately, the nrc_bfs function is just a teaser for the whole enchalada, so it might lead to more questions than answers. Denis Berthier has encouraged/challenged me to present my implementation of his nrczt-whips/braids and I don't want to hi-jack your thread, so I'll have to open a new topic when I have sufficient material to warrant publishing. Unfortunately, or fortunately depending upon point of view, I'm on vacation for another month so my sudoku time is strictly limited per family decree.

In the meantime, you might want to search for threads on strong links or strong inferences. There's an interesting topic on the Player's forum regarding using URs in chains: http://www.sudoku.com/boards/viewtopic.php?t=6648

Also, Denis has numerous topics in this forum and the Player's forum regarding nrczt chains. I'll admit up front that I'm a convert and I would dearly love to have another programmer implement nrczt chains. Nudge, nudge...

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

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Mon Jul 27, 2009 6:17 am    Post subject: Reply with quote

PIsaacson wrote:

Also, Denis has numerous topics in this forum and the Player's forum regarding nrczt chains. I'll admit up front that I'm a convert and I would dearly love to have another programmer implement nrczt chains. Nudge, nudge...


Well, I've invested in a copy of Denis Berthiers book so it may be something I look to do in the future. Although Denis mentions at the start that the book is meant for anyone interested in sudoku, I'm of the opinion that it can be a little "heavy going" in places, so it'll take a while for me to absorb it.

For the meantime I'm going to concentrate on getting the underlying architecture and nice loops up and running in order to get my logical solvers success rate up to a reasonable level. At the moment it stumbles on the harder puzzles as I've only implemented the most basic of chains as of yet (XY chains, XY wing)

Once that has been achieved though I'll defintely be revisiting nrczt chains.
Back to top
View user's profile Send private message
nukefusion

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Tue Jul 28, 2009 2:26 pm    Post subject: Reply with quote

Ok, it seems I've run into a bit of trouble implementing these nice loops (or "not-so-nice loops" as I now like to call them) Laughing

I'm building a matrix with all of the nrc links - no problem there as far as I know.
I've got the exit conditions within the search nailed (I think) and am now getting loops that satisfy the criteria for a nice loop.

The problem with the current implementation is the performance which, quite frankly is very poor at the moment. Solving a puzzle which requires the use of at least 3 or 4 loops (depending on complexity) can take anywhere from 2 to 30 or 40 seconds on a 3ghz machine.

I think the problem lies in my search routine. After a good couple of weeks wrapping my head around it I don't think I can see the wood for the trees anymore.

Presently, the search routine is taking the sledgehammer approach of picking a start cell and canididate digit and building chains by following every possible combination of paths in the matrix until it finds one that loops back on itself. If it doesn't, or the loops it does find are useless, i.e. no candidates can be removed/cells solved, it moves on to the next start cell/digit combination and tries all over again. It uses a stack and performs a kind of depth first search.

This current method isn't really all that efficient. In the course of this routine, it's obviously retravelling paths that it's travelled before, the only thing being different is the cell it needs to link back on to form the loop. Also, as the level of the search gets deeper, the number of paths to trace from that one starting cell grows exponentially.

I'm struggling to think of any way that I can improve on this at the moment. Any advice or wisdom from those that have trodden this path already would be much appreciated right now.
Back to top
View user's profile Send private message
PIsaacson

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

Items
PostPosted: Wed Jul 29, 2009 12:12 am    Post subject: Reply with quote

Matt,

I'm not sure I understood your algorithm correctly, but it sounds like you are not keeping track of which nodes you have already explored (the color matrix) and that you are sweeping an array for linking candidates instead of using a "pivot" of the right-hand child becoming the new left-hand parent for each descending level. This is unconstrained path exploration and you are re-exploring parents needlessly.

If you built an adjacency matrix and used a standard BFS or DFS algorithm as described by the Boost library documentation, then it should be taking more like 20-50 milliseconds to generate a full tree for all the potential target nodes (z-candidates) instead of 20-50 seconds. I highly recommend that you stick with the time honored approach of copying a proven, efficient algorithm.

At the very least, just add the parent tracking (color) code and don't bother to process parent nodes that you have already explored.

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

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Wed Jul 29, 2009 6:12 am    Post subject: Reply with quote

Hi Paul,

Thanks for your guidance. Your correct about my current implementation - I'll re-read the boost documentation and do some swotting up.

I must admit I confused myself thinking about the "pivot" part and would be grateful if you could help me clear up on one aspect.

I've been adding nrc links on the based on the rules in Berthiers book where he states:

Quote:
Two candidates n1r1c1 and n2r2c2 are nrc-linked if they are different and their underlying nrc-cells are nrc-linked, i.e. if:

- either n1 = n2 and the two rc-cells (r1c1) and (r2c2) are rc-linked in rc-space,
- or n1 != n2 and the rc-cells (r1c1) and (r2c2) are the same


I notice in your code example that the "key" used for the child vertex is a hash of digit row and column. It's my understanding that in a nice loop, a cell can link in on one digit, and out on another (depending on the type of links of course).
The rules above don't seem to allow for that situation directly - sure, using the above rules there are nrc-links between differing candidates within a cell, but these aren't show in the nice loop (for example, if a cell has an incoming link on 7 and an outgoing for 5, you wouldn't show the link between 7 and 5 in the same cell). Is this something I'm supposed to be dealing with at the time I build the matrix or is it just filtered out when I display the loop (either graphically or using notation)?

In the meantime I'll try to digest this algorithm a few times over. Off for some strong coffee I think.

Thanks,
Matt.
Back to top
View user's profile Send private message
PIsaacson

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

Items
PostPosted: Wed Jul 29, 2009 2:28 pm    Post subject: Reply with quote

Matt,

Okay, here goes in attempting to answer your questions in order:

1) Pivots - what the heck am I talking about?

In the primitive days of IBM ISAM (indexed sequential access method), you had to declare the primary key as the combination of the parent plus the child with the remainder of the data just part of the "record". A pivot consisted of taking the child (right hand part of the key), moving it to the parent (left hand part of the key), zeroing out the child part and then seeking on the new key with a greater or equal option. This effectively positioned you to start reading at the next record in your nrc isam file and hopefully, you started reading/processing the children of the new parent. Each pivot decended into the tree one level and you continued to descend (dfs) until you couldn't go any further. You needed to save all the current key level by level and restore your position as you traversed or reentered each branch by level.

In C/C++, you can use the STL map to emulate a ISAM file. The definition looks like the following:
Code:

#include <map>

use namespace std;

// AIC niceloops maps and tables

typedef struct
{
    short          lh_vx;
    short          rh_vx;
} nlkey_t;

typedef struct
{
    short          nl_link;
    short          nl_group;
    short          lh_cands;
    short          rh_cands;
} nldata_t;

struct nl_sort
{
    bool operator () (const nlkey_t nl_key1, const nlkey_t nl_key2) const
    {
        if (nl_key1.lh_vx < nl_key2.lh_vx) return true;
        if (nl_key1.lh_vx > nl_key2.lh_vx) return false;
        if (nl_key1.rh_vx < nl_key2.rh_vx) return true;
        if (nl_key1.rh_vx > nl_key2.rh_vx) return false;
        return false;
    }
};

typedef map<const nlkey_t, nldata_t, nl_sort> nllist_t;

nllist_t           nl_list;


I use a special red/black add-on class for pascal from http://fpcfun.firmos.at/bin/view/Freepascal/GenericRedBlackTree
It provides the equivalent operations as the STL map class. I'm not sure what is available for Java etc., but I'm assuming that there are similar types of objects/classes available.

You really need some type of class/object like the STL maps in order to code an effective tree pivot. An ancient alternative is to sort your nrc list and use a binary search to rapidly locate the pivot points. You really don't want to sequentially walk the entire nrc list in order to locate "matching" children.

2) nrc candidates? I'd say the vertex is computed rather than hashed, but that's semantics. You just need some method of computing the vertex number and for re-constructing the original digit/row/column as needed. I use the following in C/C++:
Code:
vertex = (digit * 81) + (row * 9) + column;
digit = vertex / 81;
row =  (vertex / 9) % 9;
column = vertex % 9;

As for the distinction between the entry/exit for niceloops, ignore that for now and consider it a display/presentation problem. There are two possible linkage types in a multi-value cell between all the possible candidate combinations. If there are only two candidates, then the link is a strong-link, otherwise it is a weak link. If you are correctly tracking levels, then depending on how you are counting, one of either all the odd or the even levels will demand strong-links.

So the answer is that you need to be aware at all times of what types of links you have and are looking for during the chain generation. Once the chain is developed (and again the process is identical for AIC/niceloops/nrczt), then you can worry about presenting the chain in some acceptable format. I've coded all three and use an runtime option to specify the desired format. I have not coded eureka notation, so I can't say how difficult that one is. Based on the lines of code, AIC is the smallest while niceloops and nrczt are about tied. They all process the exact same chain table which consists of the path as a table of the edges (see previous message) level by level. Level zero for me is the z-target (assumed true), so each odd level (assumed false) requires strong-linked children for the subsequent even level (assumed true). The even level parents can have children with any type of link (strong/weak/group). AIC/niceloops/nrczt all require this alternating true/false logic in order to construct valid chains.

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

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Wed Jul 29, 2009 7:35 pm    Post subject: Reply with quote

Thanks Paul for your replies, and for your patience!

I think it has finally clicked! One of the main things that had really thrown me was the fact that the Nice Loop notation doesn't list the links between candidates of the same cell. For example, take this small portion of a nice loop:

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

Two strong links but on different candidates. This is valid, but what I wasn't understanding is the simple concept that there is an implied weak link on R9C2 between candidate 6 and 8. Basic stuff and simple when you understand it exists.

I've been going mad trying to implement all of these Nice Loop propagation rules I've read about, when all I really need to do (as has been stated!) is build the nrc list and link them together, alternating strong/weak links. Whether or not the links between candidates of a same cell are displayed or not is purely a matter of presentation.

Thanks for your insight into the pivots, I've certainly learnt something there. I'm now halfway into rewriting the whole algorithm implementing BFS and a colour matrix and initial tests are looking good. I'll post back again when I've cracked it (hopefully!).

Cheers,
Matt.
Back to top
View user's profile Send private message
nukefusion

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Wed Jul 29, 2009 9:00 pm    Post subject: Reply with quote

Ok, it seems I didn't get as far as I wanted without another question.

It seems to me that all the other implementations of nice loops I've seen take into account any candidate eliminations that may have taken place due to placements made earlier in the chain. For example, take a row that has 3 cells with a candidate 7 in. If I use 1 of the 7's some where at the start of the chain, the other 2 technically then become a conjugate pair. That's not taken into account with the method I'm using at the moment, as when I build the nrc list it's effectively taking a snapshot of the grid before I've started building any chains.

Take this loop below for example. Surely the only way there can be a strong link between R6C1 and R9C1 on candidate 7 is because 7 has been eliminated from R5C1 by the placement of 4, right at the beginning of the chain.



Building the graph beforehand, I'll never see these two 7's as a conjugate pair in C1 unless I somehow update it after making the first assignment of candidate 4 in R5C1. How is this handled using your method?

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

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

Items
PostPosted: Thu Jul 30, 2009 12:02 am    Post subject: Reply with quote

Matt,

Strictly speaking, prior true values are never considered in niceloops or AIC logic. Only nrczt takes the prior true values into account using Denis' zt promotions. I would say that the example you included is (probably) listed as a forcing chain rather than a niceloop/AIC, although it is a valid nrczt chain. Here's the main reason NL and AIC don't allow priors to be considered: It (usually) makes the chain non-reversible and hence invalid for continuous loops, which must be reversible to be usable. Denis' nrczt chains skirt this issue by never allowing loops, so with that premise assumed, it's okay to generate chains that can only be true/processed in a left to right fashion.

That said, it's also true that AIC and NL can be extended with group logic which sometimes looks like it takes advantage of prior true values. But it's really based on logical inferences using things like ER hinges or box/line interactions or ALSs etc., and the links must be reversible. In general, group extensions greatly increase the ability of AIC/NL/nrczt to solve difficult puzzles. Think of all group extensions as providing additional nrc links from parents to otherwise inaccessable children and you can start to see how/why they can easily be added to the adjacency matrix. Just be sure to retain the link/group for each child in your current path stack. I simply store the child edge (see prior definitions) struct for each level with level 0 (the z-target) as the top-most parent having a zero link/group.

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

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Thu Jul 30, 2009 3:02 am    Post subject: Reply with quote

nukefusion wrote:
One of the main things that had really thrown me was the fact that the Nice Loop notation doesn't list the links between candidates of the same cell. For example, take this small portion of a nice loop:

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

Two strong links but on different candidates. This is valid, but what I wasn't understanding is the simple concept that there is an implied weak link on R9C2 between candidate 6 and 8. Basic stuff and simple when you understand it exists.

There is nothing implied.

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

In the case of your short chain segment:

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

[R1C2]=6=[R9C2]            Strong Link:   bilocation
       6=[R9C2]=8          Weak   Link:   ?-value cell
         [R9C2]=8=[R9C5]   Strong Link:   bilocation

This is why I've switched to Eureka notation:

Code:
Strong Link (SL):  ( bilocation  (n)a = (n)b ) or ( bivalue cell  (m=n)c )
Weak   Link (WL):  ( peers       (n)d - (n)e ) or ( ?-value cell  (m-n)f )
___________________________________________________________________________

The weak link is more obvious in [r9c2].

Code:
(6)r1c2 = (6-8)r9c2 = (8)r9c5
Back to top
View user's profile Send private message
nukefusion

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Thu Jul 30, 2009 6:02 am    Post subject: Reply with quote

daj95376 wrote:

There is nothing implied.


Thanks daj95376, I'm not really that well versed with Eureka notation but it does look like it conveys more information. When I say implied I merely meant that those weak bi-value links are quite often not written down in a lot of the notation I've seen, for brevity or whatever reason. I'd imagine the more advanced and more knowledgable people than myself can quite easily do without them.

Thanks Paul for the extra detail. I've got something up and running and need to do some testing now. Run time is now under a second to find all of the loops in the grid, a slight improvement on my previous attempt!

Cheers,
Matt.
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 1, 2, 3  Next
Page 1 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