 |
SudoCue Users
A forum for users of the SudoCue programs and the services of SudoCue.Net
|
| View previous topic :: View next topic |
| Author |
Message |
lac
Hooked
Joined: 02 Jan 2006
Posts: 43
Location: Göteborg, Sweden
|
 Posted: Thu Jan 19, 2006 3:56 am Post subject: Coloured Chains |
 |
|
Well, here it is. I think I am using a technique which is not being used by
anybody else who is discussing it on the web (at least in English or
Swedish or Danish or Norwegian). But this may simply mean that I
am not looking in the correct places. Also, I never saw a complete
description of 'medusa chains' or 'ultracolouring' -- so perhaps I am
only restating what is already well known but not talked about. When you
are done reading this novel, let me know what you think. Also, let me
know about any typos and the like so I can fix them.
Since I think this technique partakes of both 'forcing chains' and
'colouring' I am calling it 'coloured chains'. But where discriptions
of colouring I have read discuss colouring the cell, what I colour is
the digits themselves. This is best done with a set of coloured pencils,
but since the effort involved to generate HTML with digits in the
appropriate colours seems disproportionate, I am going to make do with
postscript notation. I am also using (x,y) notion -- so (1,4) is
column 1, row 4.
It is easier to explain with a few examples. I am endebted to Ruud for
his Daily Sudoku NightMare. We will start with a relatively easy one.
This is the puzzle from Dec 13 2005 which you can download here:
http://www.sudocue.net/dailyarchive.htm
Doing the obvious, you end up here:
| Code: |
.-----------------------.-----------------------.-----------------------.
|7 6 1 |8 3 2 |4 9 5 |
|4 9 8 |1 6 5 |2 37 37 |
|3 5 2 |4 9 7 |6 1 8 |
:-----------------------+-----------------------+-----------------------:
|9 378 367 |63 4 1 |378 5 2 |
|568 4 356 |2 7 9 |1 368 36 |
|2 1 367 |36 5 8 |37 4 9 |
:-----------------------+-----------------------+-----------------------:
|1 37 9 |57 8 6 |537 2 4 |
|568 2 356 |57 1 4 |9 3678 367 |
|568 78 4 |9 2 3 |578 678 1 |
'-----------------------'-----------------------'-----------------------'
|
At this point, I begin colouring the numbers into chains. Each chain has
two colours -- for instance, red and green. The colouring rules are as follows:
1. when any given row, column, or house has only two possible locations
for a candidate, you colour one of them the first colour, and the
second one the second colour
2. the links of the chain MUST alternate in colours.
3. whenever you reach a cell that has only two values, and you know the colour
of one candidate, you can always set the other candidate to be the other
colour.
I am only going to build one chain here, the =~ chain. Later I will give
you an example with more than one chain. I am going to indicate one colour
with = and the other with ~ . And I am going to begin with the {6,3} pair in
(4,4)
| Code: |
.-----------------------.-----------------------.-----------------------.
|7 6 1 |8 3 2 |4 9 5 |
|4 9 8 |1 6 5 |2 37 37 |
|3 5 2 |4 9 7 |6 1 8 |
:-----------------------+-----------------------+-----------------------:
|9 378 36+7 |6=3~ 4 1 |378 5 2 |
|568 4 356 |2 7 9 |1 368 36 |
|2 1 36~7 |3~6= 5 8 |37 4 9 |
:-----------------------+-----------------------+-----------------------:
|1 37 9 |57 8 6 |537 2 4 |
|568 2 356 |57 1 4 |9 3678 367 |
|568 78 4 |9 2 3 |578 678 1 |
'-----------------------'-----------------------'-----------------------'
|
Ok, this was a very short chain. (Which was the whole idea. Long ones
are easy to build, but hard to see.) Even though this one is tiny, it
still accomplishes something useful.
When building coloured chains, you are looking to do one of three things.
The first is to join two chains together. Since we have only one
chain, we cannot do this. The second thing we can do is eliminate
candidates. This is what is possible here.
If you look at (3,4) and (3,5) you find that we have a 6- and a 6+ in the
same column, which is also in the same house. Any time you find this
situation, you can remove the other candidates from the included set (in
this case the column and the house). This is the first virtue of this
technique. So we remove 6s from (3,5) (3,8 ) (1,5).
Removing the 6s makes the {3,5} a naked pair in (3,5) (3,8 ). Thus you
can remove the 3s from (3,4) and(3,6). This means that we can extend the
chain to include the 7s at both these points, since they are now doubletons.
This means we can eliminate the extra 7 in (2,4) (since the house already
has a 7= and a 7~). This means there are now only 2 sevens in the 4th
row, so we can extend the chain, and happily find 2 opposite coloured 7s
in column 7.) This means we can eliminate the extra 7s in column 7 (and
in the middle right house, if we had any.)
So far, all this has done is provided an alternative way to find Xwings
and locked candidates, so you may not be overly impressed. However,
This is only the start. Unfortunately, this is as far as this chain
will take you. We need to start a different coloured chain. I am going
to colour these ones + and -, and begin with the {5,8} in (1,5)
I can remove the 8 in (1,9) and (8,9), which makes the chain extend.
So here we are at:
| Code: |
.-----------------------.-----------------------.-----------------------.
|7 6 1 |8 3 2 |4 9 5 |
|4 9 8 |1 6 5 |2 37 37 |
|3 5 2 |4 9 7 |6 1 8 |
:-----------------------+-----------------------+-----------------------:
|9 3+8- 6+7~ |6=3~ 4 1 |37=8+ 5 2 |
|5-8+ 4 3-5+ |2 7 9 |1 368- 36 |
|2 1 6~7= |3~6= 5 8 |3=7~ 4 9 |
:-----------------------+-----------------------+-----------------------:
|1 3-7+ 9 |57 8 6 |5-3+ 2 4 |
|56-8- 2 3+5- |57 1 4 |9 3678+ 367 |
|5-6+ 7-8+ 4 |9 2 3 |5+8- 6-7+ 1 |
'-----------------------'-----------------------'-----------------------'
|
It is useful to remember that either al the + candidates exist or
all the - candidates exist in a single puzzle. But if you take a look
at (1,8 ) ýou will see that it contains two -coloured candidates. This
means that we have proven that the -coloured ones must be the ones
that do not exist, and the +coloured ones the set that do. You can mark
in every + candidate as a true solution. (proof by two -s in the same cell).
Indeed, in this example, we managed to prove this a second way.(1,9) and (3,8 )
both_ contain 5-. This also means that the -coloured candidates cannot exist.
(proof by two digits of the same colour in a common column, row, or house.)
What else do we know?
In (7,4) the first chain we built and the second intersect. Since
we know that the + candidates must exist, we can join up the chain. The
= candidates must not exist, so the colour ~ is the same as +, and could be
replaced by it, and the colour = is likewise the same as -. Thus all the
~coloured candidates must also be true solutions.
Note, if we had not already proven that the +coloured candidates were the
true solution, we could not join the chain this way. The possibility
would still exist that 3 was the true solution, and both + and = were
the same colour, the colour that did not exist in the puzzle.
At this point the puzzle is solved. To demonstrate the more advanced use
of this technique, I need a harder puzzle. Fortunately, Ruud is perfectly
willing to oblige. 
Begin with the Nightmare for Dec 31 which you can get here:
http://www.sudocue.net/dailyarchive.htm
Solving normally you soon reach:
| Code: |
.-----------------------.-----------------------.-----------------------.
|2A5a 389 13478 |1236 1246 345A6 |246789 2467 1248 |
|2a5A 389 1348 |1236 7 345a6 |24689 246 1248 |
|6 1B7b 147 |8 1b24 9 |2457 2457 3 |
:-----------------------+-----------------------+-----------------------:
|4 2D8d 5E8e |267 3 678 |25e6 1 9 |
|1 2d38 35e8 |9 2468b 468 |2456 2456 7 |
|7 6 9 |5 2F4f 1 |3 8 2f4F |
:-----------------------+-----------------------+-----------------------:
|3C8c 1b47 6 |1B37 9 378 |2478 247 5 |
|3c8C 4G7g 2 |367 5 3678 |1 9 4g8G |
|9 5 1B7b |4 1b8B 2 |7B8b 3 6 |
'-----------------------'-----------------------'-----------------------'
|
where there is an Aa chain, a Bb chain, and so on and so forth, instead
of +- and =~, all the way up to Gg. So, lots of short, useless chains.
But we can prove one useful thing. (This is actually what I find the
trickiest part. I would like to present the way to use this in a slightly
different order, saving this one for last. But so it goes ...)
First look at the lower left house.
Looking at the doubletons in (2,8 ) and (3,9) we can conclude that:
If g is a correct chain, then B must also be correct. (Only one 7 per house.)
If b is a correct chain then G must also be correct. (same reasoning.)
Then you move to the lower right house.
Looking at the doubletons in (7,9), (9,8 ) we can conclude that:
If G is a correct chain, then B must also be correct. (Only one 8 per house.)
If b is a correct chain then g must also be correct. (same reasoning.)
b implies G and not G. Therefore b cannot be a correct chain.
Therefore B is the correct chain. We can simplify a lot. In the
process, we discover that we can link the Gg chains with the Cc
chains, according to C is g. In the middle box, we find we can
join our F and D chains, according to D is F. We can also begin some
begin some new ones. (Note: I am not going to use the letters Ii or Ll
because depeinding on your font they can be confused with each other
and with the number 1. By the way, this is a _lot_ clearer with coloured
pencils.)
So now we get to here:
| Code: |
.-----------------------.-----------------------.-----------------------.
|2A5a 389 347H8 |236 1 345A6 |2489 2467h 2F48g |
|2a5A 389 348 |236 7 345a6 |2489 246 1 |
|6 1 4H7h |8 2f4F 9 |245M 245m7H 3 |
:-----------------------+-----------------------+-----------------------:
|4 2F8f 5 |2f7F 3 7f8F |6 1 9 |
|1 2f3J8 3j8J |9 6 4F8f |245m 245M 7 |
|7 6 9 |5 2F4f 1 |3 8 2f4F |
:-----------------------+-----------------------+-----------------------:
|3g8G 4g7G 6 |1 9 3G7g |2K48g 2k4K 5 |
|3G8g 4G7g 2 |367 5 367 |1 9 4g8G |
|9 5 1 |4 8 2 |7 3 6 |
'-----------------------'-----------------------'-----------------------'
|
This time using the chains is more straightforward.
Start with cells that contain more than one coloured chain.
From (2,5) (9,1) (7,7) (8,3)
f and J cannot both be correct chains. (They could both be false.)
F and g cannot both be correct chains. (likewise.)
K and g cannot both be correct chains. (likewise.)
m and H cannot both be correct chains. (likewise.)
(If they were, you would have 2 values in the same cell).
Then look at the rows and columns.
A and F cannot both be correct chains. (2 2s in row 1)
J and f cannot both be correct chains. (2 8s in row 5)
g and K cannot both be correct chains. (2 4s in row 6)
f and g cannot both be correct chains. (2 7s in column 6)
g and F cannot both be correct chains. (2 4s in column 9)
You can do the same thing for houses, but already we have a solution.
(And I know this looks really tedious, and it is taking me forever
to type this. But with a set of coloured pencils it goes really fast.)
If F and g cannot both be correct and f and g cannot both be correct
then g cannot be correct. G is the correct chain.
So, solving and simplifying and extending chains when appropriate, and
yes, creating a new one you end up with:
| Code: |
.-----------------------.-----------------------.-----------------------.
|2A5a 389N 347H8 |236 1 45A6 |8N9n 246P7h 2F4f |
|2a5A 389n 348 |236 7 45a6 |8n9N 246p 1 |
|6 1 4H7h |8 2f4F 9 |245M 245m7H 3 |
:-----------------------+-----------------------+-----------------------:
|4 2F8f 5 |2f7F 3 7f8F |6 1 9 |
|1 2f3J8 3j8J |9 6 4F8f |245m 245M 7 |
|7 6 9 |5 2F4f 1 |3 8 2f4F |
:-----------------------+-----------------------+-----------------------:
|8 7 6 |1 9 3 |2K4k 2k4K 5 |
|3 4 2 |6F7f 5 6f7F |1 9 8 |
|9 5 1 |4 8 2 |7 3 6 |
'-----------------------'-----------------------'-----------------------'
|
Here you can see that (4,1) cannot be 2, because it can see both 2F and 2f.
Similarly (6,1) cannot be 4, as it can see 4F and 4f. (Actually, the
postscript notation makes it a lot harder to see.)
| Code: |
.-----------------------.-----------------------.-----------------------.
|2A5a 389N 347H8 |3Q6q 1 5A6a |8N9n 246P7h 2F4f |
|2a5A 389n 348 |2F3q6 7 4f5a6 |8n9N 246p 1 |
|6 1 4H7h |8 2f4F 9 |245M 245m7H 3 |
:-----------------------+-----------------------+-----------------------:
|4 2F8f 5 |2f7F 3 7f8F |6 1 9 |
|1 2f3J8 3j8J |9 6 4F8f |245m 245M 7 |
|7 6 9 |5 2F4f 1 |3 8 2f4F |
:-----------------------+-----------------------+-----------------------:
|8 7 6 |1 9 3 |2K4k 2k4K 5 |
|3 4 2 |6F7f 5 6f7F |1 9 8 |
|9 5 1 |4 8 2 |7 3 6 |
'-----------------------'-----------------------'-----------------------'
|
By row 2 we can assert that a and F cannot both be correct. (2 2s in row 1)
But we already know that A and F cannot both be correct (2 2s in row 1)
Thus F is not correct. f is.
And finally the whole puzzle solves. Nasty one Ruud. Thank you.
There is one final trick which I did not use in solving which is also
very useful. It provides you with a second way of solving the problem
from the position of the last grid. For completeness, I will show
how you solve things this way.
Examine column 6.
Here you can make the following assertion:
Either a is false and f is false, or I can remove 6 from (6,2) (and
anywhere else in the column, aside from (6,1) and (6,8 ) if we had any).
This is equivalent to saying that either both A and F are true, or I
can remove 6 from (6,2). But we already know that A and F cannot both
be true, or you would have 2 2s in column 1. Thus you can remove the
6. Often that is all you get for a while, a way to eliminate
candidates, until something else interesting happens. But here we
have immediate payoff. We can now join the Aa and Ff chains, on the
rule that a is F.
| Code: |
.-----------------------.-----------------------.-----------------------.
|2f5F 389N 347H8 |3Q6q 1 5f6F |8N9n 246P7h 2F4f |
|2F5f 389n 348 |2F3q6 7 4f5F |8n9N 246p 1 |
|6 1 4H7h |8 2f4F 9 |245M 245m7H 3 |
:-----------------------+-----------------------+-----------------------:
|4 2F8f 5 |2f7F 3 7f8F |6 1 9 |
|1 2f3J8 3j8J |9 6 4F8f |245m 245M 7 |
|7 6 9 |5 2F4f 1 |3 8 2f4F |
:-----------------------+-----------------------+-----------------------:
|8 7 6 |1 9 3 |2K4k 2k4K 5 |
|3 4 2 |6F7f 5 6f7F |1 9 8 |
|9 5 1 |4 8 2 |7 3 6 |
'-----------------------'-----------------------'-----------------------'
|
This gives us two F-coloured 2s in row 2 (1,2) and (4,2).
Again we have proven that f must be correct and the puzzle solves.
So: what do you think? New technique? One thing to remind you, it
is a _lot_ faster to use this technique than to talk about it. It is
actually quite simple to use.
Thanks very much to Ruud for providing the puzzles. And to all of
you for having the patience to read this far.
Laura
Last edited by lac on Thu Jan 19, 2006 9:44 pm; edited 1 time in total |
|
| Back to top |
|
 |
Ruud
Site Owner
Joined: 30 Dec 2005
Posts: 601
|
| Posted: Thu Jan 19, 2006 7:09 pm Post subject: |
|
|
Hi Laura,
Your technique is used by various people, who all seem to give it a different name.
The names I've heard so far:
- Medusa
- Bifurcation
- Ultracolouring
- Supercolouring
They are all using the bivalue & bilocation pairs to form chains and draw conclusions.
Your explanation is very clear.
Ruud.
_________________
“If the human brain were so simple that we could understand it, we would be so simple that we couldn't.” - Emerson M Pugh |
|
| Back to top |
|
|
Ron Moore
Addict
Joined: 13 Aug 2006
Posts: 72
Location: New Mexico
|
| Posted: Thu Sep 07, 2006 4:02 pm Post subject: |
|
|
Laura,
I'm relatively new on the forum and I am slowly working my way through the archive. I did not solve the Dec 31 nightmare using multi-colored chains, but I will express my comment in the context of what you did. For convenience I've copied below the second position you give in the solution for Dec 31.
| Code: |
.-----------------------.-----------------------.-----------------------.
|2A5a 389 347H8 |236 1 345A6 |2489 2467h 2F48g |
|2a5A 389 348 |236 7 345a6 |2489 246 1 |
|6 1 4H7h |8 2f4F 9 |245M 245m7H 3 |
:-----------------------+-----------------------+-----------------------:
|4 2F8f 5 |2f7F 3 7f8F |6 1 9 |
|1 2f3J8 3j8J |9 6 4F8f |245m 245M 7 |
|7 6 9 |5 2F4f 1 |3 8 2f4F |
:-----------------------+-----------------------+-----------------------:
|3g8G 4g7G 6 |1 9 3G7g |2K48g 2k4K 5 |
|3G8g 4G7g 2 |367 5 367 |1 9 4g8G |
|9 5 1 |4 8 2 |7 3 6 |
'-----------------------'-----------------------'-----------------------' |
At one point (slightly later) you correctly observed that r1c4 cannot be 2, because r1c4 sees a 2f (in r3c5) and a 2F (in r1c9). Notice that both r3c7 and r3c8 also see these cells, so neither of them can be 2. This leaves only r3c5 for the 2 in row 3, and it's easy from there.
Ron Moore |
|
| Back to top |
|
|
David Bryant
Gold Member
Joined: 20 Jan 2006
Posts: 86
Location: Denver, Colorado
|
| Posted: Tue Sep 12, 2006 10:44 pm Post subject: Same deduction, different track |
|
|
Hi, Ron!
I used to talk to Laura a lot on this forum, but she sort of disappeared about last April, or May. Maybe she'll be back when winter rolls around in Sweden again. 
I never tried to use her "colored chains" technique (in the form she describes it), because it just seems too complex to me. But I was interested enough to go back through this puzzle again. I found the "2" in r3c5 at exactly this spot in the puzzle by following my customary "DIC" logic.
-- Placing either "2" or "4" in r3c5 forces quite a few additional choices in widely separated spots all around the board, so it's a good candidate for beginning a "DIC".
-- I'd already had good look finding a chain rooted in r5c5, that allowed me to place a "6" there. In fact, the way I spotted that chain was by thinking about the consequences of setting r3c5 = 1.
Anyway, the way I visualized that r3c5 <> 4 was as a chain of inference
r3c5 - r6c5 - r6c9 - r9c9 - r1c9 - r1c1 - r2c1
which pretty clearly winds up in a state where no "2" can be entered in box 2 if r3c5 - 4. (I guess this is the same as linking Laura's "Ff" and "Aa" chains together.) dcb |
|
| Back to top |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Usergroups
Register
Profile
Log in to check your private messages
Log in
