Fishy Cycles

gaby · Posted: Sat Aug 06, 2005 2:10 am Post subject: Still getting problems

Hi,

I've got a good implementation of Fishy Cycles in place now, but it's generating an interesting recommendation, that is ultimately incorrect. The caveats I have programmed for it, and features are:

- Edges cannot be reused as edges again in any given cycle
- One cell from each vertex forms the edge, and these cells cannot be used more than once in any given cycle
- Vertices are computed acceptably
- Edges are computed acceptably, with multiple edges arising from vertices
- Graphs seem to work, except for my example.

Here's the starting point:

MadOverlord · Posted: Sat Aug 06, 2005 3:05 am Post subject:

Well, first of all, your starting matrix has a typo in it:

gaby · Posted: Sat Aug 06, 2005 9:48 pm Post subject:

Sorry about the typos, I should have checked it a little more thoroughly before putting the code up... Smile

Also, I had disabled some forms of analysis so that I would have something for the fishy cycles to look for. When I enable number chains (what I call disjoint subsets) it finds the number chain 1,8 in row 1, and does as you suggest.

Having run some serious debug and optimisation on my code, I've found the problem. I found that edges were being generated when two vertices shared a cell in exactly the same location, where in effect this should not be an edge. Adding in this constraint greatly reduced the number of edges in the graph, and also prevented the problem I described in my last post.

On top of that, I created a function to narrow down the set of edges when a new vertex is added to the graph, just to make sure I'm only dealing with the minimal set of edges that I need to:

$edges = _fishy_edge_remove( $new_edge, $new_vertex, $edges )

You go along $new_edge to get to $new_vertex. $edges contains a list of vertex-to-vertex edges (va-vb)=(e1,e2...en). If $new_vertex == vb, then we remove the edge from the list. If any of the edges (e1,e2...en) == $new_vertex, then those edges are discarded as well. This ensures that we never revisit an edge, nor do we use a vertex as an edge later on in the cycle. We then recursively generate the list of possible cycles from the new list of edges.

Either way, this seems to have fixed the problem. My PHP code is not the most efficient, but ensuring that the path that a cycle takes never visits the same square twice, even for individual edges, has made it run nice and fast, solving the puzzle very quickly indeed Smile

_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

Lummox JR · Posted: Tue Sep 13, 2005 12:13 am Post subject:

I think I must be misunderstanding part of this algorithm. I have a board where fishy cycles is telling me to eliminate a choice I know is actually part of the solution; eliminating it results in an unsolvable board. Here's what I get with the digit 2:

MadOverlord · Posted: Tue Sep 13, 2005 1:28 am Post subject:

Lummox JR · Posted: Tue Sep 13, 2005 1:55 am Post subject:

This is the original puzzle:

gaby · Posted: Tue Sep 13, 2005 9:19 am Post subject:

I can see that you're using b1 as a vertex, and as two edges in that graph. My understanding was that b1 can only appear once in the entire graph, either as an edge or a vertex, not both, and not more than once. If you constrain it this way, what does your solver suggest?
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

MadOverlord · Posted: Tue Sep 13, 2005 1:10 pm Post subject:

Lummox JR · Posted: Tue Sep 13, 2005 9:51 pm Post subject:

Well, even constraining a house to only appear as a vertex or edge, the 3-cycle r1->c3->c6->r1 (edges are b1, r2, b2) would still seem to be valid. And indeed, the r1->c3 link with b1 as an edge could be sacrificed in favor of the 4-cycle.

I have no idea why this works out the way it does, and there must be some sort of exclusion I'm not seeing since others can get this algorithm to work. The only thing I'm seeing is that c3 and c6 link up in r2 even via the b1->r1->b2 connection, so that the same cells appear more than twice. This seems to be related to the rule that the same house can't be visited more than once, but it seems to me then that that exclusion is actually misstated. The correct rule then should not be that the house may not appear twice in the cycle, but rather that each vertex must not be part of more than 2 houses in the cycle. Counting repeated houses twice, this supercedes the other rule. In Doug's post on the exclusion it looks like this may have been the intent, but wasn't stated in that way. To formalize it:

For every simple closed cycle in a fishy cycle graph, each cell must be part of exactly one vertex and one edge.

This makes sense and, if correct, eliminates my confusion. It also implies directly that the same house cannot be used twice.

Interestingly I was looking back on the talk calling this a superset of swordfish, and I don't think that's entirely accurate. My own understanding of swordfish is that it's an extension of the X-wing technique to 3+ columns or rows, which means that it's basically a positional form of one of the subset rules (which is how my solver approaches it). While X-Wing can be considered a simple fishy cycle, not all potential swordfish can. Leastwise, a traditional swordfish with only 2 choices per row/column could be called a fishy cycle, but with more choices it has to be considered under the subset rule.

Lummox JR · Posted: Wed Sep 14, 2005 11:57 pm Post subject:

Brief addendum: I'm not so sure the repeat-house rule is even necessary. Doug posted this example, which by my new reckoning directly violates the above rule:

eclark · Posted: Wed Dec 28, 2005 1:32 am Post subject:

Sorry to bump an old thread but I am having trouble implementing fishy cycles. I am trying like a lot of people to make a solver that uses human methods to solve complex puzzles. Right now I am solving about 58% of all randomly generated sudoku's and 24 of the top 95.

I have tried to put the example code into java but for some reason I am never finding connecting links.

here is the code invloved:
Points are just holder classes that hold row and column
Vertexes have two points their type

0 = row
1 = column
2 = square

Edges have three vertexes and two points.

eclark · Posted: Wed Dec 28, 2005 6:56 am Post subject:

Well an update, I have gotten father. I was not setting the points correctly in edges the second one was never set as you can see. And I was supposed to test if the via and to were used not the from and to. The from will always be used... blah.

Anyway now I have another problem.... maybe someone will help me see what I am doing wrong. Thanks

Here is my current code:

eclark · Posted: Thu Dec 29, 2005 12:45 am Post subject:

Well I am a lot farther then I was but I need some help.. Big suprise I know....
I am runing the top 1011 through my solver and I have 6 that cause errors.

Here is one.
what is wrong with this?

eclark · Posted: Thu Dec 29, 2005 3:29 am Post subject:

YAY I have it done

eclark · Posted: Sat Jan 07, 2006 6:45 am Post subject:

Well after a lot of work here is my version of fishy cycles. If I forgot to include any functions just send me a message. Or if you have anything that betters my code.