Medusa works -- alternative to X/Y cycles for 9x9

Bob Hanson

My Sudoku Assistant page at http://www.stolaf.edu/people/hansonr/sudoku now uses a new strategy. I'm calling it "Medusa" because it behaves like a set of snakes making their way through a 3D maze.

The Medusa (M) strategy amounts to a generalized synthesis of Glenn Fowler's "X" and "Y" constraints, where we allow them to mix in a 3D fashion. What's interesting to me to see is how compact the coding is. (Most of the JavaScript on that page is just overhead for the display.) All it really is, is a building of strong chains and then an investigation into how they are connected by "weak links" (able to transmit parity both directions) and "weak corners" (able to be set, but can't transmit parity to another strong chain). Glenn's "even" and "odd" business is incorporated completely in this parity framework.

For the record, for http://magictour.free.fr/top95 I get 47 solutions (that is, with 0 constraint).

This was a fun little project that I hope will inspire others to think up new strategies for solving Sudoku puzzles.

Thanks to Glenn Fowler for his excellent descriptions at http://www.research.att.com/~gsf/sudoku/ of the X- and Y- constraints.

If anyone knows of additional strategies that you would like to see illustrated on my page, please let me know at hansonr@stolaf.edu.
I'm totally open to making it demonstrate additional strategies.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

Interesting strategy.

Just to sync terminology:

X-Constraint equals Fishy Cycles, subsumes X-Wing and "minimal" swordfish
Y-Constraint equals forced chains and subsumes XY-Wing (a small FC)
W-Constraint catches seafood (swordfish, jellyfish) without strong edges that slipped through the nets of X-Constraint.

A few questions:

Does the M-strategy cover the broader effects of multicoloring, such as the eliminations by conjugates of mutually excluding colors?

Have you also integrated the W-Constraint?

With such an abstract mechanism, how would you be able to give meaningful feedback to the user, in the form of hints?

I am very interested in combining short Forced Chains (in particular XY-Wing) with coloring. An XY-Wing on itself can eliminate a few candidates, but combined with coloring, there could be a better yield than the 2 techniques by themselves.

Do you have anything to compare your method with, as to see whether it actually does a better job than "traditional" techniques?

Lummox JR · Posted: Mon Oct 17, 2005 10:01 pm Post subject:

It sounds to me like Medusa is a form of supercoloring, if I'm not mistaken. Essentially you're using true/false conjugates throughout the 4D constraints (4D because although it's a 3D grid, the box constraint also matters), and that's exactly what supercoloring does.

From what I gather it seems like supercoloring is one of those techniques that can be discovered from multiple paths.

Bob Hanson · Posted: Mon Oct 17, 2005 10:25 pm Post subject:

quote:

Does the M-strategy cover the broader effects of multicoloring, such as the eliminations by conjugates of mutually excluding colors?

If you give me an example, I'll let you know.

Have you also integrated the W-Constraint?

cells with W-constraints fall out earlier in a generalized subset elimination.

With such an abstract mechanism, how would you be able to give meaningful feedback to the user, in the form of hints?

Don't know. It's just the X/Y business extended.

I am very interested in combining short Forced Chains (in particular XY-Wing) with coloring. An XY-Wing on itself can eliminate a few candidates, but combined with coloring, there could be a better yield than the 2 techniques by themselves.

Oh, absolutely. XY wings are taken care of very easily:

XY XZ

ZY *

This amounts to a 3D Medusa chain. (vertical lines represent same column,
strong links. horizontals are across rows, diagonals are in the 1-9 "vertical" direction.

X------X
\ \
Y \
| \
| \
Y Z
\
\
Z *

Z cannot be at the *.

Well, I can see the trouble will be describing this without actually using the Sudoku Assistant! In any case, an XY wing Medusa chain, ZYYXXZ is just a small version of a general sequence Z-x-y-(x-y)n-(x-w-y)n-x-y-Z, which forces * to NOT be Z. (because one of the Z's has to be Z).

What the Medusa idea does is allow ANY sort of strong (x-y) or selective weak (x-w-y, but not y-w-x) link sequence in this chain.

Quote:

Do you have anything to compare your method with, as to see whether it actually does a better job than "traditional" techniques?

Define "better". Define "traditional." The only thing I've done is put it up against Top95. There it found a few more 0-constraint solutions than Glenn Fowler's sudoku(1) program.

But, understand, this is just a JavaScript implementation. I wouldn't know how it stacks up in terms speed, as that's not what JavaScript is about.

My goal was simply to demonstrate what I intuited: that the Y-constraint/X-constraint distinction is artificial. They are just two subsets of a much broader "M" category.

W-constraints are not of this type; they are just a form of subset elimination, which this is not. The Sudoku Assistant handles all hidden/naked tuples X-winds, swordfish, and X-wing-like W constraints in one small recursive function. They are all done before M.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Bob Hanson · Posted: Tue Oct 18, 2005 12:14 am Post subject:

OK, how about this:

Here's a simple XY-wing:

http://www.stolaf.edu/people/hansonr/sudoku?DEMO=[2,4:2,4][2,5:4,8][5,4:2,8][5,5:8]&MODE=3D

And a more involved one, with a weak link (the green dot):

http://www.stolaf.edu/people/hansonr/sudoku/index.htm?DEMO=[2,4:2,4][2,5:3,4,5][2,6:4,8][5,4:2,8][5,6:8]&MODE=3D

What do folks think about using the Sudoku Assistant as a visualization tool?

Feel free.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

Here is an example of multicoloring, credit to Lummox JR:

Now if two colors exclude each other, they can't both be true; they may even both be false. But their conjugates have the opposite situation: They can't both be false, and may even both be true. Since in this example A!B, that means either a or b or both are true. Now you can look for intersections with a and b, and you'll find that they meet at (9,7). Therefore, (9,7)<>4.

Bob Hanson · Posted: Tue Oct 18, 2005 3:16 am Post subject:

The Medusa strategy totally bypasses any search for structured elements such as "XY-wings". The idea is as follows, with the function name of http://www.stolaf.edu/people/hansonr/sudoku that does the job, for reference:

1) getStrongEdges() Identify all "strong edges". I think this is what you mean by conjugate pairs -- any pair of "nodes" (row, column, value points) that are mutually exclusive. These include:

a) a row, column, or block with exactly two occurances of a value.
b) a cell with exactly two possibilities.

2) getStrongChains(), addNode() Idenfity chains of these "strong edges". We aren't looking for any pattern, just identifying the chains. We don't need to identify the pattern of connection (x-cycle, y-cycle, etc.) , but we do assign an alternating +/- parity to these as the chains are linked. Assign alternating "parity" -- ok, color -- to each node in a strong chain as nodes are added. Thus, each chain is a binary set -- x,y,x,y,x,y.... If one "x" is true, then all "x"s are true and all "y"s are not. If one "y" is true, then all "y"s are true and all "x"s are not.

4) checkParities() Identify all cells directly "influenced" by the strong chains -- that is, in the same row, column, or block and having the same candidate value. These are either (a) part of the same chain (a cycle), (b) part of a different chain (possibly a cycle), or (c) not on any chain (weak nodes). What the Medusa strategy identifies is that in all directions -- row, column, and block -- from these chains are forced conditions -- if a 6 is in the same row as a strong node with value 6, then I call that off-chain node a "weak node".

5) checkParity() As interactions are found, assign parity to them as well. Interaction with a "+" node leads to "-" parity; interaction with a "-" node leads to "+" parity. If a second interaction wih the (same) chain is found, compare the parities of the two chain nodes. If they are both the same, ok, but if they are different, delete this possibility and start over. Note that because the "target" node may be a chain node itself (chain wrapping onto itself), this could change the nature of the chains, and we abandon ship -- delete and start over.

At this point we have found all possible incompatible strong-chain cycles and invalid "weak links" or "weak corners" where a cell has incompatible interactions.

6) getWeakLinks() Now, the full treatment invovles not just strong chains, but the trasmission of parity from one chain to another through "weak links". A1 ---- A2 ---- A3. If these are all in a line -- same row, column, or block, but A1 and A3 are on two DIFFERENT chains, then we have a weak link. Weak links transmit the alternating parity of one chain to another if and only if the initiating point is TRUE. So if A1 is true, then both A2 and A3 are false.

7) Assign one for four types to each weak link: 0/0, 0/1, 1/0, or 1/1, depending upon the assigned parity of the nodes A1 and A3. (There are four possible link types between any two chains, since the assigned starting point for chain parity is arbitrary.)

8) addWeakCheck() The idea here is that you may have 10-20 chains. If chain 1 is linked to chain 2 through a 0/1 weak link, then they act as one LARGE strong chain in terms of any other weak connection. And if chain 2 is linked to chain 3 the same way, then, effectively, chain 1 is linked to chain 3. We we build a little table that identifies all "virtual" links.

The Medusa snakes are spreading. We are widening our sphere of influence -- now we assign "YES" to any 0-parity node on chain 1, that determines ALL of the nodes on all chains linked to it via a 0/1 or 0/0 weak link. Likewise, assigning "YES" to any 1-parity link on a chain assigns that to any other chain linked by a 1/0 or 1/1 type link.

9) checkWeakLinks() This simple function now takes care of almost all "X"-type and Y-type constraints.

10) We do the same with what I call "weak corners" -- weak nodes connected to two chains but not in a line -- not all three in the same row, column, or block, so transmission of parity is not possible from one chain to another, but deletiion of the node is possible.

In the context of http://www.research.att.com/~gsf/sudoku/

<quote>

There are three X cycle forms based on strong/weak sequence combinations within the cycle:

1. Odd strong edge sequences connected by one weak edge. Weak edge cells not participating in the cycle may be eliminated.

[These are removed in checkParity() as the weak nodes are found. ]

2. One even strong edge sequence and zero or more odd strong edge sequences connected by one weak edge. The end cells of the even strong sequence may be eliminated.

[Each "strong edge sequence" here is what I call a strong chain. "Zero" odd strong edges is taken care of by checkParity() -- this is just the same incompatibility as X1, but the node in question is on the chain. ]

3. One odd strong edge sequence connected by two weak edges. The middle cell of the weak sequence may be eliminated.

[This is what I'm calling a "weak corner."]

Y constraints are cycles composed of edges between cells with exactly two candidate values within a single row/col/box, where at least one of the candidate values is the same in both cells (strong edges.) Two of the Y cycle edges may meet at a cell that contains more than two candidate values, but has the same candidate as the other endpoints of the edges (two weak edges.)

[This is simply a set of strong chains mixed with weak links. I have simply folded it all together rather than isolate "X" from "Y". ]

</quote>

In short -- I guess we are looking at cycles, but strange as it may seem, we never actually identify them. We just look for parity errors. Interestingly enough, once these chains are in place, the setting of one single cell on one chain just might set them all on all the other chains as well. Almost a magic cell idea.

I don't fully understand the coloring language, but I would bet that the coloring logic is simply a way of following the logical connections made by strong chains connected by weak links/corners. At least to a first approximation.

Where this strategy fails, it seems (based on top95), is when there are very few long strong chains in a puzzle, though mabe many short ones. I'm not sure what the next step there is, but I'm confident that this Medusa chain strategy is very powerful. If a solution fails after this, then you really have to move on to a wholely different level, I think.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

dukuso · Posted: Tue Oct 18, 2005 5:02 am Post subject:

which of these techniques would you expect to be also useful in
larger sudokus (16*16...) or sudoku-variants i.e.
QCP (sudoku without boxes-constraint) ?

Bob Hanson · Posted: Mon Oct 24, 2005 6:01 am Post subject:

All these techniques apply to any Sudoku, I think. Strong chains are just strong chains, and weak links/corners are just that in any variety of Sudoku. Removing the box constraint simply removes an option for defining strong chains and their associated weak nodes. -- row, column, cell, instead of row, column, block, and cell. As for 16x16 - this is not a significant difference. Should be perfectly extendable.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

dukuso · Posted: Mon Oct 24, 2005 6:31 am Post subject:

Bob Hanson · Posted: Mon Oct 24, 2005 4:48 pm Post subject:

I have no clue as to speed. My point is just that it tremendously extends the X-/Y-constraints or "cycles" idea, thus allowing more solutions without guessing or backtracking. Someone else will have to code it for speed. I think Glenn Fowler might be looking into this.

The fact that it finds ALL strong chains and ALL associated weak nodes may slow it down some. Since it has to do some chain-chain cross-checking, and some of the top95 puzzles have upwards of 20 chains, this may be especially slow there.

But I was glad to see that by adding 3D weak nodes it improved to solving 54 of the top95 instead of 47 of them. (Glenn Fowler's sudoku(1) solves 43 of these, I think.)

The functions are all pretty straightforward: Find the chains, find the weak links and corners, map the chain connection, check for inconsistencies. For x-wing-type things, n-tuples, elimination, and such, it uses the same function, analyzeX(), just from different directions. So that is VERY efficient in a programming sense, and I would guess also in a performance sense, since all it is doing is binary ORs.

It may not be fast -- I don't know -- but it is quite robust and certainly takes care of ALL possible situations for which it relates to. And it's easily extendible, as my recent post relating to XYZ-wings notes.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Bob Hanson · Posted: Tue Nov 01, 2005 5:12 am Post subject:

For the record, Sudoku Assistant, now with Nick70's "reverse logical" analysis solves 90/95 top95 puzzles. See

http://www.stolaf.edu/people/hansonr/sudoku

The analysis is explained at

http://www.stolaf.edu/people/hansonr/sudoku/explain.htm

but basically amounts to a simple human-friendly process of asking "what are all the possible conditions under which A will be true?" and then looking for when two mutually exclusive conditions BOTH suggest A will be true. Then, in that case, A is proven true.

This was, indeed, the big step I was looking for. It seems hat the strategy is VERY powerful. Without it, Sudoku Assistant only solves 60/95. So that's a full 50% more attributable just to this one addition.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

bennys

You have some bug your solver is reporting that its not valid

Bob Hanson · Posted: Tue Nov 01, 2005 2:38 pm Post subject:

yup. OK. will look into that. Thanks.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Bob Hanson · Posted: Tue Nov 01, 2005 3:06 pm Post subject:

That's fixed. Thanks. The problem was in a piece of the weak+field analysis. It's not necessary anyway.

Oh my! It's better than that!

Sudoku Assistant solves all 95 of top95 !!!!!

you may have to clear your cache or reload

http://www.stolaf.edu/people/hansonr/sudoku/weak.js

where I commented out the "forcing corners" business.

Logic only! Just a more advanced version of subset elimination in terms of logical analysis. All 95 solve.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr