The New Sudoku Players' Forum

by **Jeff** » Tue Dec 13, 2005 2:32 pm

Bob Hanson wrote:Glenn Fowler's page, that describes the "X-cycles" and "Y-cycles"...............

I have taken a look at Glenn Fowler's page where the "X-cycles" and "Y-cycles" are described. Could you explain the use of edges for these cycles?

I understand that the x-cycle is a combination chain with the same label throughout and elimination is made at the intersection of 2 weak edges. However, should the edges be in alternative strong and weak colours? How about when an inclusion is made at the intersection of 2 strong edges; is it still called an x-cycle? The x-cycle examples are listed below for easy reference.

I understand that the y-cycle is a pure bivalue chain (or commonly known as xy-chain) with all weak edges. As such, all edges should be shown in green. Could you shed some light on this? The y-cycle examples are listed below for easy reference.

What cycle do you call a pure bilocation chain with all strong edges that have various labels?
What cycle do you call a combination chain consisting of strong and weak edges that have various labels?

Thanks in anticipation

by **Bob Hanson** » Tue Dec 13, 2005 4:10 pm

Edges: Really the important ones are the red lines. They imply both "TRUE
implies FALSE" and, most importantly, "FALSE implies TRUE". That's why
they are referred to as "strong" edges. This includes only two kinds of
edges:

X: conjugate pairs -- only two possibilities for a candidate in a certain
row, column, or block

Y: two-valued cells.

Now, I recommend thinking of these edges as between MARKS, not
CELLS. Thus, from my perspective, a two-valued cell is ITSELF an edge.
To me, this makes good sense.

All the X-cycle and Y-cycle (and the combination of the two, 3D Medusa)
rules are based on the idea that a strong edge has the special property
that FALSE implies TRUE. This is the key. It lets us make the logical jump
from one strong "chain" to another.

In the example on the left, we have an X-cycle on 2. Starting around the
red lines, you can say

(r1c1)F-->T-->F-->T-->F-->T(r1c2)

OK, so with an "odd number of edges" we get a false at one end and a
true at the other, and it works backward, from the other end as well. So
no matter what is T and what is F, there's always a 2 in block 1 from this
chain. Any other 2 in block 1 can be eliminated.

On the right we see that not all the connections in the chain have to be
strong. We could have some "weak edges" anywhere we have "TRUE
implies FALSE".

So the above would have been just as true if we had had:

(r1c1)F-->T...F-->T...F-->T(r1c2)

where ... denotes a weak edge (a row, column, or block with more than two 2s in it).

Something like this is in the X-cycle on the right. The idea there is to start
with a TRUE and end up in the same row, column, or block with another
TRUE (even number of edges overall). Then all those strongly connected
TRUE marks can be eliminated.

OK, so with Y cycles the idea is that ALL of the connections are like this.
The "F-->T" occur in individual two-valued cells. So Glenn doesn't
show any red lines there. I would draw the red lines between the MARKS,
though, and the green lines from mark to mark so that it's still obvious
that we have the same basic rule.

On the bottom left we have:

(r2c4)7F-->1T...1F-->8T...8F-->7T(r7c9)

OK, so r7c4#7 can be eliminated.

It's the same thing.

The bottom right is tricky. We have:

(r9c6)1F-->4T...4F-->7T...7F-->8T...8F-->1T(r1c9)

and vice versa. So r9c9#1 can be eliminated.

My 3D Medusa idea at http://www.stolaf.edu/people/hansonr/sudoku
simply combines these two into one whole. And there really isn't any
need for cycles -- just explore the chains in any direction and look for
inconsistencies. This works well on paper as well as electronically.

Sometimes its fun to try to find the simplest cycle that "explains" the
chain connections, but that really isn't necessary, if you think about it.

I've also written something up on this at
http://www.stolaf.edu/people/hansonr/top95-analysis.htm,
in case you are interested in some more examples.

by **Jeff** » Tue Dec 13, 2005 7:47 pm

Thanks Bob for the detailed explanation.

I gather that the 3D Medusa technique can be used to identify all double implication chains. Could you demonstrate the extent of 3D Medusa by listing the candidates that can be eliminated from the following grid using the technique?

Code: Select all: *-----------------------------------------------------------------------------* | 56 56 2 | 38 9 348 | 1 348 7 | | 179 3 8 | 6 2457 12 | 245 59 259 | | 4 179 17 | 123578 2578 1238 | 2568 35689 235689 | |-------------------------+-------------------------+-------------------------| | 12367 12678 1347 | 39 2678 5 | 2468 16789 12689 | | 2567 245678 9 | 278 1 268 | 3 45678 2568 | | 123567 125678 1357 | 4 2678 39 | 2568 156789 125689 | |-------------------------+-------------------------+-------------------------| | 123579 12579 1357 | 12589 2568 12689 | 68 368 4 | | 135 15 1345 | 158 4568 7 | 9 2 368 | | 8 249 6 | 29 3 249 | 7 15 15 | *-----------------------------------------------------------------------------*

by **Bob Hanson** » Tue Dec 13, 2005 9:01 pm

Yes, right, the idea is to determines ALL implication chains.

Easiest thing to do is clip that into
http://www.stolaf.edu/people/hansonr/sudoku
yourself. Just click on "Number block input", paste the table in there,
and press "puzzle".

It wouldn't be able to show all the implications, because it generally
doesn't continue through if it finds an inconsistency. For example, when I
do that and then press "Step" I get:

Strong Chains: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Cross checking
60 cells left to solve; 21 clues; 483 tidbits of information
[snapshot]
Checking block ranges
Checking for subset elimination
Checking for grids
Checking strong chains
17 strong chains
Checking for weak links
44 weak links
139 weak corners
r9c2 ISN'T 9: weak corner eliminated by both 2(b) and 2(B)--4(D)

Chain 2: r1c6#4(b) r1c8#4(B) r2c5#4(B) r2c7#4(b) r5c2#4(B) r9c2#4(b) r4c3#4(b) r8c3#4(B) r4c7#4(B) r5c8#4(b) r8c5#4(b) r9c6#4(B)
Chain 4: r2c1#9(d) r7c1#9(D) r3c2#9(D)

The fact that it went on to the weak link check tells me that the
chains are all OK -- no end-nd problems. But it isn't going to keep
going and check all. I guess you could adjust the code to do that.....

You can check the "chain table" yourself. It looks like this in this case:

Code: Select all: 16 strong chains are labeled A-P, with alternating parity shown using lowercase. |---c1---|---c2---|---c3--||---c4---|---c5--|---c6--||---c7--|---c8---|---c9--- ---------------------------------------------------------------------------------- r1 | 56 | 56 | 2 || 358 | 9 | 348 || 1 | 34568 | 7 | aA | bB | || | | c || | C | ---+--------+--------+-------||--------+-------+-------||-------+--------+-------- r2 | 1579 | 3 | 8 || 6 | 2457 | 124 || 245 | 459 | 259 | e fd | | || | j F | E || l | | ---+--------+--------+-------||--------+-------+-------||-------+--------+-------- r3 | 4 | 15679 | 157 || 123578 | 2578 | 1238 || 2568 | 35689 | 235689 | | D | || | | || | | n =============================||========================||========================= r4 | 12367 | 124678 | 1347 || 23789 | 2678 | 5 || 2468 | 146789 | 12689 | | | g || h k | | || L | | ---+--------+--------+-------||--------+-------+-------||-------+--------+-------- r5 | 2567 | 245678 | 9 || 278 | 1 | 268 || 3 | 45678 | 2568 | | i | || | | || | I | ---+--------+--------+-------||--------+-------+-------||-------+--------+-------- r6 | 123567 | 125678 | 1357 || 4 | 2678 | 23689 || 2568 | 156789 | 125689 | | | || | | H K || | | =============================||========================||========================= r7 | 123579 | 12579 | 1357 || 12589 | 2568 | 12689 || 568 | 13568 | 4 | D | | || | | || | n | ---+--------+--------+-------||--------+-------+-------||-------+--------+-------- r8 | 135 | 145 | 1345 || 158 | 4568 | 7 || 9 | 2 | 13568 | | | G || | J m | || | | N M ---+--------+--------+-------||--------+-------+-------||-------+--------+-------- r9 | 8 | 12459 | 6 || 1259 | 3 | 1249 || 7 | 15 | 15 | | J | || | | j || | oO | pP ---------------------------------------------------------------------------------- Chain Implication Table 1(a)--> 2(B) row 1 1(A)--> 2(b) row 1 2(b)--> 1(A) row 1 2(B)--> 1(a) row 1 3(c)--> 10(J) block 2 3(C)--> 9(i) col 8 12(L) block 3 4(d)--> 5(E) r2c1 6(F) r2c1 5(e)--> 4(D) r2c1 6(F) r2c1 6(f)--> 4(D) r2c1 5(E) r2c1 6(F)--> 10(J) r2c5 7(g)--> 9(I) block 4 12(l) row 4 7(G)--> 10(j) row 8 8(h)--> 11(K) r4c4 8(H)--> 11(k) r6c6 9(i)--> 7(G) block 4 10(j) col 2 9(I)--> 3(c) col 8 12(l) block 6 10(j)--> 3(C) block 2 6(f) r2c5 12(L) row 2 10(J)--> 7(g) row 8 9(I) col 2 13(M) r8c5 11(k)--> 8(H) r4c4 11(K)--> 8(h) r6c6 12(l)--> 3(c) block 3 10(J) row 2 12(L)--> 7(G) row 4 9(i) block 6 13(m)--> 10(j) r8c5 13(M)--> 14(n) r8c9 14(N)--> 13(m) r8c9 15(o)--> 16(P) row 9 15(O)--> 16(p) row 9 16(p)--> 15(O) row 9 16(P)--> 15(o) row 9

OK, so there are a lot of implications here.

HINT: Use the "load puzzle" link from this pop-up window each time you
want to reset the configuration to this one. Or you can also click the
"snapshot" link that shows up with the information.

If you start disabling things, you might be able to get some different
answers:

** checking +almost-locked sets (Y):

Cross checking
60 cells left to solve; 21 clues; 483 tidbits of information
[snapshot]
Checking block ranges
Checking for subset elimination
59 almost-locked sets (Y)
r8c3 ISN'T 1: weakly linked to two almost-locked sets already weakly linked by 7: r3c3 and r7c3 r8c1 r8c2

** checking X-cycles only:

Strong Chains: 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Cross checking
60 cells left to solve; 21 clues; 483 tidbits of information
[snapshot]
Checking block ranges
Checking for subset elimination
Checking for grids
Checking strong chains
14 strong chains
Checking for weak links
4 weak links
16 weak corners
r5c1 ISN'T 7: weak corner eliminated by both 6(f) and 6(F)--7(G)

Chain 6: r2c1#7(f) r2c5#7(F)
Chain 7: r3c4#7(g) r5c4#7(G)

(note, these are differerent chains than above)

**Edges only:

(This is just a demo mode that only considers the shortest chains and
misses some due to that.)

Strong Chains: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Cross checking
60 cells left to solve; 21 clues; 483 tidbits of information
[snapshot]
Checking block ranges
Checking for subset elimination
Checking for grids
Checking strong chains
25 strong chains
Checking for weak links
62 weak links
135 weak corners
r1c8 ISN'T 3: weak corner eliminated by both 3(C) and 3(c)--23(w)

Chain 1: r1c1#5(a) r1c1#6(A)
Chain 2: r1c2#5(b) r1c2#6(B)
Chain 3: r1c6#4(c) r1c8#4(C)
Chain 7: r2c5#4(g) r2c7#4(G)
Chain 8: r5c2#4(h) r9c2#4(H)
Chain 9: r2c1#7(i) r2c5#7(I)
Chain 10: r2c8#5(j) r2c8#9(J)
Chain 12: r4c3#4(l) r8c3#4(L)
Chain 13: r4c4#3(m) r4c4#9(M)
Chain 15: r4c7#4(o) r5c8#4(O)
Chain 20: r8c5#4(t) r9c6#4(T)
Chain 21: r8c5#6(u) r8c9#6(U)
Chain 23: r3c9#3(w) r8c9#3(W)
Chain 25: r9c8#5(y) r9c9#5(Y)

(again, a different chain definition)

So there are some, anyway.

by **Bob Hanson** » Wed Dec 14, 2005 5:52 am

I've updated Sudoku Assistant to be able to show ALL implications. Now it reports for this configuration:

Strong Chains: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Cross checking
60 cells left to solve; 21 clues; 483 tidbits of information
[snapshot]
Checking block ranges
Checking for subset elimination
59 almost-locked sets (Y)
r8c3 ISN'T 1: weakly linked to two almost-locked sets already weakly linked by 7: r3c3 and r7c3 r8c1 r8c2
Checking for grids
54 almost-locked sets (X)
Checking strong chains
17 strong chains
Checking for weak links
44 weak links
139 weak corners
r9c2 ISN'T 9: weak corner eliminated by both 2(b) and 2(B)--4(D)
r4c3 ISN'T 1: weak corner eliminated by both 2(b) and 2(B)--8(h)
r4c7 ISN'T 8: weak corner eliminated by both 2(B) and 2(b)--12(L)
r1c8 ISN'T 3: weak corner eliminated by both 2(B) and 2(b)--16(p)
r9c2 ISN'T 9: weak corner eliminated by both 4(D) and 4(d)--2(b)
r7c1 ISN'T 3: weak corner eliminated by both 4(D) and 4(d)--16(p)
r5c1 ISN'T 7: weak corner eliminated by both 6(f) and 6(F)--10(J)
r4c3 ISN'T 1: weak corner eliminated by both 8(h) and 8(H)--2(b)
r5c1 ISN'T 7: weak corner eliminated by both 10(J) and 10(j)--6(f)
r5c9 ISN'T 6: weak corner eliminated by both 11(k) and 11(K)--14(N)
r4c7 ISN'T 8: weak corner eliminated by both 12(L) and 12(l)--2(B)
r5c9 ISN'T 6: weak corner eliminated by both 14(N) and 14(n)--11(k)
r1c8 ISN'T 3: weak corner eliminated by both 16(p) and 16(P)--2(B)
r7c1 ISN'T 3: weak corner eliminated by both 16(p) and 16(P)--4(D)

Chain 1: r1c1#5(a) r1c1#6(A) r1c2#5(A) r1c2#6(a)
Chain 2: r1c6#4(b) r1c8#4(B) r2c5#4(B) r2c7#4(b) r5c2#4(B) r9c2#4(b) r4c3#4(b) r8c3#4(B) r4c7#4(B) r5c8#4(b) r8c5#4(b) r9c6#4(B)
Chain 4: r2c1#9(d) r7c1#9(D) r3c2#9(D)
Chain 6: r2c1#7(f) r2c5#7(F)
Chain 7: r2c8#5(g) r2c8#9(G)
Chain 8: r3c3#1(h) r3c3#7(H)
Chain 9: r4c4#3(i) r4c4#9(I) r6c6#3(I) r6c6#9(i)
Chain 10: r3c4#7(j) r5c4#7(J)
Chain 11: r5c6#6(k) r7c6#6(K)
Chain 12: r7c7#6(l) r7c7#8(L)
Chain 14: r8c5#6(n) r8c9#6(N)
Chain 15: r9c8#1(o) r9c9#1(O) r9c8#5(O) r9c9#5(o)
Chain 16: r3c9#3(p) r8c9#3(P) r7c8#3(p)

by **Carcul** » Wed Dec 14, 2005 11:05 am

Hi Bob Hanson and hi Jeff.

I have read with interest some threads about X-Cycles, Y-Cycles, and 3D-Medusa. I have some questions:

1. Is 3D-Medusa equivalent to the nice loops (combination chains) that can he identified with the bilocation-bivalue plot?

2. In the "chain table" above, how can we identify implication chains with the aid of the letters?

3. The use of letters is equivalent to draw a bilocation-bivalue plot?

4. For the grid posted by Jeff, I have identified, until now, 13 chains that allow a few more eliminations to be made than the ones posted above by Bob Hanson. Are more eliminations implied by the chains 1-16 posted above?

Regards, Carcul

by **ronk** » Wed Dec 14, 2005 12:58 pm

Carcul wrote:1. Is 3D-Medusa equivalent to the nice loops (combination chains) that can he identified with the bilocation-bivalue plot?

If you select the radio button to limit Medusa to strong chains, I believe eliminations would be identical to that of a fully-utilized bilocation-bivalue plot.

2. In the "chain table" above, how can we identify implication chains with the aid of the letters?

The letters indicate true-false parity. If you "enter the chain" at a lower case letter assuming candidate x is true/false, you can just scan the chain ... without counting links ... and know that at another lower case letter, the candidate is true/false there also. Therefore, it's an aid in knowing where (weak) linking strong chains together is even possible.

3. The use of letters is equivalent to draw a bilocation-bivalue plot?

If my viewpoint above is correct, clearly not.

4. For the grid posted by Jeff, I have identified, until now, 13 chains that allow a few more eliminations to be made than the ones posted above by Bob Hanson.

Would you please provide a link to those?

Are more eliminations implied by the chains 1-16 posted above?

I believe Medusa'a eliminations are based on a set of "static chains", IOW, the eliminations are identified and executed in a block manner. Only after *all* the eliminations are identified for any given grid (and during a Medusa step), are *any* strong chains actually modified due to eliminations. Then on the next step, this new (or modified) set of chains is used to identify another block of eliminations.

So I think the direct answer to your question is "no", but additional eliminations may then be made in a subsequent step.

I know I'm "sticking my neck out" by answering for Jeff and/or Bob, but doing so helps clarify my understanding ... and perhaps an outlook other than an author's is helpful to others.

Regards, Ron

by **Carcul** » Wed Dec 14, 2005 1:27 pm

Hi Ronk.

Thanks for your explanation, but there are still some things that I don't understand.

ronk wrote:Therefore, it's an aid in knowing where (weak) linking strong chains together is even possible.

Could you please explain this a little further and, if possible, provide a concrete example?

Thanks in advance, Carcul

by **Jeff** » Wed Dec 14, 2005 3:31 pm

ronk wrote:
Carcul wrote:1. Is 3D-Medusa equivalent to the nice loops (combination chains) that can he identified with the bilocation-bivalue plot?

If you select the radio button to limit Medusa to strong chains, I believe eliminations would be identical to that of a fully-utilized bilocation-bivalue plot.

I have proven here that advanced colouring is equivalent to bilocation/bivalue simple nice loops, ie. exactly the same deductions are resulted from the 2 techniques. Somehow, I am feeling that 3D-Medusa has yet to cascade to the next 'rounds' where some more deductions are possible. That's why I asked Bob to perform 3D-Medusa on this grid for comparison.

ronk wrote:
Carcul wrote:2. In the "chain table" above, how can we identify implication chains with the aid of the letters?

The letters indicate true-false parity. If you "enter the chain" at a lower case letter assuming candidate x is true/false, you can just scan the chain ... without counting links ... and know that at another lower case letter, the candidate is true/false there also. Therefore, it's an aid in knowing where (weak) linking strong chains together is even possible.

With the true-false parities, look for contradictions in intersections which are equivalent to the discontinuities of the bilocation/bivalue simple nice loops. My understanding with weak linking strong chain is that it is just another name for xy-chain.

ronk wrote:
Carcul wrote:3. The use of letters is equivalent to draw a bilocation-bivalue plot?
If my viewpoint above is correct, clearly not.

The concept is difference, but the propagation means are the same. The labelled links in bilocation/bivalue plot are replaced by letters with upper case and lower case representing conjugate relationships for bilocation nodes and bivalue nodes.

ronk wrote:
Carcul wrote:4. For the grid posted by Jeff, I have identified, until now, 13 chains that allow a few more eliminations to be made than the ones posted above by Bob Hanson.

Would you please provide a link to those?

I have identified 12 chains and a total of 17 candidate eliminations. That's the limit of advanced colouring as well as bilocation/bilocation simple nice loops. Refer here.

ronk wrote:
Carcul wrote:Are more eliminations implied by the chains 1-16 posted above?

I believe Medusa'a eliminations are based on a set of "static chains", IOW, the eliminations are identified and executed in a block manner. Only after *all* the eliminations are identified for any given grid (and during a Medusa step), are *any* strong chains actually modified due to eliminations. Then on the next step, this new (or modified) set of chains is used to identify another block of eliminations.
So I think the direct answer to your question is "no", but additional eliminations may then be made in a subsequent step.

I also got a feeling that 3D-Medusa can be cascaded further to get the remaining deductions made by the bilocation/bivalue plot.

ronk wrote:I know I'm "sticking my neck out" by answering for Jeff and/or Bob, but doing so helps clarify my understanding ... and perhaps an outlook other than an author's is helpful to others.

Every contribution helps. Please feel free to discuss.

by **Jeff** » Wed Dec 14, 2005 4:04 pm

Bob Hanson wrote:r9c2 ISN'T 9: weak corner eliminated by both 2(b) and 2(B)--4(D)
r4c3 ISN'T 1: weak corner eliminated by both 2(b) and 2(B)--8(h)
r4c7 ISN'T 8: weak corner eliminated by both 2(B) and 2(b)--12(L)
r1c8 ISN'T 3: weak corner eliminated by both 2(B) and 2(b)--16(p)
r9c2 ISN'T 9: weak corner eliminated by both 4(D) and 4(d)--2(b)
r7c1 ISN'T 3: weak corner eliminated by both 4(D) and 4(d)--16(p)
r5c1 ISN'T 7: weak corner eliminated by both 6(f) and 6(F)--10(J)
r4c3 ISN'T 1: weak corner eliminated by both 8(h) and 8(H)--2(b)
r5c1 ISN'T 7: weak corner eliminated by both 10(J) and 10(j)--6(f)
r5c9 ISN'T 6: weak corner eliminated by both 11(k) and 11(K)--14(N)
r4c7 ISN'T 8: weak corner eliminated by both 12(L) and 12(l)--2(B)
r5c9 ISN'T 6: weak corner eliminated by both 14(N) and 14(n)--11(k)
r1c8 ISN'T 3: weak corner eliminated by both 16(p) and 16(P)--2(B)
r7c1 ISN'T 3: weak corner eliminated by both 16(p) and 16(P)--4(D)

Thanks Bob for your time and effort. Is the list above a complete list of eliminations made by 3D-Medusa? It shows 7 eliminations only as opposed to 12 made by bilocation/bivalue plot or advanced colouring. Have I missed something. Anyway, after all double implication chains are identified, the reduced grid should be:

Code: Select all: *-----------------------------------------------------------------------------* | 56 56 2 | 38 9 34 | 1 48 7 | | 179 3 8 | 6 2457 12 | 245 59 259 | | 4 179 17 | 12578 2578 128 | 2568 35689 23568 | |-------------------------+-------------------------+-------------------------| | 1236 12678 47 | 39 2678 5 | 246 16789 12689 | | 256 245678 9 | 278 1 268 | 3 45678 258 | | 123567 125678 1357 | 4 2678 39 | 2568 156789 125689 | |-------------------------+-------------------------+-------------------------| | 12579 12579 1357 | 125 2568 1268 | 68 368 4 | | 135 15 1345 | 158 4568 7 | 9 2 368 | | 8 24 6 | 29 3 49 | 7 15 15 | *-----------------------------------------------------------------------------*

by **ronk** » Wed Dec 14, 2005 4:58 pm

Carcul wrote:
ronk wrote:Therefore, it's an aid in knowing where (weak) linking strong chains together is even possible.

Could you please explain this a little further and, if possible, provide a concrete example?

Consider the following strong links from Bob's most recent post.

Chain 2: r1c6#4(b) r1c8#4(B) r2c5#4(B) r2c7#4(b) r5c2#4(B) r9c2#4(b) r4c3#4(b) r8c3#4(B) r4c7#4(B) r5c8#4(b) r8c5#4(b) r9c6#4(B)
Chain 4: r2c1#9(d) r7c1#9(D) r3c2#9(D)
Chain 6: r2c1#7(f) r2c5#7(F)

r2c5, r1c1, and r7c1 are all poly-valued cells ... r2c5={2457}, r1c1={179}, r7c1={123579} ... and as such are weak links (edges). While r2c5=4 (true) => r2c5<>7 (false) is correct, the reverse ... r2c5<>4 (false) => r2c5=7 (true) ... is not correct. IOW for a weak link, we must have a true for one value of a poly-valued location in order to propagate a false to any other value at that location.

In addition, there are strong links between r2c5 and r1c1 and between r1c1 and r7c1. Therefore, we have the implication chain ...

r2c5=4 => r2c5<>7 => r1c1=7 => r1c1<>9 => r7c1=9 => r7c1<>3

The above is just an example, and not necessarily part of an actual chain that leads to an elimination.

AFAIK herein lies the difference between bilocation/bivalue approach and the Medusa approach of using both strong and weak links. The former requires bivalued locations ... which are strong links ... while the latter does not. And at least theoretically, use of weak links should yield a few more eliminations. (There may also be a corollary for locations.)

by **Carcul** » Wed Dec 14, 2005 5:39 pm

Ronk,

Thanks for your comprehensive explanation.
I have now solved the grid posted above by Jeff. I have used a total of 26 chains: 20 simple nice loops, 3 loops having an extended disjoint subset link (as defined by Rubylips), 2 weak nice loops, and 1 strong nice loop. Does anyone have come also to a solution? I would like to compare different solutions.

Carcul

by **Bob Hanson** » Wed Dec 14, 2005 6:03 pm

I think I agree with pretty much everything anyone said about Medusa here. Basically I think it's advanced coloring or maybe xy-chains, or something like that.

Jeff wrote:Thanks Bob for your time and effort. Is the list above a complete list of
eliminations made by 3D-Medusa? It shows 7 eliminations only as
opposed to 12 made by bilocation/bivalue plot or advanced colouring. Have I missed something.

Ah, I think I misunderstood what you were asking for. Generally what the
Sudoku Assistant does is go through a sequence of stages and drops out
to start again if any eliminations are found in one of those stages. These
include:

singlet checking
range checking (row-locked cells)
subset elimination (hidden pairs, etc.)
grid checking (X-Wings, etc.)
chain analysis (Medusa)

The Medusa stuff is not until the last stage.

If any eliminations are found in any of these stages, then at the end of the
stage, it starts over with another "step".

I implemented the "All" option to not register the eliminations -- just
announce them -- so that all of the possible eliminations from the current
configuration could be found.

But if you instead use the "Solve" option, then you get the configuration
you refer to. Does the bivalue-bilocation plot get all 12 of these in one
go? -- one "step"? That would be interesting.

By the way, adding the new "almost-locked" option solves this puzzle
directly. See this link.

Bob

by **ronk** » Wed Dec 14, 2005 6:15 pm

Jeff wrote:It shows 7 eliminations only ...
Bob Hanson wrote:r9c2 ISN'T 9: weak corner eliminated by both 2(b) and 2(B)--4(D)
........
r9c2 ISN'T 9: weak corner eliminated by both 4(D) and 4(d)--2(b)
r7c1 ISN'T 3: weak corner eliminated by both 4(D) and 4(d)--16(p)
........
r7c1 ISN'T 3: weak corner eliminated by both 16(p) and 16(P)--4(D)

I hadn't noticed the duplications. Apparently, some eliminations may be made by following any one of several chains. IMO it would nicer if the Medusa only logged one of them. [edit: A revisit of the site shows Bob has already done exactly that.]

Is the list above a complete list of eliminations made by 3D-Medusa? It shows 7 eliminations only as opposed to 12 made by bilocation/bivalue plot or advanced colouring. Have I missed something.

Yes, those are the eliminations of Step 3 only. Subsequent steps produce further eliminations.

Anyway, after all double implication chains are identified, the reduced grid should be: [edit: see prior post]

Enabling weak links [edit: but apparently without Almost Locked Sets], Medusa gets stuck at exactly the same candidate state ...

Code: Select all: *-----------------------------------------------------------------------------* | 56 56 2 | 38 9 34 | 1 48 7 | | 179 3 8 | 6 2457 12 | 245 59 259 | | 4 179 17 | 12578 2578 128 | 2568 35689 23568 | |--------------------------+------------------------+-------------------------| | 1236 12678 47 | 39 2678 5 | 246 16789 12689 | | 256 245678 9 | 278 1 268 | 3 45678 258 | | 123567 125678 1357 | 4 2678 39 | 2568 156789 125689 | |--------------------------+------------------------+-------------------------| | 12579 12579 1357 | 125 2568 1268 | 68 368 4 | | 135 15 1345 | 158 4568 7 | 9 2 368 | | 8 24 6 | 29 3 49 | 7 15 15 | *-----------------------------------------------------------------------------*

(Bob Hanson, I edited out Medusa's clutter, but left the right justification.)

I had thought that "only strong links" would produce the same result as the bilocation/bivalue techniques, but obviously weak links are required too. I haven't a clue why.

by **ronk** » Wed Dec 14, 2005 6:31 pm

Bob Hanson wrote:By the way, adding the new "almost-locked" option solves this puzzle
directly. See this link

Meaning "without" hypothesis and disproof, errr ... trial and error. Bravo!!

The New Sudoku Players' Forum

x-cycle, y-cycle & 3D-Medusa

x-cycle, y-cycle & 3D-Medusa