The New Sudoku Players' Forum

by **Jeff** » Tue Sep 27, 2005 12:32 pm

kwdos wrote:.....There will however also be regions of the incorrectly set Sudoku within which multiple solutions are possible and where, as a result, both candidates in any cell with two possible values are simultaneously right and wrong (i.e. they will be right in one solution and wrong in another solution). Now the consequences of following xy-chains don't seem quite so clear to me and I just wonder whether there could ever be situations where multiple forcing chains exist in this region of the Sudoku whereby one or more chain might resolve into just one of the solutions
- presumably another chain could then resolve into the other solution(s).

It may be that one could never get forcing chains which resolve within a non-uniquely valued part of any incorrectly set Sudoku - I am just not sure about this - though clearly, if resolvable forcing chains cannot exist within such regions, then there would be no problem.....

If a grid has 2 solutions, an xy-chain will not give one of the solutions. The chain will be a non-repetitive one and there will be no conclusion on the placement of the nodes within the chain. I let you to think about this. Let me know if you still have any problems.

by **tso** » Tue Sep 27, 2005 4:49 pm

Jeff is exactly correct. We understand your proposition exactly, but it cannot have the results you suggest.

Suppose a puzzle with a 1000 solutions has the digit digit '1' in r1c1 in every possible solution but has the digit '2' in r1c2 only 999 times. It will be IMPOSSIBLE to construct a forcing chain -- or any other type of logical step -- that will place a digit in r1c2. It WILL be possible for a logical step to allow a placement of '1' in r1c1. There is no conflict.

A normal Sudoku has two types of cells -- those that are initially filled and those that are to be filled by the solver.

A multi-solution Sudoku has a THIRD type of cell -- the AMBIGUOUS cell that CANNOT be filled by the solver by logical means, that can ONLY be narrowed down to a choice of several options. It will not be obvious which cells are ambiguous and which are sovable -- but which are which is set in stone at the outset. No amount of clever logical finageling will allow the solver to decide one of the ambiguous cells -- conversely, if the sovler DOES prove the contents of a cell, that cell was NOT ambiguous.

A puzzle with exactly two solutions can be considered as two separate puzzles. At the point where you fill in an unfillable cell with one digit or another, you are choosing to solve one puzzle or the other. Until then, it is Schrodinger's Sudoku, neither dead nor alive. After this bifurcation, then and only then can you build forcing chains -- or x-wings, or naked pairs -- to fill in the no-longer-ambiguous cells.

If what you suggest did happen, and the forcing chains resolved to one specific placement in a cell -- that placement WOULD be correct in ALL cases. It would NOT be ambiguous and in fact, if you could then fill in the rest of the puzzle, you would in fact have a valid, unique soution puzzle.

You are describing an irresistable force meeting an immovable object. It cannot logically exist.

Actually, the situation you are describing is NOT a mutli-solution puzzle, but a puzzle with NO solutions, one that is internally inconsistant. In this case, YES! it is possible -- likely -- actually mandatory -- that there will be local logical tactics that will lead to contraditory placements, be they forcing chains or any other.

Additionally, you are giving some special significance to forcing chains to somehow differenciate them from other logical means where none exists. They are only different by degree. Even [12][12][123] could be described as a forcing chain instead of a naked pair.

by **Lummox JR** » Wed Sep 28, 2005 1:45 am

Heh. Schrodinger's Sudoku has got to be one of the most novel turns of phrase I've heard all year. What you just said basically spells out something I'd been thinking but couldn't put into words: A multi-solution grid has ambiguity built into the initial conditions.

And the conclusion about forcing chains is truly correct. If a logical method can narrow down a cell at all, it's because of the clues already provided. Either those clues lead to a cell/value common to all solutions, or they lead to an inconsistency that existed (but was not immediately evident) in the original grid.

Regarding hand-setting puzzles, kwdos, I'd highly recommend using a program like Sudoku Susser to test the validity of the result. It can tell you immediately if there's a problem with the clue placement leading to ambiguous sets or insoluble puzzles. Other tools online can also verify this for you.

by **kwdos** » Wed Sep 28, 2005 4:32 pm

Thanks all for comments (esp to Tso for spending so much time and trouble helping clarify the issue). Seems convincing but I guess I will have to get more experience with forcing chains before I am completely convinced!

With respect to Lummox's comment about checking for uniqueness of solution - I have written my own software to do this in any case, but in tweaking Sudokus my software uses much quicker algorithms in generating new ones : any interesting ones I then check with my single-solution software. It is however of course helpful if the quicker algorithms (including forcing chains are fully sound under all conditions - which certainly looks to be the case based on this topic!)

by **Lummox JR** » Wed Sep 28, 2005 11:52 pm

I suspect that a method I just started using is, for a program, faster than finding forcing chains. For lack of a better name I've been calling this multicoloring, though my research on types of coloring suggests that multicoloring is actually something else. I don't know if anyone has used this same method, but it basically encompasses forcing chains. I posted about it here, where I'm awaiting some information on whether there's already a name for it or not.

This method works just like coloring but extends the principle of finding conjugates to individual cells, not just houses. You then have to apply full transitivity, e.g. if a->b and b->c then a->b,c, and so on. This will often reveal that one of the colors cannot be valid, or that one is valid, or that some are equivalent. Once you've distilled this down, just like in regular coloring you can look for intersections between conjugate colors. Those intersections can occur either between houses for the same digit, or between a house/digit and a cell.

by **Jeff** » Thu Sep 29, 2005 5:35 am

Good stuff, Lummox JR. Actually, the term 'multicolouring' has been used in Angus' solver for a technique, slightly more complicated than 'solved by colour', which cover conjugate chains including a case of turbot fish. For easy reference, I am calling your technique 'advanced colouring' if you don't mind.

Take a look at here and here. The colouring technique mentioned in these threads resembles the 'advanced colouring' you have described. Could you shed some light on the correctness of the following cases:

Double implication forcing chain is a subset of advanced colouring.
Advanced colouring is a subset of double implication forcing chain.
Advanced colouring is equivalent to double implication forcing chain.

Thanks in anticiplation.

by **Lummox JR** » Fri Sep 30, 2005 3:07 am

Yes, I think the technique I've been using is just like what Nick was doing in that second link. I'd actually seen that thread before but couldn't make heads or tails of it until this clicked for me. And I very much like his concept in the first link of using only an exclusion matrix with the rule e(x,y) + e(Y,z) -> e(x,z).

To be honest I'm not too familiar with the concept of double-implication forcing chains, unless by that you mean the sort that forms a graph which shares 2 edges labeled with the same digit. This is the kind I've used sparingly myself and studied in use in Trebor's Sudoku Susser. If this is the sort you mean, then I'm absolutely convinced it's a subset of advanced coloring. Consider this puzzle:

Code: Select all: 4 1 .|. 3 .|. . . 2 . .|. 7 9|. 6 . . . .|4 . 5|. . . ----------------- 8 . .|. . .|. 4 . 3 9 .|. 4 .|. . . . . 4|5 . .|. . 8 ----------------- . 2 .|. . .|5 . . . . .|9 6 3|. . 1 . . 9|. . 7|8 . .

Eventually you'll reach a point where singles, intersections, and subsets fail, but a forcing chain can be found. That forcing chain works on the following 2-candidate cells, which I will illustrate here:

Code: Select all: . . . | . . . | . . . . . a5A8 | b1B8 . . | c1C4 . . . . . | . . . | . . . --------------------------------------------------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . --------------------------------------------------- . . . | . . . | . . . . . f7F8 | . . . | d2D4 e2E7 . . . . | . . . | . . .

The following colors can be found to exclude each other: A-B, A-F, b-c, C-D, d-e, E-f.

That leads to these implications:
A->b,f; b->C; B->a; c->B; C->d; d->E; D->c; e->D; E->F; f->e; F->a

Now follow that to a second round:
A->b,C,e,f; b->C,d; B->a; c->a,B; C->d,E; d->E,F; D->B,c; e->c,D; E->a,F; f->D,e; F->a

On the third round you'll immediately find A->b,c,C,d,D,e,E,f. Because it has c and C, or for that matter d and D or e and E, it must be false.

Now if you take a and A out of the equation and just consider the other conjugates, you'll find that on the third round, b->F and f->B. This is equivalent to saying b and f interact and cannot both be true. Therefore, either B or F or both are true, and cell (3,2) still can't be an 8.

I should take a moment aside and actually mention at this point that my algorithm as presently implemented is not making that sort of deduction, but if implemented to perfection it certainly can. The trick would be extending this to recognize that at least one of B or F is true, and eliminate accordingly; currently it can only do that with conjugates. If however this used Nick's exclusion matrix technique, then all you'd have to do is look for places that are "touched" by two colors (i.e., the way B and F intersect at (3,2)=8) and eliminate if those colors' conjugates exclude each other. You can do the same with the implication matrix method I'm using, but with less ease.

Advanced coloring must therefore be a superset, because it can make the same deductions as forcing chains, but it can make others much better. Usually it will find an entire color to eliminate, and that alone will usually crack the puzzle.

by **Jeff** » Fri Sep 30, 2005 10:17 pm

Lummox JR wrote:.......Consider this puzzle:
Code: Select all
4 1 .|. 3 .|. . . 2 . .|. 7 9|. 6 . . . .|4 . 5|. . . ----------------- 8 . .|. . .|. 4 . 3 9 .|. 4 .|. . . . . 4|5 . .|. . 8 ----------------- . 2 .|. . .|5 . . . . .|9 6 3|. . 1 . . 9|. . 7|8 . .

Eventually you'll reach a point where singles, intersections, and subsets fail, but a forcing chain can be found. That forcing chain works on the following 2-candidate cells, which I will illustrate here:
Code: Select all
. . . | . . . | . . . . . a5A8 | b1B8 . . | c1C4 . . . . . | . . . | . . . --------------------------------------------------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . --------------------------------------------------- . . . | . . . | . . . . . f7F8 | . . . | d2D4 e2E7 . . . . | . . . | . . .

The following colors can be found to exclude each other: A-B, A-F, b-c, C-D, d-e, E-f.

Could you list all candidates in your grid? Here is my grid, in which A-B, A-F, E-f are not conjugates.

by **Lummox JR** » Sat Oct 01, 2005 5:07 am

Here is my grid, in which A-B, A-F, E-f are not conjugates.

Indeed they are not conjugates, or else I wouldn't have given them different color labels. I simplified even further by assuming that none of those excluded pairs were conjugates, since that would not be a safe assumption for the general case of forcing chains.

When I say A and B exclude each other, I mean simply that if one is true, the other must be false. Therefore either a or b is true, or both, and any position where they intersect must be false. Since in my example b excludes f, either B or F or both are true, and they intersect at (3,2)=8. Therefore, (3,2) is not an 8.

by **Jeff** » Sat Oct 01, 2005 11:21 am

Lummox JR wrote:When I say A and B exclude each other, I mean simply that if one is true, the other must be false. Therefore either a or b is true, or both, and any position where they intersect must be false. Since in my example b excludes f, either B or F or both are true, and they intersect at (3,2)=8. Therefore, (3,2) is not an 8.

Sorry, I still don't get it. With either a or b is true, a & b must be conjugates and they can't be both true.

However, I wish you could try your technique on this grid which I was able to remove 10 candidates using double inplication forcing chains from here, but yet unable to solve it completely. I will be interested to see what candidates can be eliminated by the advanced colouring technique and whether it can solve the grid completely.

by **Lummox JR** » Sat Oct 01, 2005 8:47 pm

I think there's a discrepancy in our terminology here. In my coloring, a and A are conjugates, and b and B are conjugates, and so on. That says nothing about whether two completely different colors are conjugates.

So if I were to say that b excludes f, as in my examples, that means that at most one of them can be true--but it's not necessary that either of them be true. If b is true then f is false, and F its conjugate must be true. Similarly if f is true then b is false, and B its conjugate must be true. If both b and f are false, their conjugates B and F are both true. Therefore, (4,2)=8, or (3,8)=8, or both. In any of those cases, (3,2) cannot be 8.

I look forward to the challenge of running your grid through advanced coloring. I suspect I can't crack the puzzle with it, because it simply has too many cells with 3+ (often 6!) candidates, but I'm sure I can come up with something interesting.

by **Lummox JR** » Sun Oct 02, 2005 2:00 am

Well, here's my analysis of the situation. I also was able to remove only 10 candidates, which suggests that advanced coloring does supercede forcing chains.
[edit]
When I updated my solver to try to run this it found an exclusion I originally didn't, so the end result was the elimination of 16 candidates.

It's also clear that double-implication chains aren't what I thought they were, since the forcing chains I'm familiar with are the ones found by Trebor's susser. If you have any links explaining how to use double implication chains I'd like to see them. Anyway, what follows is my set of deductions, at length:

Code: Select all: 56 56 . | 38 . 348 | . 348 . aA Aa | bB c | C 179 . . | . 2457 12 | 245 59 259 def | C E Dd | c gG . 179 17 | 123578 2578 1238 | 2568 35689 235689 F hH | i | j -------------------------------------------------------------------------- 12367 12678 1347 | 39 2678 . | 2468 16789 12689 c | kK | C 2567 245678 . | 278 . 268 | . 45678 2568 C | I l | c 123567 125678 1357 | . 2678 39 | 2568 156789 125689 | Kk | -------------------------------------------------------------------------- 123579 12579 1357 | 12589 2568 12689 | 68 368 . F | L | mM j 135 15 1345 | 158 4568 . | . . 368 nN C | c o | JO . 249 . | 29 . 249 | . 15 15 c | pP C | qQ Qq

Exclusions:
A!N; b!k; c!o; C!E; d!e; d!f; d!h; e!f; e!H; E!i; f!G; g!Q; H!i; J!O; K!P; L!m; L!o; m!O

2nd round:
A!N; b!k,P; c!J,m,o; C!d,E,f,H; d!C,e,f,h,i; e!d,f,H; E!C,i,o; f!C,d,e,G,i,Q; g!Q; G!f; h!d; H!C,e,i; i!d,E,f,H; J!c,L,O; k!b; K!P; L!J,m,o; N!A; m!L,O; o!c,E,L; O!J,m; P!b,K; Q!f,g

3rd round:
A!N; b!k,P; c!J,m,o; C!d,E,f,H; d!C,e,f,h,i,J,m,o; e!d,f,H; E!C,i,J,m,o; f!C,d,e,G,i,J,m,o,Q; g!Q; G!f; h!d; H!C,e,i,J,m,o; i!d,E,f,H; J!c,d,E,f,H,L,O; k!b; K!P; L!J,m,o; m!c,E,L,O; N!A; o!c,d,E,f,H,L; O!J,m; P!b,K; Q!f,g

4th round:
A!N; b!k,P; c!J,m,o; C!d,E,f,H; d!C,e,f,h,i,J,m,o; e!d,f,H; E!C,i,J,m,o; f!C,d,e,G,i,J,m,o,Q; g!Q; G!f; h!d; H!C,e,i,J,m,o; i!d,E,f,H; J!c,d,E,f,H,L,O; k!b; K!P; L!J,m,o; m!c,d,E,f,H,L,O; N!A; o!c,d,E,f,H,L; O!J,m; P!b,K; Q!f,g

No contradictions found

c!J, so C or j is true. C and j intersect at (8,1)=3, so (8,1)<>3.
A new pointing pair is discovered in box 3, row 3, so (4,3)<>3 and (6,3)<>3.

Code: Select all: 56 56 . | 38 . 348 | . 48 . aA Aa | bB Bc | Cc 179 . . | . 2457 12 | 245 59 259 def | C E Dd | c gG . 179 17 | 12578 2578 128 | 2568 35689 235689 F hH | i | J j -------------------------------------------------------------------------- 12367 12678 1347 | 39 2678 . | 2468 16789 12689 c | kK | C 2567 245678 . | 278 . 268 | . 45678 2568 C | I l | c 123567 125678 1357 | . 2678 39 | 2568 156789 125689 | Kk | -------------------------------------------------------------------------- 123579 12579 1357 | 12589 2568 12689 | 68 368 . F | L | mM j 135 15 1345 | 158 4568 . | . . 368 nN C | c o | JO . 249 . | 29 . 249 | . 15 15 c | pP C | qQ Qq

b and k are conjugates, and B and K are conjugates, so bB=Kk

Code: Select all: 56 56 . | 38 . 348 | . 48 . aA Aa | bB Bc | Cc 179 . . | . 2457 12 | 245 59 259 def | C E Dd | c gG . 179 17 | 12578 2578 128 | 2568 35689 235689 F hH | i | J j -------------------------------------------------------------------------- 12367 12678 1347 | 39 2678 . | 2468 16789 12689 c | Bb | C 2567 245678 . | 278 . 268 | . 45678 2568 C | I l | c 123567 125678 1357 | . 2678 39 | 2568 156789 125689 | bB | -------------------------------------------------------------------------- 123579 12579 1357 | 12589 2568 12689 | 68 368 . F | L | mM j 135 15 1345 | 158 4568 . | . . 368 nN C | c o | JO . 249 . | 29 . 249 | . 15 15 c | pP C | qQ Qq

New exclusion: B!c

A!N; b!P; B!c; c!B,J,m,o; C!d,E,f,H; d!C,e,f,h,i,J,m,o; e!d,f,H; E!C,i,J,m,o; f!C,d,e,G,i,J,m,o,Q; g!Q; G!f; h!d; H!C,e,i,J,m,o; i!d,E,f,H; J!c,d,E,f,H,L,O; L!J,m,o; m!c,d,E,f,H,L,O; N!A; o!c,d,E,f,H,L; O!J,m; P!b; Q!f,g

2nd round:
A!N; b!P; B!c,d,E,f,H; c!B,J,m,o,P; C!d,E,f,H; d!B,C,e,f,h,i,J,m,o; e!d,f,H; E!B,C,i,J,m,o; f!B,C,d,e,G,i,J,m,o,Q; g!Q; G!f; h!d; H!B,C,e,i,J,m,o; i!d,E,f,H; J!c,d,E,f,H,L,O; L!J,m,o; m!c,d,E,f,H,L,O; N!A; o!c,d,E,f,H,L; O!J,m; P!b,c; Q!f,g;

3rd round:
A!N; b!P; B!c,d,E,f,H; c!B,J,m,o,P; C!d,E,f,H; d!B,C,e,f,h,i,J,m,o,P; e!d,f,H; E!B,C,i,J,m,o,P; f!B,C,d,e,G,i,J,m,o,P,Q; g!Q; G!f; h!d; H!B,C,e,i,J,m,o,P; i!d,E,f,H; J!c,d,E,f,H,L,O; L!J,m,o; m!c,d,E,f,H,L,O; N!A; o!c,d,E,f,H,L; O!J,m; P!b,c,d,E,f,H; Q!f,g

No contradictions found

c!m, so C or M must be true. C and M intersect at (7,4)=8, so (7,4)<>8.
c!P, so C or p must be true. C and p intersect at (6,9)=2, so (6,9)<>2.

Code: Select all: 56 56 . | 38 . 348 | . 48 . aA Aa | bB Bc | Cc 179 . . | . 2457 12 | 245 59 259 def | C E Dd | c gG . 179 17 | 12578 2578 128 | 2568 35689 235689 F hH | i | J j -------------------------------------------------------------------------- 12367 12678 1347 | 39 2678 . | 246 16789 12689 c | Bb | C 2567 245678 . | 278 . 268 | . 45678 2568 C | I l | c 123567 125678 1357 | . 2678 39 | 2568 156789 125689 | bB | -------------------------------------------------------------------------- 123579 12579 1357 | 12589 2568 12689 | 68 368 . F | L | mM j 135 15 1345 | 158 4568 . | . . 368 nN C | c o | JO . 249 . | 29 . 49 | . 15 15 Pc | pP Cc | qQ Qq

C!H, so c or h must be true. c and h intersect at (3,4)=1, so (3,4)<>1.
E!i, so e or I must be true. e and I intersect at (1,5)=7, so (1,5)<>7.
f!J, so F or j must be true. F and j intersect at (9,3)=9, so (9,3)<>9.

Code: Select all: 56 56 . | 38 . 348 | . 48 . aA Aa | bB Bc | Cc 179 . . | . 2457 12 | 245 59 259 def | C E Dd | c gG . 179 17 | 12578 2578 128 | 2568 35689 23568 F hH | i | J f j -------------------------------------------------------------------------- 12367 12678 347 | 39 2678 . | 246 16789 12689 c | Bb | C 256 245678 . | 278 . 268 | . 45678 2568 C | I l | c 123567 125678 1357 | . 2678 39 | 2568 156789 125689 | bB | -------------------------------------------------------------------------- 123579 12579 1357 | 12589 2568 12689 | 68 368 . F | L | mM j 135 15 1345 | 158 4568 . | . . 368 nN C | c o | JO . 249 . | 29 . 49 | . 15 15 Pc | pP Cc | qQ Qq

L!o, so l or O must be true. l and O intersect at (9,5)=6, so (9,5)<>6.
f!J, so F or j must be true. F and j intersect at (1,7)=3, so (1,7)<>3.

Code: Select all: 56 56 . | 38 . 348 | . 48 . aA Aa | bB Bc | Cc 179 . . | . 2457 12 | 245 59 259 def | C E Dd | c gG . 179 17 | 12578 2578 128 | 2568 35689 23568 F hH | i | J f j -------------------------------------------------------------------------- 12367 12678 347 | 39 2678 . | 246 16789 12689 c | Bb | C 256 245678 . | 278 . 268 | . 45678 258 C | I l | c 123567 125678 1357 | . 2678 39 | 2568 156789 125689 | bB | -------------------------------------------------------------------------- 12579 12579 1357 | 12589 2568 12689 | 68 368 . F J | L | mM j 135 15 1345 | 158 4568 . | . . 368 nN C | c o | JO . 249 . | 29 . 49 | . 15 15 Pc | pP Cc | qQ Qq

This is where I initially stopped when I first posted this. However my solver told me there was more. Sure enough I looked, and it's there.

C!f, so c or F must be true. c and F intersect at (2,9)=9, so (2,9)<>9.
A new pointing pair is discovered in box 8, row 9, so (4,7)<>9 and (6,7)<>9.

Code: Select all: 56 56 . | 38 . 348 | . 48 . aA Aa | bB Bc | Cc 179 . . | . 2457 12 | 245 59 259 def | C E Dd | c gG . 179 17 | 12578 2578 128 | 2568 35689 23568 F hH | i | J f j -------------------------------------------------------------------------- 12367 12678 347 | 39 2678 . | 246 16789 12689 c | Bb | C 256 245678 . | 278 . 268 | . 45678 258 C | I l | c 123567 125678 1357 | . 2678 39 | 2568 156789 125689 | bB | -------------------------------------------------------------------------- 12579 12579 1357 | 12589 2568 12689 | 68 368 . F J | L | mM j 135 15 1345 | 158 4568 . | . . 368 nN C | c o | JO . 24 . | 29 . 49 | . 15 15 Pc | pP Cc | qQ Qq

c and P are conjugates in (2,9), so cC=pP.
b and C are conjugates in column 4, digit 9, so bB=cC.

Exclusions are now:
A!N; b!J,m,o; B!d,E,f,H; d!B,e,f,h,i,J,m,o; e!d,f,H; E!B,i,J,m,o; f!B,d,e,G,i,J,m,o,Q; g!Q; G!f; h!d; H!B,e,i,J,m,o; i!d,E,f,H; J!b,d,E,f,H,L,O; L!J,m,o; m!b,d,E,f,H,L,O; N!A; o!b,d,E,f,H,L; O!J,m; Q!f,g

Code: Select all: 56 56 . | 38 . 348 | . 48 . aA Aa | bB Bb | Bb 179 . . | . 2457 12 | 245 59 259 def | B E Dd | b gG . 179 17 | 12578 2578 128 | 2568 35689 23568 F hH | i | J f j -------------------------------------------------------------------------- 12367 12678 347 | 39 2678 . | 246 16789 12689 b | Bb | B 256 245678 . | 278 . 268 | . 45678 258 B | I l | b 123567 125678 1357 | . 2678 39 | 2568 156789 125689 | bB | -------------------------------------------------------------------------- 12579 12579 1357 | 1258 2568 1268 | 68 368 . F J | L | mM j 135 15 1345 | 158 4568 . | . . 368 nN B | b o | JO . 24 . | 29 . 49 | . 15 15 Bb | bB Bb | qQ Qq

Conjugates b and B intersect at (6,1)=8, so (6,1)<>8.
Conjugates b and B intersect at (3,4)=3, so (3,4)<>3.

Code: Select all: 56 56 . | 38 . 34 | . 48 . aA Aa | bB Bb | Bb 179 . . | . 2457 12 | 245 59 259 def | B E Dd | b gG . 179 17 | 12578 2578 128 | 2568 35689 23568 F hH | i | J f j -------------------------------------------------------------------------- 12367 12678 47 | 39 2678 . | 246 16789 12689 b bB | Bb | B 256 245678 . | 278 . 268 | . 45678 258 B | I l | b 123567 125678 1357 | . 2678 39 | 2568 156789 125689 | bB | -------------------------------------------------------------------------- 12579 12579 1357 | 1258 2568 1268 | 68 368 . F J | L | mM j 135 15 1345 | 158 4568 . | . . 368 nN B | b o | JO . 24 . | 29 . 49 | . 15 15 Bb | bB Bb | qQ Qq

b!m, so B or M must be true. B and M intersect at (4,7)=8, so (4,7)<>8.
Conjugates b and B intersect at (1,4)=7, so (1,4)<>7.

Code: Select all: 56 56 . | 38 . 34 | . 48 . aA Aa | bB Bb | Bb 179 . . | . 2457 12 | 245 59 259 def | B E Dd | b gG . 179 17 | 12578 2578 128 | 2568 35689 23568 F hH | i | J f j -------------------------------------------------------------------------- 1236 12678 47 | 39 2678 . | 246 16789 12689 b bB | Bb | B 256 245678 . | 278 . 268 | . 45678 258 B | I l | b 123567 125678 1357 | . 2678 39 | 2568 156789 125689 | bB | -------------------------------------------------------------------------- 12579 12579 1357 | 125 2568 1268 | 68 368 . F J | L | mM j 135 15 1345 | 158 4568 . | . . 368 nN B | b o | JO . 24 . | 29 . 49 | . 15 15 Bb | bB Bb | qQ Qq

That's the absolute limit of advanced coloring. As implemented originally in my program it didn't find those because this is using the intersection of conjugates of mutually exclusive colors. It's far more common for advanced coloring to find a color contradicting itself. However in a puzzle like this one that has so many candidates left, it's amazing it could find anything at all.

One thing of note: Note the spots where 7 is eliminated from (1,5) and 6 from (9,5). Simple coloring will actually find these if you use the exclusion rule.

16 candidates vs. 10 is a definite sign that this beats the tar out of forcing chains of any kind.

by **Jeff** » Sun Oct 02, 2005 9:29 am

Lummox JR wrote:I think there's a discrepancy in our terminology here. In my coloring, a and A are conjugates, and b and B are conjugates, and so on. .....

Thank you for your patience to explain. The fog is finally cleared. BTW, for the benefits of other readers, may I make a couple suggestions with no obligation of course.

1) Could 'bivalue' be used in place of 'conjugate' in this context, considering that:

a) conjugates have already been well adopted as to mean 'x' and 'not x', not 'x' or 'y'.
b) your example above deals with 2-candidate cells, which is equivalent to bivalue cells of an xy-chain: starting [r2c3], 58-81-14-42-27-78-85 => r2c3<>8.

2) It would be nice if you could use coordinate notation in the form of r2c3 instead of (3,2).

I will respond in length on the comparison of advanced colouring and double implication chain shortly.

by **Jeff** » Sun Oct 02, 2005 12:39 pm

Lummox JR wrote:It's also clear that double-implication chains aren't what I thought they were, since the forcing chains I'm familiar with are the ones found by Trebor's susser. If you have any links explaining how to use double implication chains I'd like to see them........

Refer here to start with.

Firstly, thank you for your effort for the amount of work done. Could you advise whether the advanced colouring deductions were performed manually or aided by computer solver. They are remarkably accurate. If they were computer aided, would you consider advanced colouring as a technique suitable for manual application.

Actually, when I said 10 candidates were eliminated by double implication chains, it doesn't include those ones eliminated by basic rules in between. However, guided by your findings, I found 2 more chains that I have missed out earlier.

In conclusion, with all the candidates excluded via advanced colouring, the double implication chain technique actually does exactly the same. Listed below are the chains identified for your reference.

Starting grid:

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 | *-----------------------------------------------------------------------------*

Chain 1 (Turbot fish): [r5c1]-7-[r2c1]=7=[r2c5]-7-[r3c4]=7=[r5c4]-7-[r5c1] => r5c1<>7
Chain 2 (Turbot fish): [r5c9]-6-[r5c6]=6=[r7c6]-6-[r8c5]=6=[r8c9]-6-[r5c9] => r5c9<>6
Chain 3: [r1c8]=4=[r1c6]-4-[r2c5]=4=[r8c5]=6=[r8c9]=3=[r3c9]-3-[r1c8] => r1c8<>3
Chain 4: [r4c3]=4=[r4c7]-4-[r2c7]=4=[r2c5]=7=[r2c1]-7-[r3c3]-1-[r4c3] => r4c3<>1
Chain 5: [r4c7]=4=[r2c7]-4-[r2c5]=4=[r8c5]=6=[r8c9]-6-[r7c7]-8-[r4c7] => r4c7<>8
Chain 6: [r3c9]=3=[r8c9]=6=[r8c5]=4=[r2c5]=7=[r2c1]=9=[r3c2]-9-[r3c9] => r3c9<>9

where chain notation '=x=' means conjugate linked and '-x-' means unconditionally linked.

From here, applying basic rules gives r3c4<>3 and r3c6<>3. The grid is then reduced to:

Code: Select all: *-----------------------------------------------------------------------------* | 56 56 2 | 38 9 348 | 1 48 7 | | 179 3 8 | 6 2457 12 | 245 59 259 | | 4 179 17 | 12578 2578 128 | 2568 35689 23568 | |-------------------------+-------------------------+-------------------------| | 12367 12678 347 | 39 2678 5 | 246 16789 12689 | | 256 245678 9 | 278 1 268 | 3 45678 258 | | 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 | *-----------------------------------------------------------------------------*

Chain 7: [r9c6]=4=[r1c6]=3=[r6c6]-3-[r4c4]-9-[r9c6] => r9c6<>2
Chain 8: [r7c1]=9=[r2c1]-9-[r3c2]=9=[r3c8]-3-[r4c4]=3=[r7c8]-3-[r7c1] => r7c1<>3
Chain 9: [r9c2]-9-[r9c6]-4-[r1c6]=4=[r2c5]=7=[r2c1]=9=[r7c1]-9-[r9c2] => r9c2<>9

From here, applying basic rules gives r7c4<>9, r7c6<>9 and r1c6<>8. The grid is then reduced to:

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 | |-------------------------+-------------------------+-------------------------| | 12367 12678 347 | 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 | 1258 2568 1268 | 68 368 4 | | 135 15 1345 | 158 4568 7 | 9 2 368 | | 8 24 6 | 29 3 49 | 7 15 15 | *-----------------------------------------------------------------------------*

Chain 10: [r7c4]-9-[r9c6]-8-[r1c4]-3-[r1c6]-4-[r9c6]=4=[r8c5]=6=[r8c9]-6-[r7c7]-8-[r7c4] => r7c4<>8
Chain 11: [r4c3]=4=[r8c3]-4-[r9c2]-2-[r9c4]-9-[r4c4]-3-[r4c3] => r4c3<>3
Chain 12: [r4c1]=3=[r4c4]-3-[r1c4]=3=[r1c6]=4=[r2c5]=7=[r2c1]-7-[r4c1] => r4c1<>7

From here, after 12 chains and a total of 17 candidate eliminations, the grid reduced to same as the advanced colouring limit:

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 | *-----------------------------------------------------------------------------*

From here, a further candidate can be removed by an wxyz-wing, a rare encounter indeed. But it still leads to nowhere.

by **Lummox JR** » Mon Oct 03, 2005 4:59 am

Well, to address all those points:

Firstly, thank you for your effort for the amount of work done. Could you advise whether the advanced colouring deductions were performed manually or aided by computer solver. They are remarkably accurate. If they were computer aided, would you consider advanced colouring as a technique suitable for manual application.

The first set of deductions were performed manually. However when I initially posted I had missed one, which eliminated 9 at (2,9). Once I implemented the new rules into my solver, it found this one quite quickly, and that in turn led to further deductions that could be made by hand. I do think this is suited to manual application, but it takes a sharp eye to see sometimes where intersections are possible.

1) Could 'bivalue' be used in place of 'conjugate' in this context, considering that:

a) conjugates have already been well adopted as to mean 'x' and 'not x', not 'x' or 'y'.
b) your example above deals with 2-candidate cells, which is equivalent to bivalue cells of an xy-chain: starting [r2c3], 58-81-14-42-27-78-85 => r2c3<>8.

The way I'm using conjugates does mean 'x' and 'not x'. In each case it's a binary choice between one set of placements and another, with no third option. One and only one of those choices must be true.

Also, not all of the methods use 2-candidate cells. While my first example was exactly that, your grid was a case that used conjugates in house-digit constraints as well as in cells. And because in simple coloring, extension of conjugates to other cells is part of the technique, it makes sense not only to use the same method but also the same terminology from that.

2) It would be nice if you could use coordinate notation in the form of r2c3 instead of (3,2).

I confess I have a certain aesthetic revulsion to that, though. For one thing, it puts the Y coordinate first, which isn't logical given that we number the boxes 1-9 in a left-to-right order, nor the fact that pretty much all coordinate systems (graphical, Cartesian) put the X first. I know, granted, a simple coordinate pair like (3,2) might cause some confusion inasmuch as so many people are putting the Y first, but I just have no truck with acknowledging it. Putting the Y first is a programmatic concept, not a mathematical one; it's merely convenient in C and other languages.

Chain 1 (Turbot fish): [r5c1]-7-[r2c1]=7=[r2c5]-7-[r3c4]=7=[r5c4]-7-[r5c1] => r5c1<>7
Chain 2 (Turbot fish): [r5c9]-6-[r5c6]=6=[r7c6]-6-[r8c5]=6=[r8c9]-6-[r5c9] => r5c9<>6

These are the two cases I noted that show up with simple coloring, provided you give it full transitivity and tell it to look for intersections of the conjugates of mutually exclusive colors. I don't think most people take simple coloring to this extreme, but given the number of colors involved it's quite easy and vastly improves coloring's power (while simultaneously making it a superset of fishy cycles).

Chain 3: [r1c8]=4=[r1c6]-4-[r2c5]=4=[r8c5]=6=[r8c9]=3=[r3c9]-3-[r1c8] => r1c8<>3

Now I get what double-implication means: This chain says the very thing I first predicted advanced coloring would, namely that you can say that either r1c8=4 or r3c9=3, or perhaps both, so therefore r1c8 can't be 3 (nor r3c9 a 4, though that's not a possibility here). The "both" part I didn't realize at first, but it's a crucial insight. Essentially a double-implication is just an intersection of possibilities, at least one of which must be true, between two placements in the same house.

Given the way that works, I suspect advanced coloring is the union of all forcing chain techniques.

From here, a further candidate can be removed by an wxyz-wing, a rare encounter indeed. But it still leads to nowhere.

Now that's a new one on me. I'm wondering whether I should try implementing that in my solver, or if I should figure out if there's a base logic extending XYZ-wing to a more general case.

The New Sudoku Players' Forum

My Worry with Forced Chains