The Formal definition of Unified Colors Technique

TheSpaniard

This is the Formal definition of Expanded Colors technique (since now on, in this post, "X-Colors"). As we will see later, it is a generalisation, better: the Unification of both Colors and Multicolors techniques, and even goes beyond both of them.

Terminology: (I thing it is the most commonly used by Sudoku players).

House: Every set of cells that must contain one and only one of the digits 1 to 9. Rows, Column and a boxes are houses.
Peer (of one cell): All the cells that share a house with this given cell.
Conjugate (pair of cells) on one digit: Two and only two cells of one house that are the only possibilities to hold that digit in the whole house.
Candidate: Every different digit a cell can contain satisfying all the constraints of the given position.

Definition of the technique (the algorithm used):

Step 1) Once selected one digit candidates, select one pair of conjugate cells, and colour them with two alternate colors (namely, color "A" and color "B").

Step 2) If one of these two cells, coloured "A", is conjugate of another cell, then colour this new cell with the opposite colour (color "B").
This process is recursive, and ends when all the chain of conjugates are alternatively coloured "A" or "B".

Step 3) If all but one and only one cell (called the "Exception Cell") of all the candidates in a house are peers of cells coloured with the same color "A", then colour the Exception cell with the same color "A".
This process is recursive, and ends when you cannot find any more cells to colour.
(IMPORTANT: If as result of this process you colour "A" one cell that has a conjugate not been coloured "A" or "B" until then, YOU CAN NOT COLOUR THIS NEW CELL WITH THE OPPOSITE COLOR. This is made in steps 1 and 2, but we are now in step 3).

Step 4) Once marked "A"-"B" all possible cells in the position:

Step 4.1) If one cell has two or more peers coloured with both colors ("A" AND "B"), you can safely exclude this cell as a candidate for the digit.

Step 4.2) If two or more cells of the same house are coloured with the same color "A", then you can conclude that THE OTHER COLOR "B" IS TRUE.

That's enough to define the whole technique. Here are the "True"/"False" implications:

i) If one cell coloured "A" is identified as "True", then all cells coloured with the same color "A" are True.
ii) If one cell coloured "A" is identified as "False", then all cells coloured with the Opposite Color "B" are True.

Please note that these two assertions DOES NOT IMPLY that if "A" is true, then "B" is False, and viceversa. This sentence is only true when dealing exclusively with conjugates, and in that case, it is irrelevant, because trueing the cells colured "A" will immediatly eliminate candidates in peer cells, included the coloured "B".

Its relation with the standard Color and Multicolor techniques is the following:

Definitions:
Let's define the function Colors(x,z), that means that, given a position x, the standard Colors technique will find the solution z.
Let's define the function Multicolors(x,z), that means that, given a position x, the standard MultiColors technique will find the solution z.
And let's define the function X-Colors(x,z), that means that, given a position x, the X-Colors technique as defined in the Steps 1 to 4 of this post will find the solution z.

Then:
a) For All x, Colors(x,z) implies X-Colors(x-z), or, that is the same: (Not Colors(x,z)) Or X-Colors(x,z).
b) For All x, Multicolors(x,z) implies X-Colors(x,z), or, that is the same: (Not MultiColors(x,z)) Or X-Colors(x,z).
c) It exist some x where (Not Colors(x,z)) And (Not MultiColors(x,z)) And X-Colors(x,z).

That means that every possible solution that can be found using Colors or Multicolors can be found too with X-Colors (sentences a and b), but there are some positions where X-Colors finds a solution that neither Colors not MultiColors can not (sentence c).
Some of this new solutions mentioned in sentence c (maybe all of them, I don't konw) can be found too using other different techniques. It is irrelevant for the definition of the tecnique.

The implications of this new definition on Sudoku Solving are:
1) This technique is easy to understand, use and spot by humans. More or less, same difficulty to spot than Standard Colors. That is my only interest: solving Sudokus by humans.
Of course, probably it should ease the programming of computer Sudoku Solvers, but it is at the choice of the programmers.
2) Only uses two colors, avoiding the confusion originated by the use of four or more colors in Multicolors.
3) It is more powerful than the sum of both Colors and Multicolors, though it can find solutions in more positions.

Some examples (they are the same than in previous posts).
I have to say that I haven't learnt how to use fixed-pitch fonts like Courier in this forum to avoid the horrible impression of what it follows... my apologies. I have published the same info in
http://www.sudoku.org.uk/discus/messages/2/2441.html?1157232862
where I could easily attach some images with the three examples.
1)

angusj · Site Admin

Hi again TheSpaniard.

While the techniques you've described have been discussed elsewhere, your definitions or rules above are the perhaps the clearest (or most systematic) I've seen documented so far. Having said that, I do think you need to more clearly differentiate between strong conjugate links and weak links (which have been documented at length and are widely accepted terms) as per Ruud's post here: http://www.setbb.com/sudoku/viewtopic.php?p=6588&mforum=sudoku#6588 . That should eliminate any residual confusion about you current colouring descriptions.

Also, I've edited you post and put your grids in code blocks which I think makes them much easier to view.

TheSpaniard · Posted: Sun Sep 03, 2006 4:47 pm Post subject:

Thank you, Angus, both for the reply, and your comments, and for editing my post. I am dumb, really, I must take a course of HTML, but I have time problems...

Angus: One of the things that happen with this definition of Colors is that it does not matter what happens to conjugates. If after colouring cells with steps 1,2,3, you find the conditions cited in 4.1 or 4.2, then you proceed as mentioned, and it does not matter what happens with conjugates. At least I think so...

I am aware that X-Colors break with a well stated tradition until now, that is that blue-green are as ying-yang, if one is true the other is false and viceversa. Using X-Color technique it changes. Sometimes they are true, sometimes it is not (like in real world, things are not usually black and white, they are all grey, clearer or darker) Well, life is change....

Thank you again.

Starflyer Alien · Posted: Tue Sep 05, 2006 10:12 am Post subject:

Most excellent addition to human solving methods...

I have successfully applied it to several (previously awkward) puzzles with good results. However, I ran into a serious problem in the following (partially solved) puzzle...

angusj · Site Admin

Starflyer Alien · Posted: Tue Sep 05, 2006 12:42 pm Post subject:

Aha! Light dawns.

Had I read the method more closely and paid attention to the section marked "IMPORTANT" I would not have made this silly mistake. Embarassed

Thanks, Angus... and double thanks for your most excellent program. Very Happy

Starflyer Alien · Posted: Tue Sep 05, 2006 1:00 pm Post subject:

Further Question/Clarification...

Your statement

angusj · Site Admin

Starflyer Alien · Posted: Tue Sep 05, 2006 1:41 pm Post subject:

daj95376 · Posted: Tue Sep 05, 2006 3:11 pm Post subject:

Is there anything in the UCT to explain [r8c5]<>2 ???

Starflyer Alien · Posted: Tue Sep 05, 2006 3:41 pm Post subject:

daj95376 · Posted: Tue Sep 05, 2006 3:59 pm Post subject:

Starflyer Alien · Posted: Tue Sep 05, 2006 4:18 pm Post subject:

We're going off topic here. we should move this elsewhere...
and I'd like to see that DIC... I've tried real hard to find one for [r8c5]<>2.
There's a really nice one for [r2c2]=5,

daj95376 · Posted: Tue Sep 05, 2006 5:08 pm Post subject:

I disabled HTML and BBcode. So, the DIC may not be pretty but it will at least list properly.

[r8c8]=2 => [r8c5]<>2

[r3c8]=2 => [r12c5]=2 => [r8c5]<>2
-or-
[r3c8]=2,[r5c6]=2,[r7c4]=2 => [r8c5]<>2

This isn't the first time a message thread has gone off-topic. It'll survive our short tangent!

Mike Barker · Posted: Tue Sep 05, 2006 7:10 pm Post subject:

A simple Empty rectangle gives the elimination: