Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Colors Redefined: X-Ray Colors. Multicolors obsolete??

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
TheSpaniard

Joined: 28 Aug 2006
Posts: 20
:
Location: Spain

Items
PostPosted: Mon Aug 28, 2006 1:57 pm    Post subject: Colors Redefined: X-Ray Colors. Multicolors obsolete?? Reply with quote

Good day. I am new to this Forum (actually, I am new to ALL Forums).
First, my mothertongue is not English (Spanish, actually), so I apologize in advance if I make mistakes.
Second: I am afraid this post will be a little long, but I need space to explain the new technique: X-Ray Colors.

Several months ago, I accidentally discovered one very powerful technique, that I have used many times with very good results when I solve Sudokus.
Since a couple or two of weeks I have read many of the posts in this forum (that is The Forum where new solving techniques and strategies are shown, shared and discussed) trying to realize that someone has already defined and formalised "my" technique... and I haven't found it. That's surprising for me, since you usually discuss techniques that I can hardly understand (IF I can), but I have no found evidence of this technique.
That's the reason why I decided to publish "my" technique to your exam. Here is: X-Ray Colors (that's the war-name I use for it, although I am convinced that it is simply an extension to "Colors").

The rule definition would be something like:
"Given a cell RxCy that forms part of a conjugate pair of cells (or a chain of conjugates) coloured with colors "A" and "B", and assuming that the cell RxCy is coloured with Color "A", then NONE of the peers (row, column, box) of this cell will have the same colour "A".
Then, ALL THE CELLS that, excluding all the peers of that cell RxCy, REMAIN ALONE in one row, column or box WILL HAVE THE SAME COLOR "A" than the originating cell RxCy".

I am sure that the definition can be improved, both in formality and understandability; that's the better I have got.

Example: (MMMM, How can I insert images??)
(and... How can I set text font to "Courier"?)
Code:

 *-----------*
 |..5|4..|..7|
 |.4.|87.|..5|
 |187|.56|4.2|
 |---+---+---|
 |2..|718|564|
 |816|524|973|
 |754|..3|..1|
 |---+---+---|
 |.7.|.85|146|
 |5.1|.49|7.8|
 |4.8|1.7|.59|
 *-----------*


Looking to candidate "3", and marking colors (Green, Blue), we have:

Code:

 *----------------------------------------------------------*
 | 369   2369  5     | 4    *39G   12    | 368   1389  7    |
 | 369   4     239   | 8     7     12    | 36    139   5    |
 | 1     8     7     |*39B   5     6     | 4    *39B   2    |
 |-------------------+-------------------+------------------|
 | 2     39    39    | 7     1     8     | 5     6     4    |
 | 8     1     6     | 5     2     4     | 9     7     3    |
 | 7     5     4     | 69    69    3     | 28    28    1    |
 |-------------------+-------------------+------------------|
 | 39    7     239   | 23    8     5     | 1     4     6    |
 | 5     236   1     | 236   4     9     | 7    *23X   8    |
 | 4     236   8     | 1    *36B   7     | 23    5     9    |
 *----------------------------------------------------------*


In this example, look at the cell R9C5 (Blue). If we look now at box 9 (lower-right), we see that has only two cells (R8C8, R9C7) that are conjugate, but they doesn't form part of the conjugate chain marked blue-green, because the cell R9C2 avoid it. But, applying "X-Ray Color" (the new technique) we see that this cell R9C5 avoids the cell R9C7 to be
blue... so the only cell in box 9 that can be blue is R8C8 (marked "X"). That's this way because R9C8 is the ONLY REMAINING CELL in box 9 when we eliminate the peers of R9C5, marked blue. We then mark R8C8 as blue, and then R1C8 and R2C8 can be safely removed.

In the same position, looking to cell R3C8, and applying "X-Ray Color" to box 9, we see that R8C8 cannot be Green, so the Green cell inbox 9 is, then, R9C7. We can then safely exclude the candidate 3 from R9C2.

In the same position, Multicolors would find the same exclusions... But X-Ray-Colors is much, much simpler to spot.
In my experience using this technique and comparing it with multicolors, EVERY position in which Multicolors can be applied to exclude some candidate, is suitable too to apply X-Ray Colors, with the same result.
I DOES NOT ASSURE that "There is NO position in which multicolors (in all of their flavors: Ultracolors, Advanced Colors, or whatever Colors) can solve a position that X-Ray cannot"; I only say that I have never found one case in several months.

AND, X-Ray Colors can exclude candidates in some positions (that I find regularly) where Multicolors can not. That fact is because Multicolors needs several chains of conjugates, while X-Ray only needs one. Let's see an example:

Code:

 *-----------*
 |14.|.8.|.9.|
 |..8|.42|1.6|
 |...|3..|4.8|
 |---+---+---|
 |..1|...|6.9|
 |..9|.2.|8..|
 |4.6|...|3..|
 |---+---+---|
 |9.7|..4|...|
 |8.4|13.|9..|
 |.1.|.9.|..4|
 *-----------*


Looking to the candidate "7", we have:

Code:

 *---------------------------------------------------------------------*
 | 1      4       235   | 567    8      567Y    | 257G   9       2357  |
 | 357    3579    8     | 579    4      2       | 1      357     6     |
 | 2567   25679   25    | 3      1567   15679   | 4      257     8     |
 |----------------------+-----------------------+----------------------|
 | 2357   23578   1     | 4578   57     3578    | 6      2457    9     |
 | 357    357     9     | 4567   2      13567   | 8      1457    157   |
 | 4      2578    6     | 5789   157    15789   | 3      1257    1257  |
 |----------------------+-----------------------+----------------------|
 | 9      2356    7     | 2568   56     4       | 25     123568  1235  |
 | 8      256     4     | 1      3      567X    | 9      2567    257   |
 | 2356   1       235   | 25678  9      5678    | 257B   235678  4     |
 *---------------------------------------------------------------------*


In this position there is only one pair of conjugate cells (R1C7 and R9C7, that are the only cells with candidate 7 in column 7; there are not any other conjugate pair in "7's" in this position). So, multicolors are unuseful here.
But X-Ray-Colors applied in this position makes R8C6 (with the "X" in the diagram) marked with the same color than R9C7 (Blue), due to the fact that all the rest of the cells of box 8 (lower center) cannot be blue, because R9C7 is blue and avoids R9C4 and R9C6 be the same color; then, the only cell of box 8 that can be blue is R8C6; so, it is Blue. You can then safely exclude candidate 7 from R1C6 (marked with "Y").


In my modest opinion, subject to verification by this Forum members or anyone else, X-Ray-Colors is only an extension to the standard Colors technique (it only needs two colors) and gives the same results than all Multicolors techniqueS in a much more simpler way; even more, it can find exclusions in positions where multicolors cannot.

Resuming:

Pros:
1) X-Ray Colors only needs two colors to use, not four or even more, like in Multicolors are needed.
2) It finds the same exclusions that every flavour of Multicolors find (subject to verification).
3) It finds exclusions in positions where Multicolors can not.
4) As it is only one extension to the standard Colors Technique (is not more than a way to give a color to some cell according with the same two colors used in the standard Colors technique), and assuming that the assertion number 2 is true, then IT ELIMINATE THE NEED OF MULTICOLORS TECHNIQUES IN SOLVING ALGORITHMS.

Cons:
1) It needs mathematical verification of its validity as technique. As I don't have this mathematical background, I ask the help of people that can do this verification.

Hopefully, this post should be of interest to you.

Best Regards.

Ruud: enabled BBCode and added code tags
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Mon Aug 28, 2006 4:18 pm    Post subject: Reply with quote

Hi Spaniard,

First: Using my moderator powers, I've edited your post, so the grids are now placed between code tags. To make them work, I also had to enable BBCode. To embed images, you upload the image to a webhost (like ImageShack.us) and place a hyperlink to it between img tags.

On topic then.

I found an error in your first candidate grid, where R3C8 should have a G mark (it's green, not blue).

Actually, you will not find anything in this forum that looks like X-Ray coloring. But David P Bird has introduced this on another forum as weak colouring. Follow the link to an interesting discussion which keeps drifting off topic.

As I already explained to David, this technique is a bifurcative version of Nishio. In example 2, consider what would happen when you place digit 7 in R1C6. It would lead to the situation where R8C6 is forced to 7, which eliminates R1C6. Can't have a candidate that eliminates itself.

I like David's suggestion to use lighter shades for weak inferences.

cheers,
Ruud
Back to top
View user's profile Send private message Visit poster's website
TheSpaniard

Joined: 28 Aug 2006
Posts: 20
:
Location: Spain

Items
PostPosted: Mon Aug 28, 2006 4:54 pm    Post subject: Reply with quote

Thank you, Ruud, both for replying my post, and to correct the format, I am new to editing html.

Yes, you're right, I made a mistake transcribing the images of the first example, this column R3C8 is, obviously, Green. Thanks again.

On the subject, I think you're not right.

I am not speaking of "weak" conjugates. There are "strong" conjugates.
When, in the second example I say that R8C6 is Blue, I am not saying that "it can be Blue". IT IS BLUE. So, the candidate 7 in R1C6 is immediatly and safely eliminated. No guessing at all.

And I think this technique has nothing similar to Nishio. Nishio is very close to "trial and error", and is very very difficult to spot by human players.
X-Ray Coloring is very simple, and produces the safe elimination of the victim without any extra condition. In fact, I am convinced it is only an extension to the standard "Colors".

One example, in your (excellent) Solving Guide, when you explain "Empty Rectangles or Hinge", you mention that "Daily Nightmare" of August the 25th is a good example of that. It is not.
I have solved this Sudoku ONLY with the easy techniques (exclusion, pairs, triples, etc) AND ONLY X-Ray. You can check it, if you want. Even more, most of these Nightmares can be solved using standard "easy" techniques and Colors-X-Ray Colors.

The important thing is that maybe (only maybe, by the moment) we are in front of one simple technique that can change our vision of the Color technique. If, after all, it is unuseful, at least will be funny to take a look on it.

Thank you again, and my congratulations, both for the forum and for your personal page.

Cheers
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron