Building inference chains/nice loops

nukefusion

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.

daj95376 · Posted: Wed Jul 22, 2009 4:59 pm Post subject:

[Withdrawn]

PIsaacson · Posted: Thu Jul 23, 2009 3:29 pm Post subject:

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

nukefusion · Posted: Thu Jul 23, 2009 6:40 pm Post subject:

PIsaacson · Posted: Thu Jul 23, 2009 8:50 pm Post subject:

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

nukefusion · Posted: Mon Jul 27, 2009 6:17 am Post subject:

nukefusion · Posted: Tue Jul 28, 2009 2:26 pm Post subject:

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.

PIsaacson · Posted: Wed Jul 29, 2009 12:12 am Post subject:

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

nukefusion · Posted: Wed Jul 29, 2009 6:12 am Post subject:

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:

PIsaacson · Posted: Wed Jul 29, 2009 2:28 pm Post subject:

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:

nukefusion · Posted: Wed Jul 29, 2009 7:35 pm Post subject:

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.

nukefusion · Posted: Wed Jul 29, 2009 9:00 pm Post subject:

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.

PIsaacson · Posted: Thu Jul 30, 2009 12:02 am Post subject:

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

daj95376 · Posted: Thu Jul 30, 2009 3:02 am Post subject:

nukefusion · Posted: Thu Jul 30, 2009 6:02 am Post subject: