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   

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

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Mon Oct 17, 2005 8:59 pm    Post subject: Medusa works -- alternative to X/Y cycles for 9x9 Reply with quote

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
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Mon Oct 17, 2005 9:52 pm    Post subject: Reply with quote

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?
Back to top
View user's profile Send private message Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Mon Oct 17, 2005 10:01 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Mon Oct 17, 2005 10:25 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Tue Oct 18, 2005 12:14 am    Post subject: Reply with quote

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
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Tue Oct 18, 2005 12:27 am    Post subject: Reply with quote

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.
Code:
. . .|. . .|. . .
. . .|a . .|. A .
. . .|. . A|. . a
-----------------
. . .|. . .|. . .
. . .|. . .|* a *
. . .|. . .|. . .
-----------------
b . .|. . *|* . -
B . .|A . .|* . .
. . .|. . c|C . .

There are more complicated deductions possible in multicoloring, such as: A!B and b!C, therefore A!C (! means "mutually exclude each other")
Thus, there can be a relation between 2 chains that do not cross each others paths.

About XY-Wing. I understand that you do cover the XY-Wing. However, my interest lies in the fact that 2 cells are turned into a conjugate pair by such an XY-wing. This conjugate pair can then possibly be linked to other conjugate pairs in the Z-Value-plane. Does Medusa stop when it finds the XY-wing, or will it try to "crawl" further to see whether this "fresh" conjugate pair can be exploited a little more?

Define "better" (be careful in discussions with a scientist, Ruud!)
I'm not concerned with speed, but with solving capability. Compared to Glenn Fowler's program, yours is better than his because it solves more of the top95.

Define "traditional"
In the short time Sudoku programs have been around, there has grown some consensis about the techniques that can be used to tackle these puzzles. Many programs use the same set of techniques, though they may be implemented differently in each program. A traditional technique would be something that many Sudoku programmers have implemented in their program.

As Lummox stated: your M strategy sounds a lot like supercoloring, which is soon to become "traditional", if not already. A way to prove that Medusa is something completely new would be comparing it to a program that uses supercoloring. If it solves more or a different set of benchmark puzzles (like the top95), it would be a nice addition to the toolkit.

For me, useful feedback is a mandatory requirement for such a method. I have implemented 4 different algorithms in my program that can solve a Sudoku in a flash, including Knuth's dancing links algorithm, but they can only tell what the solution is, but not (in plain English) how it was found. A Sudoku helper (or Assistent) must be able to give hints and tips to the user.

Ruud.
Back to top
View user's profile Send private message Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Tue Oct 18, 2005 3:16 am    Post subject: Reply with quote

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
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Tue Oct 18, 2005 5:02 am    Post subject: Reply with quote

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) ?
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Mon Oct 24, 2005 6:01 am    Post subject: Reply with quote

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
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Mon Oct 24, 2005 6:31 am    Post subject: Reply with quote

Bob Hanson wrote:
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.


yes, but can we expect it be faster than simpler,competing techniques ?
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Mon Oct 24, 2005 4:48 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Tue Nov 01, 2005 5:12 am    Post subject: Reply with quote

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
Back to top
View user's profile Send private message Send e-mail Visit poster's website
bennys

Joined: 30 Sep 2005
Posts: 6
:

Items
PostPosted: Tue Nov 01, 2005 5:43 am    Post subject: Your solver have problem with this sudoku Reply with quote

You have some bug your solver is reporting that its not valid
Code:
+-------+-------+-------+
| . . 2 | . 9 . | 1 . 7 |
| . 3 8 | 6 . . | . . . |
| 4 . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . 5 | . . . |
| . . 9 | . 1 . | 3 . . |
| . . . | 4 . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . 4 |
| . . . | . . 7 | 9 2 . |
| 8 . 6 | . 3 . | 7 . . |
+-------+-------+-------+
Back to top
View user's profile Send private message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Tue Nov 01, 2005 2:38 pm    Post subject: Reply with quote

yup. OK. will look into that. Thanks.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Tue Nov 01, 2005 3:06 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
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