Coloured Chains

If you invented that new way to solve these little puzzles, tell us about it
Post Reply
lac
Hooked
Hooked
Posts: 43
Joined: Mon Jan 02, 2006 1:20 am
Location: Göteborg, Sweden

Coloured Chains

Post by lac »

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: Select all

.-----------------------.-----------------------.-----------------------.
|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: Select all

.-----------------------.-----------------------.-----------------------.
|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: Select all

.-----------------------.-----------------------.-----------------------.
|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. :D

Begin with the Nightmare for Dec 31 which you can get here:
http://www.sudocue.net/dailyarchive.htm

Solving normally you soon reach:

Code: Select all

.-----------------------.-----------------------.-----------------------.
|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: Select all

.-----------------------.-----------------------.-----------------------.
|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: Select all

.-----------------------.-----------------------.-----------------------.
|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: Select all

.-----------------------.-----------------------.-----------------------.
|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: Select all

.-----------------------.-----------------------.-----------------------.
|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.
Ruud
Site Owner
Site Owner
Posts: 601
Joined: Fri Dec 30, 2005 10:21 pm

Post by Ruud »

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
Ron Moore
Addict
Addict
Posts: 72
Joined: Sun Aug 13, 2006 3:34 am
Location: New Mexico

Post by Ron Moore »

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: Select all

.-----------------------.-----------------------.-----------------------.
|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
David Bryant
Gold Member
Gold Member
Posts: 86
Joined: Fri Jan 20, 2006 6:21 pm
Location: Denver, Colorado
Contact:

Same deduction, different track

Post by David Bryant »

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
Post Reply