| View previous topic :: View next topic |
| Author |
Message |
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
 Posted: Wed Oct 19, 2005 3:45 pm Post subject: "Coloring technique" examples |
 |
|
Hi,
I have some "coloring" technique examples.
I mean dealing with the remaining numbers of the same kind, and trying to find out if there are some that can be eliminated.
I found out that, if in the candidate table we have 15, 17 or 19 occurances of the same number, than it is a good probability that at least one could be eliminated.
Anybody interested in some examples?
Do you also have such ones?
see u, |
|
| Back to top |
|
 |
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Wed Oct 19, 2005 4:07 pm Post subject: "Coloring" examples |
|
|
Yes, I'd like to see some examples.
What I understand about "coloring" (so far!) is that sometimes we can find a chain of cells that only has two possible placements for a particular value in each of several rows, columns, or 3x3 boxes. So we may be able to label alternative "links" in the chain as, say, either green or blue.
If the chain leads back to itself, so that we get two green cells in the same row, or column, or 3x3 box, then we know that green is false and blue is true, for instance. Or we may be able to line up both a green cell and a blue cell with another cell (not in the chain) which can then be eliminated as a candidate for the value we're tracing.
Is that about it? Or have I missed something? dcb |
|
| Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Thu Oct 20, 2005 7:02 am Post subject: |
|
|
Hi David,
You explained a technique using colors, so it MUST be a coloring technique. I can not argue against.
If you reduce your description to deal with only ONE number that this is also a coloring technique. This one I ment.
BTW (By The Way), there are circulating also names like:
"multi-coloring"
"super-coloring"
"ultra-coloring"
at least if not more.
Maybe you know what is the difference between them.
Next question: What is the difference between "Nishio" and "coloriung"?
Is there not a case that does the same, and the technique is called ones "NIshio" and the second time "coloring" (because a color was used)?
Is there an example of "NIshio" that can't be solved with "coloring" ?
And one with "coloring" that can't be solved with "Nishio" ?
OK, to be back to USSA, I will look and prepare some examples I have with "coloring involving only one number".
see u, |
|
| Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Thu Oct 20, 2005 10:13 am Post subject: |
|
|
Hi,
Here one with "coloring for one number" which is pretty simple:
| Code: |
508030000
300700000
000000000
100000085
040607000
000200000
000080030
020000700
000000600 |
that should get you to:
| Code: |
5 7 8 19 3 4 19 2 6
3 19 6 7 2 5 8 19 4
2 19 4 8 6 19 5 7 3
1 6 7 39 4 39 2 8 5
8 4 2 6 5 7 3 19 19
9 3 5 2 1 8 4 6 7
7 5 19 4 8 6 19 3 2
6 2 13 5 9 13 7 4 8
4 8 139 13 7 2 6 5 19 |
Nr=1 occurs=15
Nr=3 occurs=6
Nr=9 occurs=14
And dealing with "1" is now a pice of cake.
This was a simple one, I agree.
see u, |
|
| Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Thu Oct 20, 2005 10:17 am Post subject: |
|
|
Here an other one:
| Code: |
000032400
501000000
000000000
000170050
020060000
000500000
040000200
000000306
800700000 |
which should bring you to:
| Code: |
6 7 89 89 3 2 4 1 5
5 3 1 4 89 7 6 2 89
2 89 4 6 1 5 789 3 789
3 89 6 1 7 4 89 5 2
79 2 5 3 6 89 1 789 4
4 1 789 5 2 89 789 6 3
1 4 3 89 5 6 2 789 789
79 5 79 2 48 1 3 48 6
8 6 2 7 49 3 5 49 1 |
And we have:
Nr=4 occurs=4
Nr=7 occurs=10
Nr=8 occurs=19
Nr=9 occurs=22
So according to my strategy, I would start with coloring for "8".
And indeed you will be successful with it.
see u, |
|
| Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Thu Oct 20, 2005 10:22 am Post subject: |
|
|
an other one:
| Code: | 600030000
004000050
010000080
000108000
300000200
000500000
050700000
000040300
000000609 |
will lead you to:
| Code: | 6 79 8 4 3 5 1 29 27
27 3 4 29 8 1 79 5 6
5 1 29 269 69 7 4 8 3
247 2679 2679 1 269 8 5 3 47
3 8 5 69 7 4 2 69 1
1247 2679 12679 5 269 3 79 469 8
9 5 3 7 1 6 8 24 24
127 267 1267 8 4 9 3 17 5
8 4 17 3 5 2 6 17 9 |
With the following statistic:
Nr=1 occurs=7
Nr=2 occurs=19
Nr=4 occurs=6
Nr=6 occurs=13
Nr=7 occurs=18
Nr=9 occurs=17
Again according to my strategy, I will start with "9" and when not successfull will try "2". But dealing with "9" should be enough.
Hope you enjoy them, |
|
| Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Thu Oct 20, 2005 10:28 am Post subject: |
|
|
Just an other example to show how successfull my strategy is, when it is successfull ;-)
Starting from:
| Code: | 003070000
600000002
000040000
000700130
200000000
000000070
010000340
000208000
000600500 |
you should get to:
| Code: | 59 28 3 59 7 26 4 68 1
6 4 1 3 8 59 7 59 2
7 2589 58 1 4 26 68 59 3
459 68 68 7 2 59 1 3 459
2 3 7 4 59 1 68 68 59
1 59 45 8 6 3 2 7 459
8 1 2 59 59 7 3 4 6
45 56 456 2 3 8 9 1 7
3 7 9 6 1 4 5 2 8 |
with the statistic:
Nr=2 occurs=4
Nr=4 occurs=6
Nr=5 occurs=20
Nr=6 occurs=10
Nr=8 occurs=9
Nr=9 occurs=15
Again, if my strategy works, than I have to start with "9". And it works.
Bad news is that sometimes it works, but the puzzle is not solved. Only elimination of a sigle number from the candidate table is not making a decisive move for solving. I still can be stucked without any furthe clue.
see u, |
|
| Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Thu Oct 20, 2005 10:36 am Post subject: |
|
|
Now an negative example.
For the following puzzle:
340600000
007000000
020090570
000005000
070010020
000400000
068020010
000000300
000007092
I can get up to:
3 4 5 6 7 1 2 8 9
1689 189 7 2 5 348 146 346 1346
168 2 16 38 9 348 5 7 1346
124689 1389 123469 7 368 5 14689 346 13468
4568 7 346 89 1 689 468 2 34568
15689 13589 1369 4 368 2 16789 356 135678
4579 6 8 359 2 39 47 1 457
124579 159 1249 1589 468 689 3 456 45678
145 135 134 158 468 7 468 9 2
having a disaster statistic:
Nr=1 occurs=25
Nr=2 occurs=4
Nr=3 occurs=22
Nr=4 occurs=27
Nr=5 occurs=17
Nr=6 occurs=30
Nr=7 occurs=7
Nr=8 occurs=28
Nr=9 occurs=20
The good news is that if you work on the "5" you can eliminate one occurence. The bad news is that this will not be an essential move in the direction of the solution. Maybe with a different technique you will break it and this small move will not be necessary.
Any sugestion is wellcomed!
see u, |
|
| Back to top |
|
|
alanr555
Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39
|
| Posted: Thu Oct 20, 2005 10:33 pm Post subject: Re: "Coloring technique" examples |
|
|
| Code: |
> I have some "coloring" technique examples.
> I mean dealing with the remaining numbers of the same kind, and
> trying to find out if there are some that can be eliminated.
> I found out that, if in the candidate table we have 15, 17 or 19
> occurences of the same number, than it is a good probability that at
> least one could be eliminated.
It was good to have the examples - but what is one supposed to DO with
them. I recall some reference to blue and green cells interacting or not
but do not recall any specific details of the mechanics of the process.
What are "numbers of the same kind" mentioned above? The digits 1-9
being all integers with only one digit in the decimal system would suggest
that ALL those nine digits are "numbers of the same kind" - so there MUST
be some more arcane definition!
It is fine that colouring can find out if some can be eliminated. Given the
axiom that the puzzle has a unique solution, it should already be know
that some can be eliminated - the question is which and, especially, HOW?
Alan Rayner BS23 2QT
|
|
|
| Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Fri Oct 21, 2005 7:32 am Post subject: |
|
|
Hi Alan,
My english is unfortunate not my first and not even my second language ;-)
Yup, you are right. Using the term "digit" is accurate.
But, back to USSA, ... as the song was suggesting ...
I supplied the example for who wants to try the "coloring of a digit" technique, I described before.
Did you tried one of the examples?
I am interested about constructive remarks and tipps that would reduce my set of unsolved Sudoku puzzles.
see u, |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Fri Oct 21, 2005 5:23 pm Post subject: Re: Examples of "Coloring" |
|
|
| AlanR555 wrote: | | It was good to have the examples - but what is one supposed to DO with them. I recall some reference to blue and green cells interacting or not but do not recall any specific details of the mechanics of the process. |
You might be so kind as to refresh your memory by looking here and here and even over here.
Our friend someone_somewhere has provided an excellent example. Let's analyze it, and illustrate the technique again that way.
| Code: | 5 7 8 19 3 4 19 2 6
3 19 6 7 2 5 8 19 4
2 19 4 8 6 19 5 7 3
1 6 7 39 4 39 2 8 5
8 4 2 6 5 7 3 19 19
9 3 5 2 1 8 4 6 7
7 5 19 4 8 6 19 3 2
6 2 13 5 9 13 7 4 8
4 8 139 13 7 2 6 5 19 |
You will notice that the value "1" has been entered in two places at this point -- at r4c1 & r6c5. So there are 7 more "1"s remaining to be placed. But looking at the "candidate" cells where "1" appears to be a possibility, you will also notice there are 15 of those. So this pattern of "1"s is inherently unstable. If there were exactly 2 possibilities for a "1" in each of 7 rows (and columns), we would have to look elsewhere for a clue. But we may be able to isolate the odd man out just by concentrating on the "1"s.
Let's start the analysis at r1c4. (One could start anywhere, but this happens to be a good choice that gets the answer with just a few steps). We follow two chains of inference:
r1c4 = 1 ==> r1c7 is not 1 ==> r2c8 = 1 ==> r5c8 is not 1 ==> r5c9 = 1 ==> r9c9 is not 1
r1c4 is not 1 ==> r1c7 = 1 ==> r2c8 is not 1 ==> r5c8 = 1 ==> r5c9 is not 1 ==> r9c9 = 1
Because of the binary chain of "1"s that leads along row 1, through the top right 3x3 box, down column 8, along row 5, and down column 9, we can be certain that either there is a "1" in r1c4, or else there is a "1" in r9c9. Either way there _cannot_ be a "1" in r9c4. So we can place a "3" in that cell and go merrily on our way.
People call this sort of analysis "coloring" because an easy way to visualize it is to mark the cells in the binary chain with two different colors, say blue and green. In this example one might color r1c4, r2c8, & r5c9 blue, and r1c7, r5c8, & r9c9 green. The fact that a "1" is impossible at r9c4 would then become apparent by observing that it is in line with both a blue cell and a green cell. dcb |
|
| Back to top |
|
|
alanr555
Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39
|
| Posted: Fri Oct 21, 2005 5:32 pm Post subject: |
|
|
| Code: |
> English is not my first and not even my second language.
Native English speakers are at a disadvantage. Which language should
they choose as a second one? It is different in other countries but has
been dependent upon politics. For example old Hungarians (Magyars)
speak German second, Middle-age speak Russian second but the young
people speak English second. Should English people speak French or
Spanish or German (or Latin as when I went to school) as their second
language? For a lot of people in USA a good choice is Spanish and this
is an increasingly taken option in Britain but which is most useful? The
only thing that we can say is that there is a definite change in the mindset
of those who have learned to communicate in another language. However
my problem is "thinking in Serbian" and "speaking Spanish" when I am
in France. Sadly it is all so foreign - Une tasse de the, por favor!
My first language is English
Moj drugi jezik je taj od Srbije.
Mi treca lengua es lo de Espana
Numero quatre est francais
I do not do well in any of them except the first!
+++
> I supplied the example for who wants to try the "coloring of a digit"
> technique, I described before.
> Did you try one of the examples?
No - because I do not know what is involved in using the technique.
It seems to involve colouring cells blue and green alternately but why
or in what sequence I have no idea. What factor links each cell in the
chain, how is the next cell chosen?
If anyone other than djb is to try the examples, a reeat of the rules for
applying the technique will be needed.
> I am interested about constructive remarks and tipps that would reduce > my set of unsolved Sudoku puzzles.
I would be pleased to contribute, if I understood the technique.
Alan Rayner BS23 2QT
|
|
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Fri Oct 21, 2005 6:50 pm Post subject: Example where coloring isn't enough |
|
|
| Someone_Somewhere wrote: | I can get up to:
| Code: | 3 4 5 6 7 1 2 8 9
1689 189 7 2 5 348 146 346 1346
168 2 16 38 9 348 5 7 1346
124689 1389 123469 7 368 5 14689 346 13468
4568 7 346 89 1 689 468 2 34568
15689 13589 1369 4 368 2 16789 356 135678
4579 6 8 359 2 39 47 1 457
124579 159 1249 1589 468 689 3 456 45678
145 135 134 158 468 7 468 9 2 |
|
I don't think there's a logical way to solve this one -- I think you have to guess.
Anyway, I do have a couple of suggestions. Putting a "5" at r8c1 would force one to place "5"s at r6c2 & r5c9, thus making it impossible to place a "5" in the lower right 3x3 box. So r8c1 is not a "5".
You can learn a little by looking at "6". Putting a "6" at r5c7 would force one to place a "6" at r8c6, making it impossible to put a "6" in the lower right 3x3 box. So r5c7 is not a "6".
That's about as far as I can get without making an outright guess. This one makes my head swim! dcb |
|
| Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Fri Oct 21, 2005 6:54 pm Post subject: |
|
|
Hi Alan,
I think that you should take a look at the following page:
http://www.simes.clara.co.uk/programs/sudokutechniques.htm
where the basic and advanced techniques are shown.
Than you should try some of the examples I have posted.
If you still have questions, please don't hesitate, put them.
P.S. the intersection of your languages with my ones gives the unique element "english".
see u, |
|
| Back to top |
|
|
alanr555
Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39
|
| Posted: Sat Oct 22, 2005 10:11 pm Post subject: |
|
|
| Code: |
Thank you for the links to other contributions.
Two of them are about the implications of coluring and the only one with
any form of description is David's piece as below. However, he seemed to be uncertain as to the validity of the method (or maybe just the name??).
I have an example and I have identified the cells and digits where a digit
occurs EXACTLY twice on a line. I presume that this is the first stage.
What happens to the other cells containing that digit (eg those where
there are three cells with the digit on a line)?
> What I understand about "coloring" (so far!) is that sometimes we can > find a chain of cells that only has two possible placements for a
> particular value in each of several rows, columns, or 3x3 boxes. So we > may be able to label alternative "links" in the chain as, say, either
> green or blue.
> If the chain leads back to itself, so that we get two green cells in the
> same row, or column, or 3x3 box, then we know that green is false and > blue is true, for instance. Or we may be able to line up both a green cell > and a blue cell with another cell (not in the chain) which can then be
> eliminated as a candidate for the value we're tracing.
My example leads to the following candidate profile - where a hyphen
represent a value already resolved.
- - 24 / 345 45 - / - - 234
- - 47 / - - 347 / - 45 345
- - 247 / 47 18 18 / - - 24
- 456 - / - 456 46 / - - -
- 456 - / 457 1456 1467 / 45 - -
- 45 - / - - - / - 45 -
- - - / 24 - - / 24 - -
- - - / 234 - 34 / 245 - 45
- - - / - 68 68 / - - -
From this all the values of 1,2,3,7,8 form "circular" chains
(eg 2 in r1c3,r1c9,r3c9,r3c3 and r7c4,r7c7,r8c7,r8c4)
They all occur just twice in a line and any alternate colouring would
result in a consistent chain (ie green returns to green) but there are no
other occurrences of '2' and so this may not be a valuable exercise.
Digit 4 occurs "twice in a line" in only two places (row6 and col 8)
They do not form a "closed" chain.
Can colouring reveail any useful information about the '4's?
The digit '5' is perhaps more interesting.
There are Twelve occurrences of it where it forms one of a pair in the
same line. There are also TWO occurrences where the '5' is NOT part
of a such a pair. These "outcasts" are in r5c2 and r5c5.
Does the coluring method imply that these two outcasts can be removed
from further consideration? Even having removed the '5' from those two
locations, the puzzle does not seem to be progressed very far!
Digit '6' appears in two pairs that do not intersect. Thus, I do not see that
any new information can be acquired for this digit. The pairs are r4c2 with
r6c2 and r9c5 with r9c6.
+++
This puzzle appears to have "all-congruent" candidate profiles (ie there
are as many distinct digits in each row/column/region as there are cells
needing to be resolved. There is a hidden pair (18) in row 3 but this does
not appear to lead to a quick resolution of any other cells.
Thus, how would one proceed?
The original puzzle was raised in a topic on the subject of "slight variation
on Uniqueness" rather than colouring but I have used it in order to get a
proper understanding of the HOW of colouring. The full grid was
080 / 000 / 700
010 / 620 / 000
530 / 000 / 090
000 / 800 / 030
009 / 000 / 028
000 / 900 / 006
070 / 005 / 001
106 / 070 / 080
020 / 000 / 070
which reduces (by my reckoning) to
680 / 009 / 710
910 / 620 / 800
530 / 000 / 690
201 / 800 / 937
309 / 000 / 028
708 / 932 / 106
873 / 095 / 061
196 / 070 / 080
425 / 100 / 379
I am now stuck on this one - any ideas on progress would be welcome.
Alan Rayner BS23 2QT
|
|
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Mon Oct 24, 2005 3:41 pm Post subject: Coloring doesn't work on this one |
|
|
| AlanR555 wrote: | | I am now stuck on this one - any ideas on progress would be welcome. |
Coloring won't work on this one, Alan. Or at least, I couldn't get it to work.
| Code: | - - 24 / 345 45 - / - - 234
- - 47 / - - 347 / - 45 345
- - 247 / 47 18 18 / - - 24
- 456 - / - 456 46 / - - -
- 456 - / 457 1456 1467 / 45 - -
- 45 - / - - - / - 45 -
- - - / 24 - - / 24 - -
- - - / 234 - 34 / 245 - 45
- - - / - 68 68 / - - - |
I did find a way to resolve the puzzle, involving "forcing chains." Some people would call it trial and error, I suppose. Anyway, this was the best I could do.
There are only two places a "4" can fit in column 8. Suppose that r2c8 = 4. Then the following moves are forced:
r2c8 = 4 ==> r2c3 = 7 ==> r2c6 = 3 and also r2c8 = 4 ==> r8c9 = 4 ==> r8c6 = 3
This contradiction (can't have two "3"s in column 6) proves that r2c8 is not 4, and therefore r2c8 = 5. dcb |
|
| Back to top |
|
|
alanr555
Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39
|
| Posted: Tue Oct 25, 2005 1:34 am Post subject: Re: Examples of "Coloring" |
|
|
> Our friend someone_somewhere has provided an excellent example.
> Let's analyze it, and illustrate the technique again that way.
Apologies for not responding to this one earlier. It was submitted nine
minutes before my contribution. One is liable to miss something that is
in the future when when one downloads but in the past when one uploads
the response to an earlier message.
| Code: |
5 7 8 19 3 4 19 2 6
3 19 6 7 2 5 8 19 4
2 19 4 8 6 19 5 7 3
1 6 7 39 4 39 2 8 5
8 4 2 6 5 7 3 19 19
9 3 5 2 1 8 4 6 7
7 5 19 4 8 6 19 3 2
6 2 13 5 9 13 7 4 8
4 8 139 13 7 2 6 5 19 |
> You will notice that the value "1" has been entered in two places at this > point -- at r4c1 & r6c5. So there are 7 more "1"s remaining to be
> placed. But looking at the "candidate" cells where "1" appears to be a
> possibility, you will also notice there are 15 of those. So this pattern
> of "1"s is inherently unstable. If there were exactly 2 possibilities for
> a "1" in each of 7 rows (and columns), we would have to look
> elsewhere for a clue. But we may be able to isolate the odd man out
> just by concentrating on the "1"s.
Fascinating analysis. It just goes to shew that a simple 9x9 grid has a
real wealth of "hidden" properties. This concept of "inherent instability"
is not something of which I would have thought previously. Indeed it is
only fairly recently that I considered counting the frequency of the
initial cell populations.
> Let's start the analysis at r1c4. (One could start anywhere, but this
> happens to be a good choice that gets the answer with just a few
> steps). We follow two chains of inference:
r1c4 = 1 ==>
r1c7 is not 1 ==>
r2c8 = 1 ==>
r5c8 is not 1 ==>
r5c9 = 1 ==>
r9c9 is not 1
r1c4 is not 1 ==>
r1c7 = 1 ==>
r2c8 is not 1 ==>
r5c8 = 1 ==>
r5c9 is not 1 ==>
r9c9 = 1
I understand the concept of binary chains. My thoughts then turn to the
"Why?" when selecting particular chains.
It would appear that any binary chain which is restricted to rows and
columns as the links CANNOT create the elimination effect as the number
of steps to reach the target square will always have the same parity.
Here r1c4 to r9c4 can be reached in one step and ANY other route on
just rows and columns would add two steps or a multiple of two steps -
thus preserving the parity.
In order to change the parity, there must be a route involving at least
one diagonal. In fact it can be shewn that such a route must have an
ODD number of diagonal links. The example has one with r1c7 to r2c8.
Here a "diagonal" is any link within a box/region that is NOT also a link
along the line of a row or column.
It would seem reasonable to suppose that any elimination must be of
a candidate in a row/column/region with more than two occurrences of
the candidates. Otherwise it would be part of a binary chain and so not
eligible for elimination - BUT only one of its 'dimensions' need be other
than two (eg r9c4 has two in column and two in region but the three in
row makes it eligible for elimination.
+++
Thus the methodolgy for human solvers becomes
a) Identify any row/column/region with more than two occurrences of
the target digit as candidate.
(In our example row 9 or column 3)
b) From the cells containing the target digit, identify those which have
a binary link to another cell.
(In our example, this would exclude r9c3 as it has no binary links)
c) Select any pair from the cells identified at (b)
(in our example this means r7c3/r8c3 or r9c4/r9c9)
d) Select a simple (ie one-step) binary link from either of the two cells
in the pair and call the other end of the link the 'target' cell.
(In our example say r9c4 to r8c6)
e) Search for a route from the OTHER selected cell (of the pair in (c))
and trace a route - USING BINARY LINKS ONLY - from that cell to
the target cell. If a route can be found with an ODD number of links
then one of the pair of cells in (c) is eligible for elimination.
Here it is useful to remember that the route should use an ODD number
of diagonal links (ie binary links not in a single row or column).
(in our example the route is r9c9, r5c9, r5c8, r2c8 and then we want to
use the diagonal link. If we do so there is NO route back to r8c6 but
this gives us the clue that we need to use a different one-step link at
stage (d). There are a maximum of TWO possible binary links and so
this trial process is not unduly onerous.
If we try the link from r9c4 to r1c4 as a one step link, we can continue
the route from r9c9 from r2c8 with r1c7 and r1c4. This gives FIVE
links and so we have proved an inconsistency in the candidate profiles)
f) The question remaining is then which occurrence to eliminate.
If we call the pair selected at step (c) say P and Q and the target cell
selected at (d) - or possibly re-selcted at (e)! as R, we know.
If R is our selected digit then P is not and also Q is not.
If R is NOT our selected digit then P must be it AND also Q must be it.
These conclusions arise because there is an ODD number of steps in
each case (ie the truth/falsehood is opposite at each end whereas
an even number of steps would prove them to be the same).
Given this logical result, we know that P and Q can NEVER hold the
same digit and so cell R is the one that MUST be our digit. As soon as
this is recognised, there is immediate resolution of half the cells in
the binary chain used.
In this example r1c4 MUST take value 1 and BOTH of r9c4 and r9c9
can be eliminated - leaving r9c3 as the only cell eligible to be value 1.
+++
This result is much more far-reaching than that derived by djb previously
(quoted below) and I would appreciate confirmation of my logic.
> Because of the binary chain of "1"s that leads along row 1, through the
> top right 3x3 box, down column 8, along row 5, and down column 9, we
> can be certain that either there is a "1" in r1c4, or else there is a "1" in
> r9c9. Either way there _cannot_ be a "1" in r9c4. So we can place a "3"
> in that cell and go merrily on our way.
My belief (derived above) is that this is only PART of the resolution. While
it is true that we can set r9c4 to 3, I believe that ALSO we can set r9c3
to 1 and r9c9 to 9 - all as a result of the "colouring".
Using my rules as above, it would be possible to shew that there is an
inconsistency in column 3 so that r7c3 becomes 9, r8c3 becomes 3 as
well as confirming that r9c3 MUST be 1 and r8c6 and r7c7 must also be 1
(plus r2c8 and r5c9 and r3c2 as intermediate members of binary chains)
while digit 1 can be eliminated from r1c7,r2c2, etc as a 'forcing chain'.
> People call this sort of analysis "coloring" because an easy way to
> visualize it is to mark the cells in the binary chain with two different
> colors, say blue and green. In this example one might color r1c4, r2c8,
> & r5c9 blue, and r1c7, r5c8, & r9c9 green. The fact that a "1" is
> impossible at r9c4 would then become apparent by observing that it is
> in line with both a blue cell and a green cell.
If my logic above is correct, the concept of 'colouring' may be slightly
counter-productive in that it focusses on the result in one cell. Taking
the power of binary logic (either it is or it is not!) then far more may be
able to be gleaned.
My approach above started out as an attempt to assist identification of
potential situations for colouring and so I have been quite surprised at
the conclusion.
In summary, my approach does not depend upon "colouring" at all.
1) Identify the potential for elimination - being the presence of more
then two occurrences of the target digit in candidate profiles in any
row/column/region but with at least one binary link in one of the
other two dimensions for at least two of the cells.
2) Test the potential eliminees pairwise by demonstrating that one of
the pair can be linked in a one-step binary chain to another cell
and that the other member can be linked in a binary chain to the
SAME cell with an ODD number of steps - taking note in practice that
this will require an odd number of "diagonal" binary links.
3) If this situation is found, the "other" cell can be set to the digit being
considered and BOTH of the pair being tested can have the target digit
removed from their candidate profiles.
In conclusion, this would seem to be a very powerful technique. The work
done by our friend in Munchen is immensely valuable in identifying when
it might be useful to try the technique; our friend in Colorado has given
us the logical basis for colouring and, if my contentions above are true,
we now have a more extensive resolution where the 'colouring' outcome
is proven to exist.
Alan Rayner BS23 2QT |
|
| Back to top |
|
|
alanr555
Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39
|
| Posted: Tue Oct 25, 2005 2:15 am Post subject: Re: Coloring doesn't work on this one |
|
|
> Coloring won't work on this one; or at least, I couldn't get it to work.
| Code: |
- - 24 / 345 45 - / - - 234
- - 47 / - - 347 / - 45 345
- - 247 / 47 18 18 / - - 24
- 456 - / - 456 46 / - - -
- 456 - / 457 1456 1467 / 45 - -
- 45 - / - - - / - 45 -
- - - / 24 - - / 24 - -
- - - / 234 - 34 / 245 - 45
- - - / - 68 68 / - - -
|
Following my recent work on "colouring", I would concur with the above conclusion. My reasoning is
a) For colouring to be useful there need to be some rows/columns/regions
with more than two occurences of cells containing the specific digit in
their candidate profiles. Further at least two of the occurences need
to have a binary link in one of their other 'dimensions' for the said
digit.
b) Only the 4 and 5 digits have other than binary links.
c) None of the rows/columns/regions containing more than two instances
of '4' in their profiles have more than one occurence where one of the
other dimensions has a binary link on '4'.
d) Digit 5 has potential for elimination in row 5 and column 2. In order for
this potential to be realised it must be possible for chains leading from
the possible eliminees to meet at some point. Inspection reveals that
they do not - in that the chain runs out when a binary link intersects
with a row/column/region which has only ONE binary link (although it
may have several multiple links).
> I did find a way to resolve the puzzle, involving "forcing chains." Some
> people would call it trial and error, I suppose. Anyway, this was the
> best I could do.
I am one of those "some people".
I accept a 'forcing chain' in the context where one of the values is proven
so that the others are determined like falling dominoes (cf Laos. Vietnam, Kampuchea etc in the late 1960s and through the 1970s). Where I do not
accept the methodology is where the solver says "Let us try this value".
That is inherently different to things like XY-wing where the proof depends
on such supposition logic but the methodology is such that "if these
conditions apply the value in cell P and absent in cell Q can be eliminated from cell R"
> There are only two places a "4" can fit in column 8. Suppose that r2c8
> = 4. Then the following moves are forced:
> r2c8 = 4 ==> r2c3 = 7 ==> r2c6 = 3 and also r2c8 = 4 ==> r8c9 = 4
> ==> r8c6 = 3
> This contradiction (can't have two "3"s in column 6) proves that r2c8 is
> not 4, and therefore r2c8 = 5.
This would be fine if you could demonstrate that having value "X" (rather
than specifically 4!) in r2c8 would lead to "X" or "not X" in another cell or
to the conclusion that "X" must be in one of a number of specified cells -
but as soon as the postulation is "Try a specific value and see if a
contradiction results" one has crossed a line in my book. As it says on
one website, "trial and error" is the only technique which is guaranteed
to find a solution - eventually. Of course even T&E fans use 'logic' to
reduce the scope for T&E as applying it to 81 cells would be quite a
nonsense (or even to 64 cells if 17 are inital givens!). This is one reason
why I ster clear of the British "Daily Telegraph" puzles and like those
on this site.
So congratulations on getting a solution - but no cheers to the compiler
unless someone can provide a 'logic' method of solution.
Alan Rayner BS23 2QT |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Tue Oct 25, 2005 3:39 pm Post subject: Re: Examples of Coloring |
|
|
| AlanR555 wrote: | It would appear that any binary chain which is restricted to rows and
columns as the links CANNOT create the elimination effect as the number
of steps to reach the target square will always have the same parity. |
Well yes and no, Alan. Coloring is a bit more supple than that. Let me give you an example.
| Code: | . 2? . . . 2? . . .
. . 2? . . . . . 2?
. . 2? . 2? . . 2? .
. 2? . . 2? . 2? 2? .
2? . . . 2? . . . 2?
. . 2? . . 2? . . .
. . . . . . . . .
2? . . . . . . 2? .
. . 2? . . . 2? . 2? |
In this example we can use coloring to deduce that r5c1 = 2. There's a binary chain leading from r4c2 to r1c2 to r1c6 to r6c6 to r6c3. There are no diagonal links in that chain. But since r4c2 and r6c3 both lie in the same 3x3 box, we can see that neither r4c2 nor r6c3 can contain the "2" -- precisely because both cells have the same parity. Or, to use the coloring terminology, r4c2 = r1c6 = r6c3 = green, and r1c2 = r6c6 = blue. We can't have two "true" cells in the same 3x3 box, so green is "false" for "2", and blue must be "true" for 2. (BTW, once a "2" is placed at r5c1 -- or at r1c2 or r6c6 -- all the other "2"s will fall like nine pins.)
This formation has been called a "turbot fish" in another forum -- you can find a good example of that technique in this earlier post.
| AlanR555 wrote: | | This result is much more far-reaching than that derived by djb previously (quoted below) and I would appreciate confirmation of my logic. |
If you say so, Alan. I'm curious -- were you once an engineer? I'm just asking because you apparently want to reduce everything to a (rather complex) formula.
Have a great day! 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
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
