NEWS:
 Fishy Cycles Goto page 1, 2, 3  Next
Author Message
 Doug Joined: 28 May 2005 Posts: 42 :
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:
 Code: r3           b1-------------c4            \        _____/|           r1\    b5/     /              \   /      /b2                \|      /                c6____/

[Edit: This graph has three vertices: vertices b1 and c6 are connected by edge r1, vertices b1 and c4 are connected by edge r3, and finally vertices c4 and c6 are connected by edges b5 and b2.]

The basic principle is that once graph(n) is constructed in the

above way, the labels of all edges, which are part of cycles in the

graph, constitute a set of houses for which n may be eliminated

(excepting vertex defining locations).

Example 2

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

The vertex set is: {c3, r5, b2, b3}. The edge set for this case

is then (we denote edges of a multigraph (as usual) by labeled

unordered pairs.):

{{c3,r5} with label b4, {r5,b2} with label c5, {b2,b3} with label

r1, {c3,b3} with label r3}.

In this case there is no multiple edge.

Accordingly, with the exceptions of the possibilities for n in the

locations a,A,b,B,c,C,d, and D, n can not be a possibility in houses

b2,c5, r1, and r3 (excepting vertex defining possibilities).

A more detailed explanation of the first edge in this example: a and

A occur in c3. b and B occur in R5. These pairs are unique in these

houses (by assumption). Now A and b occur in b4. Niether a nor B

occur in this house. Thus b4 forms an edge between c3 and r5.

The graph in this example is:
 Code: b4           c3------r5            |       |          r3|       |c5            |       |           c9------b2               r1

[Edit: The graph here is a square: The vertices are c3, r5, b2, and c9. The label of the edge between c3 and r5 is b4, the label of the edge between r5 and b2 is c5, the label of the edge between b2 and c9 is r1.]

The algorithm "Fishy Cycle" that arises from this is rather easy to

describe, and I think program.

-----------------------Algorithm "Fishy Cycle"--------------------------

For n ranging from 1 to 9 do:

1) Create the vertex set by searching through the 27 houses for

those with exactly two possibilities for n.

2) For each pair of vertices, check if there is a house containing

exactly one possibility from each pair. (For each pair of vertices,

there are four possibilities to check: For example, in the first

example above, when considering the pair of vertices b1 and c4, one

needs to check and see if there are houses containing the four

combinations a and b, a and B, A and b, as well as A and B. (This

is how multiple edges can arise in the graph.) Note that if a house

contains ,say a and b, then an edge is not formed if it also

contains either A or B.

3) With the graph constructed, one uses standard algorithms to find

all cycles in the graph. (Given the sizes of the graphs likely to

occur here, this will be very fast, as with the rest of this

algorithm.)

4) From the houses labeling the edges of cycles one now removes

possibilities for n which are not elements of the pairs which define

the vertices in the cycle under consideration.

Next n

The name "Fishy cycle" comes from swordfish, jellyfist, etc that

have been discussed here. Cycle from the fact that cycles in graphs

is the basis for the algorithm.

------------------------------------------

Remarks.

Swordfish, for example will only eliminate candidates for n which

are in a set of rows. This algorithm generalizes it, and will

eliminate candidates that are in rows, columns, as well as blocks

for each n.

Both x-wings and swordfish and the extensions that I've seen discussed here are special cases.

The algorithm should take almost no time typically as in most Sudoku

pubbles I've worked through, there are few vertices in the sense of the

algorithm above.

The algorithm can be done by hand.

I am not a programmer, but I would be delighted if anyone is

interersted in implementing this algorithm. I would be happy to try

out the results and look forward to more exploration with Sudoku. I

think the problem of finding computer solutions that are human

comprehensible to these puzzles is quite fun. Backtracking is so not

amusing by hand. :/

I only found out about Sudoku two days ago from a news website! This

forum seems to have a really fun spirit! Nice to meet everyone! =)

Please forgive me and don't hesitate to point out my mistakes etc.

No offense will be taken.

On that note, I have no skill programming, so this algorithm hasn't

been fire tested. Perhaps there is some glaring fault with what I

written above. If so, please forgive me for wasting your time. If this is the

case, most likely, there are missing hypothesis for certain situations

where this can be applied or something to that effect.

Peace,

PS My appologies, I can't seem to make the graphs come out right. Bah!

Hopefully the vertex and edge descriptions will sufice.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

Last edited by Doug on Thu Jun 02, 2005 4:08 am; edited 12 times in total
 nick89 Joined: 26 May 2005 Posts: 2 :
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:
 Code: r3 b1-------------c4 \ _____// r1\ b5/ / \ / /b2 \| / c6____/

 Code: b4 c3------r5 | | r3| |c5 | | c9------b2 r1
 MadOverlord Joined: 01 Jun 2005 Posts: 80 : Location: Wilmington, NC, USA
 Posted: Wed Jun 01, 2005 3:21 am    Post subject: Hmmm... Found a counterexample or more likely, don't suss it 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 Joined: 28 May 2005 Posts: 42 :
 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/bistrosavageLast edited by Doug on Wed Jun 01, 2005 12:19 pm; edited 1 time in total
 rubylips Joined: 07 Apr 2005 Posts: 62 : Location: London
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.

 Quote: Here's an attempt at a more precise definition of a Swordfish: A sector is the generic term for a row, column or box. A unit-length string comprises two cells within a single sector that are the only possible candidate positions for some given value within that sector. Two strings are connected if they share a common-cell and have been defined using the same value. Of course, connected strings will have to occur across different sector types - e.g., one string in a column could connect to another in a box. An n-leg string comprises n connected unit-length stings. Some logical observations: Provided that a string has an odd number of legs, exactly one of its end cells must contain the given value. When we find two strings, each with an odd number of legs, such that their end points lie on the same row (or column), we know that exactly one of the two end-points on each row (or column) must contain the given value. This allows us to eliminate the given value as a candidate for the remaining cells in each row (or column). More definitions: When the two strings are of unit length, the pattern is called an X-Wings. When one or more of the strings has length greater than one, the pattern is known as a Swordfish.

However, since Swordfish doesn't consider cyclic patterns as elegantly as your algorithm, I'll look to update my implementation for the next release. Should anyone be interested in how I locate Swordfish patterns, download the source from http://sf.net/projects/sudoku and look in the file LeastCandidatesHybrid.java, particularly the function LeastCandidatesHybrid.swordfish(StringBuffer). I believe that the code addresses some of the issues discussed by MadOverlord.
 MadOverlord Joined: 01 Jun 2005 Posts: 80 : Location: Wilmington, NC, USA
 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 Joined: 28 May 2005 Posts: 42 :
 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 Joined: 01 Jun 2005 Posts: 80 : Location: Wilmington, NC, USA
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.

Last edited by MadOverlord on Thu Jun 02, 2005 12:53 am; edited 1 time in total
 Doug Joined: 28 May 2005 Posts: 42 :
 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 Joined: 01 Jun 2005 Posts: 80 : Location: Wilmington, NC, USA
Posted: Thu Jun 02, 2005 12:52 am    Post subject: Re: Fishy Cycles

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

Ok, then I misunderstood. It's easy enough to fix. taptaptap.. okay, doesn't seem to break the code. I'll update my posting with the corrected code.

BTW, I think in your original posting, where you say 9X9 you mean 3X3... (grin)
 Doug Joined: 28 May 2005 Posts: 42 :
 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 Joined: 01 Jun 2005 Posts: 80 : Location: Wilmington, NC, USA
Posted: Thu Jun 02, 2005 2:39 am    Post subject: Re: Fishy Cycles

 Doug wrote: 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.

I'd already found those challenge problems. Fishy Cycles (plus other standard techniques) doesn't resolve them, but I'll try implementing your implication trees technique next.

Looking at the simes.clara.co.uk stuff, it looks like I'm implementing everything except perhaps his "reducing, part 2" concept (http://www.simes.clara.co.uk/programs/sudokutechnique4.htm).

However, this may be subsumed by other heuristics I'm using.

So far I've implemented:

"It can't be anything else"
"It's the only square in a group that can have that value"

"Simple locked set"

If a set of N squares in a group all have the same set of N possibilities, then we can eliminate those possibilities from the other squares in the group.

Example: if there are 3 squares with possibilities 1, 2 and 3, then one must be 1, one 2 and the other 3; so none of the other 6 squares in the group can be 1, 2 or 3.

A set of two squares with the same two possibilities is referred to as a "locked pair"; a set of three squares with the same three possibilities would be a "locked triplet", and so on.

"Possibility Reduction"

Remove extra possibilities on groups of squares that share the same subset of unique possibilities.

Example: if there are two squares with possibilities 12 and 123, and no other squares have possibilities 1 or 2, then the second square cannot be a 3 (because one square must be a 1, and the other must be the 2).

"Intersection Removal"

Rows and columns intersect with blocks.

If the squares in a row that have a given possibility only intersect a single block, then that possibility must occur in the 3-square intersection of the row and the block, and can be removed from the constraints of the other 6 squares in the block.

Example: consider the first row and the top-left block. If the possibility 1 only appears in the first 3 squares of the row (and is not a possible solution for the other 6 squares), then it must be in those first 3 squares, and therefore cannot be in the other 6 squares of the top-left block.

The same removal can be done with columns vs. blocks, blocks vs. rows, and blocks vs. columns.

"Remote Locked Pairs"

Okay, this is a tough one.

Consider two squares A and B in a row, column or block that have the same two possibilities; these form a "locked pair", and if you find out what A is, you'll know what B is.

Now consider two locked pairs B and C in an intersecting row, column or block. Now A and C form a "complimentary pair"; if you know A, you know C must be same.

Finally, consider two locked pairs C and D in yet another intersecting row, column or block. Now A and D form a "remote locked pair"; they will be in different rows, columns and blocks.

If you can find A and D, they will form two corners of a box, and you can eliminate their possibilities from the squares at the other two corners of the box.

This can be extended further; if you can find locked pairs DE and EF, you have found a remote pair AF, and so on.

"Comprehensive Locked Set"

For each row, column and block, look for a set of N squares that have exactly N possible solutions. Then those solutions must be in the N squares, and can be removed from the other squares of the group.

Since there are many possible sets of N squares, this one is computationally intensive.

This test is a more general version of Simple Locked Set.

and of course,

"Fishy Cycles"

This one I'm not going to even attempt to explain, as it involves enough graph theory to give you a nosebleed.

Any basics that I've missed?
 Doug Joined: 28 May 2005 Posts: 42 :
 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 Joined: 28 May 2005 Posts: 42 :
 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 Joined: 01 Jun 2005 Posts: 80 : Location: Wilmington, NC, USA
Posted: Thu Jun 02, 2005 5:13 am    Post subject: Re: Fishy Cycles

 Doug wrote: His definition of "conjugate pair" is a bit different it seems from your "locked pairs"

I looked in the thread and also did a search but couldn't find an explanation of the algorithm. Can you point my tired eyes to it?

In case I didn't mention it, I learned about remote locked pairs from

http://www.scanraid.com/remotepairs.htm
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMTGoto page 1, 2, 3  Next Page 1 of 3

 Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback
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