Fishy Cycles

Doug · Posted: Sun May 29, 2005 11:27 am Post subject: Fishy Cycles

Edit: Following nick89's suggestion, I got the graphs to look pretty close to what I intended. Thanks nick89! Edit2: I have cleaned up more of the displays and some typos.

Below is a generalization of swordfish and x-wing. This result is an

algorithm which should run fast, at least for small puzzles, and

should give more information on some difficult puzzles. It extends

the set of logic rules discussed here.

Some nomenclature. (For the moment, until I get up to speed on the

standard terminology.) I will refer to the individual 81 squares as

"cells". I will refer to the 9x9 (Edit: I meant 3x3 here, thanks MadOverlord!) blocks as "blocks". I will refer to

individual rows, columns, or blocks as "houses". I will name the

houses by their column number, row number, or block number

(numbering blocks 1 through 9 in the usual way, left to right, top

to bottom.) For example, b3 is block 3, the third 9x9 (bah! I mean 3x3!) cell block on

the top right, and r2 refers to row 2, counting from top to bottom.

b3, r2, etc are refered to as the "names" of the houses.

The algorithm works by constructing for each of the numbers n (from

1-9) a multigraph "graph(n)" in which the vertices and edges are

labeled with certain house names. From graph(n), all possibilities

for the number n will be able to be removed from the houses which

label the edges of cycles in the graph. The construcion of graph(n)

is as follows:

The vertex set is the set of names of houses which contain n as a

possibility in exactly two of their cells.

An edge is drawn between two vertices if and only if there is a

house different from the houses of the two vertex sets which

contains exactly one possibility for n from each of the two vertex

houses.

The theorem (obvious extension of swordfish argument) states that

all other possibilities for n in the edge houses which are part of cycles in

the graph may be removed. ("Other" here meaning except for the pairs

that define the vertex

houses.) Here are two examples to illustrate the idea.

In the examples lower and upper case versions of the same letter in

the alphabet denote the unique pair of locations of possibilities

for the number n in a particular house.

Example 1

a**|**c|***
***|***|***
*A*|b**|***
---------------
***|B**|***
***|**C|***
***|***|***
---------------
***|***|***
***|***|***
***|***|***

The conclusion in this case is that the houses: r3,b5,r1, and b2 can

be cleared of n (excepting the locations a,A,b,B,c,C, of course).

The proof is as follows. Each location possibility x can be assigned

the value T or F according to whether or not n is in that location.

Now we chase the implications of the rules of Sudoku. Logical implications are denoted by ->.

Case 1. a=T -> c=F -> C=T -> B=F -> b=T -> A=F (consistent with

a=T).

Case 2. a=F -> A=T -> b=F -> B=T -> C=F -> c=T (consistent with

a=F).

Note that in either case, in the houses r3, b5, r1, and b2, there

will be locations for n with opposite values. (For example in Case

2, in b2, b=F and c=T; in Case 1, these values are reversed.). Thus,

in any case, there must be a T, and by the uniqueness of n in each

house, all other locations in those houses may have n eliminated

from them.

Point on the logic above. The implications from T to F follow from

the fact that in any house n can occupy only one cell. The

implications from F to T follow from the fact that the two locations

in question are always in a house with exactly two possible

locations for the number n.

The translation of this example into the graph language is as

follows:

Since a and A are the unique possibilities for the number n in the

house b1, there is a vertex labeled b1. Similarly there are vertices

labeled c4 and c6 (there are exactly two places that n can occur in

column 4 as well as two places n can occur in column 6).

Since the possible locations A and b both lie in (row) r3, (and

neither a nor B lie in that house), there is an edge in the graph

between the vertices b1 and c4. Similarly the edge b5 connects the

vertices c4 and c6. The edge r1 connects the vertex b1 to the vertex

c6. Finally, the house b2 also connects c4 to c6.

Accordingly, the graph has the following appearance:

nick89 · Posted: Mon May 30, 2005 12:00 pm Post subject:

Using the code tags in your post will force a fixed width font for your diagrams.

IE:
Your 1st digram-

MadOverlord

I've been writing a Macintosh Sudoku solver for my kids and for giggles.

The Fishy Cycles algorithm looks really interesting, so I took a stab at it.

However, the recommendations it generates on complex puzzles are incorrect, so either it's not correct, or my implementation is bad (much more likely).

AFAICT it is properly computing the vertexes (easy).

However, when I compute the edges and cycles, I get a lot of weird cycles, such as:

1) cycles that repeatedly pass through the same house via different vertexes (ie: going from r1 to r2 through b2, then r2 to c5 through b2, and so on.

2) cycles that contain vertexes in the edges (an edge that is also a vertex).

Even after restricting things so that these conditions cannot occur (ie: a cycle with unique vertexes and edges, where no edge can be a vertex), I still get results that would lead me to incorrectly set squares. So clearly I'm not understanding things properly.

So questions:

1) can a vertex be an edge in a cycle that doesn't contain it as a vertex? Or are vertexes not permitted to even be considered as edges?

2) What restrictions on cycles are there? I would appreciate a more specific definition of what you consider a cycle to be.

Much obliged for any help you can provide.
R

Doug · Posted: Wed Jun 01, 2005 5:32 am Post subject: Fishy Cycles

cycles that repeatedly pass through the same house via different vertexes (ie: going from r1 to r2 through b2, then r2 to c5 through b2, and so on.

The example you gave and others like it need to be excluded. One
cannot allow a 3-cycle with the same house on all edges.

Example:

abc
A**
*B*
**C

gives a 3-cycle with common edge r1. In this situation, one cannot conclude that r1 can be cleared.

I believe the fix is to restrict the edges to using the cells shared by the vertices only one time in the cycle. (Each of the two cells forming the pair of cells defining the vertex must be part of the two different edges connecting the vertex to the cycle. This is required for the algorithm and was not spelled out in my first post.

Let me know if that fixes the problems!

In answer to 1) I allow vertices to be edges of other cycles.

Now when an edge occurs that is also a vertex, that edge gives no elimination information since one cannot eliminate the locations which define the vertices. (There are only two possibilities in that house already!) However, it might be needed for forming a larger cycle and eliminating elsewhere.

2) I was thinking of simple cycles which contain vertices only once, forming a "loop".
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

rubylips · Posted: Wed Jun 01, 2005 11:11 am Post subject:

Doug - this is very interesting. (And thanks for your patience - I notice that the posting has been edited ten times!) First, I'd like to point out that Swordfish, as implemented at http://act365.com/sudoku, isn't limited to rows - though several postings have suggested that it is. Here's a copy of a definition I posted to the Puzzles: plain text / Puzzle 5 (from Swordfish compendium) topic.

MadOverlord · Posted: Wed Jun 01, 2005 1:30 pm Post subject: Re: Fishy Cycles

Doug,

I'll start coding up your changes ASAP.

One question: Each vertex house has the two special squares (ie: aA in your examples). Consider that two vertexes might share one or both special squares (say, aA and bB where a=b, or consider the intersection between a row and a block, where the two special squares are in the block). Is it legal to form an edge between these two vertexes.

Thinking about it, the only case that really applies is a row and column sharing a single special square; the question is, can the block they intersect in form an edge between them?

Doug · Posted: Thu Jun 02, 2005 12:17 am Post subject: Fishy Cycles

MadOverlord--

I believe that is ok. Here is an example and the logic works:

***|***|***
*B*|***|***
**a|A**|***
----------------
*bA|***|***
***|***|***
***|***|***

Here the graph has the following structure:

Vertex set: {r3,c3,c2}

Edge set: {Edge {r3,c3} labeled with b1, Edge {c3,c2} labeled with b4, Edge {c3,c2} labeled with r4, Edge {c3,c2} labeled with b1, Edge {c2,r3} labeled with b1}

Notice the parallel edges between c3 and c2. (Three edges in this case!)

In this instance, anyway, it is legitimate to clear houses b1, b4 and r4.

The proof is as follows:

A=F (in r3) -> a=T -> B=F -> b=T -> A=F (in c3) (consistant with a=T and A=F)

A=T (in r3) -> a=F -> A=T (in c3) -> b=F -> B=T (consistant with a=F and A=T).

In either case there is a True in the houses b1,b4, and r4, and so these houses may be cleared.

The point here is that the A in r3 is actually irrelevent. It can be ignored. The triple parallel edges between c3 and c2 give all that is needed for elimination. The extra A in r3 just means that we know the two cells in r3 that have n as a possibility. The A certainly doesn't interfere with the triple edges between c2 and c3 which comprises three different 2-cycles between vertices c2 and c3, depending which pair of edges are chosen to make a cycle, eg, edges b1 and b4 making a 2-cycle, or edges b1 and r4 making a 2-cycle, or edges b4 and r4 making a 2-cycle. Each of these cycles gives elimination information and at least two of them need to be considered to milk all the elimination information. The A in r3 doesn't do any harm. Of course the computer will find it as well as the 3-cycle which has two edges labeled with b1, but the b1 here is redundant. In some cases, of course, the 3-cycles will give new information. "Swordfish" cases, for instance.

Anyway, this degenerate case is ok. Maybe there are some that are not, but I can't think of any.

Remark. If the b were one cell lower, one could not clear r4, but otherwise the logic still would work and b1 and b4 could still be cleared.

Hope that helps.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

MadOverlord · Posted: Thu Jun 02, 2005 12:23 am Post subject: I implemented Fishy Cycles.

Hey everyone, I got the implementation of Fishy Cycles working. It turns out to be quite straight-forward once you add in the extra constraints that Doug clarified last night.

Here is the code that implements it in RealBasic. I took a quick stab at commenting it so it should be easy to port to Javascript or whatever other language you are using.

I have tested it against the Swordfish and X-Wings samples and it handles them easily.

I'll be releasing my Macintosh solve-assistant in the next few days and will post a link when it's ready; I want to clean some things up first.

BTW, anyone got a link to a place where I can download lots of puzzles in a machine-readable format?

Note: edited to make a minor change suggested by Doug.

Doug · Posted: Thu Jun 02, 2005 12:46 am Post subject: Fishy Cycles

Looking through your documentation I noticed:

"// however, we are only interested in cycles that
// have at least three edges in them "

I am not a coder, so maybe I misunderstand, but cycles with two edges are legitimate and give information. See:

http://www.setbb.com/phpbb/viewtopic.php?t=37&start=0&postdays=0&postorder=asc&highlight=&mforum=sudoku

Did I miss something?
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

MadOverlord · Posted: Thu Jun 02, 2005 12:52 am Post subject: Re: Fishy Cycles

Doug · Posted: Thu Jun 02, 2005 1:09 am Post subject: Fishy Cycles

MadOverlord-

Here are a few links to places with puzzles to test against:

Follow the links to the technique descriptions for X-wing and Swordfish here and after the descriptions are some sample puzzles:

http://www.simes.clara.co.uk/programs/sudokutechniques.htm

Also, there are challenge puzzles here:

http://www.sudokusolver.co.uk/challenge.html
and
http://www.sudokusolver.co.uk/challenge2.html

I have another post on this board

http://www.setbb.com/phpbb/viewtopic.php?t=40&mforum=sudoku

which gives an algorithm which resolves the first challenge puzzle above. (When I say resolves, I mean when used with established techniques, say those listed on the first link above along with extensions found here:
http://www.sudokusolver.co.uk/solvemethods.html
and
http://www.sudokusolver.co.uk/codeit.html

I don't know if my second algorithm (linked above), maybe combined with Fishy Cycles, can get the second one, though. I also don't know if Fishy Cycles combined with standard techniques can get the first challenge problem. I kind of doubt it, but I haven't tried it by hand.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

MadOverlord · Posted: Thu Jun 02, 2005 2:39 am Post subject: Re: Fishy Cycles

Doug · Posted: Thu Jun 02, 2005 3:42 am Post subject: Fishy Cycles

If I'm reading you correctly, your method "Comprehensive Locked Sets" is "Expanding Method D" described at:

http://www.sudokusolver.co.uk/codeit.html

Also, the "Removing Candidates II" method you mention is a special case of Fishy Cycles, it arises from 2-cycles. in fact! This is discussed here:

http://www.setbb.com/phpbb/viewtopic.php?t=37&mforum=sudoku

So it is indeed subsumed!

I added a note to my post on the Limited Implication Trees heuristic explaining how I believe Nishio is subsumed by it as well.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

Doug · Posted: Thu Jun 02, 2005 4:29 am Post subject: Fishy Cycles

MadOverlord--

Looking at the thread:

http://www.setbb.com/phpbb/viewtopic.php?t=12&postdays=0&postorder=asc&start=15&mforum=sudoku

It looks like your "Remote Locked Pairs" algorithm is the same as AMcK's coloring algorithm.

Edit: Oops! Not quite. His definition of "conjugate pair" is a bit different it seems from your "locked pairs". You might want to have a look at his algorithm, well example, anyway.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

MadOverlord · Posted: Thu Jun 02, 2005 5:13 am Post subject: Re: Fishy Cycles