Building inference chains/nice loops

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

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!

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

daj95376 · 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.

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

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

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

daj95376 · 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 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.

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

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

PIsaacson · 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

PIsaacson · 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 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

PIsaacson · 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 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

leeo

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

nukefusion · 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.

daj95376