Fishy Cycles

Doug · Posted: Thu Jun 02, 2005 5:33 am Post subject: Fishy Cycles

MadOverlord-

I have looked quickly through all of AMcK's posts for an explanation. I didn't find one. But looking at his examples I think I can deduce the algorithm easily. (I need to copy down a complete example and work through it to figure it out completely.) What I have been able to figure out so far is that conjugate pairs are pairs of cells in a house that are the only ones that can contain a given digit. So if one cell contains the digit, then the other cannot and the digit must be in one of them.

Now then, his colors represent variables with potential truth values for the presence of the given digit in a cell. In each application of the algorithm he consideres only a single digit. He then finds all pairs in the graph using as few variables (colors) as possible, by first going through rows, then columns, and finally boxes.

At the row stage, all conjugate pairs get the different variables (colors).

At the column stage, some new colors may be required as well as old colors may be re-used.

Finally at the box stage, re-colorings are made and a matrix results with colors in certain cells. Finally, the digit which is being used is eliminated from other cells.

I haven't worked out the details of his recoloring rule, but I have an idea about the elimination rule. It is something like: "When a row and a column each have two variables with different values, then the cell at their intersection can have that color removed from it." (At least that seems to me to be approximately correct. I am missing part of the rule for elimination for sure, but it's certainly along those lines.)

Later I'll work out all the details of his algorithm and look for extensions of it.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

MadOverlord · Posted: Thu Jun 02, 2005 12:48 pm Post subject: Re: Fishy Cycles

Doug · Posted: Thu Jun 02, 2005 1:05 pm Post subject: Fishy Cycles

Trebor--

Perhaps I'm coufused.

My understanding:

To you a locked pair would be possibility sets {1,2} and {1,2} in a row with no other 1's or 2's in the row.

To him a conjugate pair would be {1,2} and {1,3,7} in a row with no other 1's in the row.

The difference being that his concept is about a single value having two exclusive possible locations in a house. In locked pairs, there are two values with the same two exclusive locations in a house.

OK. Really time for bed.

Must not check sudoku forum any more before pillow. MUST NOT>

Wizardry! Really?

Doug <-- Thinks of spiral tracks.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

MadOverlord · Posted: Thu Jun 02, 2005 3:14 pm Post subject:

No, it's me that is confused. You're right.

Doug · Posted: Fri Jun 03, 2005 5:35 am Post subject: Fishy Cycles

I believe AMcK's algorithm is likely subsumed by Fishy Cycles, but I haven't worked out a proof of this yet.

Edit: Thinking about it a bit more, it seems quite possible that they, in fact, give equivalent information.

Edit2: I'm quite sure now that they are equivalent! The coloring rules applied to the matrix will give conjugate labels to two cells in the edge houses in Fishy Cycles. Thus it will eliminate the other entries for n in those houses, that is, from the edges in the graph. Also, the coloring algorithm is, I think, easier to code and apply. I think its preferable to Fishy Cycles. It's possible my reasoning is missing something on their equivalence, but I don't see it.

Anyway, here is his coloring algorithm. I will be using ordered pairs to represent the colors. The colors should be thought of as logical variables which can take the values T or F.

Definition. A conjugate pair is a pair of cells in a house which are the only possible locations in the permissions matrix for a particular value.

The algorithm works on a particular value at a time, say n.

1) All conjugate pairs in the rows are found. These are labeled in the following way. Let m=1. The first cell is assigned an ordered pair (m,0) and the second is given the label (m,1). They must of necessity have different truth values. (I call these conjugate labels.) m is then incremented when new pairs are found on new rows.

2) Now conjugate pairs are searched for in columns. Each conjugate pair found in a column is colored according to:

a. If neither cell in the pair already has a label, they are given next label pair not used.

b. If one of the cells is already labeled, but the other is not, then the unlabeled cell gets the conjugate label to the first one.

c. If both cells already have labels, say (p,a) and (q,b), then we re-assign the labels on the larger row in accordance with the forced conjugacy of the column pair. All cells labeled with those labels (of the larger row) in the graph are also adjusted. Example: Say in a column we find a conjugate pair with lables (3,1) and (5,0). Then all cells in the graph with the labels (5,0) are changed to (3,0) and all cells with the label (5,1) are given the label (3,1).

3) Conjugate pairs are searched for in the blocks. Again the labels are adjusted, if necessary, to preserve conjugate consistancy.

4) Finally, all houses which initially did not have conjugate pairs are searched. If two cells now have conjugate labels, then all non-labeled cells may have n removed from their permissions matrix.

Hope I haven't missed anything.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

MadOverlord · Posted: Fri Jun 03, 2005 1:24 pm Post subject: Re: Fishy Cycles

Doug · Posted: Fri Jun 03, 2005 1:31 pm Post subject: Fishy Cycles

Yes, I agree that FC is easier by hand. And I'm still not sure the algorithms are equivalent. If coloring is easy to code, then running a bunch of examples using only those two algorithms and comparing the eliminations should give better confidence.

Good morning!
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

Gennadog

I've been looking into implimenting this in my own program and I've come across a situation that I'm not sure how to make progress.

The original grid is:

Doug · Posted: Sat Jun 18, 2005 12:45 pm Post subject:

The vertices are rows, columns, or blocks containing exactly two possibilities (containing two 9's in your case). In your example only possible vertices are: c4, c9, r6, r9, b2, b6, and b9.

Unfortunately, the conditions for the edges do not give any cycles here. See previous posts for definitions and examples.

BTW I believe that the AMcK's coloring algorithm described above is equivalent to Fishy Cycles. It is also easier to code, I believe. It is described in some detail in posts above.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

jiffle · Posted: Tue Jun 21, 2005 4:50 pm Post subject: Re: Fishy Cycles

MadOverlord · Posted: Tue Jun 21, 2005 7:02 pm Post subject: Re: Fishy Cycles

In a simple locked set the possibilities have to be the same, ie:

12 12 is a locked pair

123 123 123 is a locked triple

But in a comprehensive locked set things can be more complicated, ie:

12 23 13 is a locked triple.

A locked set of size N is N squares who have, between them, a total of N possibilities.

gaby · Posted: Fri Jul 29, 2005 10:12 pm Post subject:

Nice. Well, I've finally got round to properly thinking about fishy cycles and reading the thread through. It's not nearly as complicated as I thought it would be once I though about edges and vertices a bit better. Here's my take on fishy cycles, I'd appreciate thoughts on it:

1. For each number 1 to 9, n, do:

1.1. Create our vertex set {v} by searching each row, column
and block where n only appears twice as a candidate. Each
vertex will be a pair of coordinates, one pair for each cell
that holds n.

1.2. For every possible pair of vertices in {v}, {v1} and {v2},
check for a row, column or block that holds one number from
{v1} and one number from {v2}, but does not contain all the
numbers in both vertices.

Example: There are clearly four numbers that we need to check
the positions for; {v1:1}, {v1:2}, {v2:1} and {v2:2}. So we
should check for a row/column/block that contains any of
these sets:

a. {v1:1} and {v2:1}
b. {v1:1} and {v2:2}
c. {v1:2} and {v2:1}
d. {v1:2} and {v2:2}

However, if a row/col/block contains all four numbers in the
pair of vertices (sets a and d, or b and c) then we cannot use this
row/col/block in our graph.

If we find a row/column/block that fits this criteria, then
we can draw an edge between the two vertices, and we name the
edge by the row, column or block that we found.

Keep going until we've tried every possible combination of vertices.

1.3. Look through the graph for all cycles {c}. A cycle is a
path that you would take from vertex to vertex, along the
edges of the graph, finishing up where you started from, and
only going through each vertex once. There may be quite a few
of these cycles, you'll need to thoroughly check the graph.

1.4. For each cycle in {c}, do:

1.4.1. Being that each edge in our cycle represents a given
row, column or block, we can now remove the number n from
all the other cells in that row/col/block that aren't
in either {v1} or {v2} (from each end of the edge).

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

droid42 · Posted: Fri Jul 29, 2005 11:22 pm Post subject:

Re: Fishy algorithm...

The explanation seems awfully involved for what can easily be implemented with simple bitmaps (representing the "possibles" in a sector) and trivial bitwise operations.

My own solver has a single 200-line method that unifies the logic for detecting X-Wing, Swordfish, Swordfish4/5/6, solitary n-tuples, hidden n-tuples etc. The logic to detect them all is surprisingly similar.

Or am I missing something? (honest question, not a sarcastic one)...

Ian.

P.S. This is my first post on here after lurking for a while so "Hi" Smile

gaby · Posted: Sat Jul 30, 2005 2:05 pm Post subject:

I'd very much like to see that code. Would it be possible to send me a copy?
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

AMcK · Posted: Sun Jul 31, 2005 1:54 pm Post subject:

The new supercolouring algorithm seems to solve this cleanly - without any need for a final execution of the standard 3 rules.
Here's the staring point