About Colouring

Advanced methods and approaches for solving Sudoku puzzles

About Colouring

Postby Bunnybuck » Tue Aug 09, 2005 10:33 am

Firstly, i just want to clarify that whenever i mention 'colouring' in this post, i am neither referring to colouring as illustrated at angusj's site nor at simes' site. I am referring to a general colouring technique which simply just involves choosing a candidate and follow through its 2 routes as far as you can, removing any possibility which lies on the same shared unit (row, columns, or 3x3 block) thereafter.

Theoretically, it may sound inelegant to some players (esp those anti-forcing-chain users). However whenever i apply colouring, i find it makes perfect logical sense. As some of you know, x-wing, swordfish, turbotfish, even the recently proposed skewed swordfish are applications of colouring in a way. Like how wolfgang put it, "In principle it is the same, just another notation." I must stress that however, colouring does cover those techniques and possibly more. Here's an example:

x-wing vs colouring:
Code: Select all
 6  6  6 | .  .  6 | 6  .  .
 .  .  6 | 6  .  . | .  .  .
 .  .  6 | .  .  . | 6  .  .
---------+---------+---------
 6  6  6 | .  .  . | .  6  .
 6  6  . | .  .  . | .  6  .
 .  .  . | .  .  . | .  .  .
---------+---------+---------
 .  .  . | .  .  . | .  .  .
 6  6  . | 6  .  6 | .  .  .
 .  .  6 | 6  .  . | .  .  .
(puzzle taken from xwing1.sdk)
Upon finding an x-wing on row 2 and 9, you eliminate four 6s on column 3 and 4.

With colouring,
Code: Select all
 6  6 [6]| .  . -6 | 6  .  .
 .  . -6 |+6  .  . | .  .  .
 .  . [6]| .  .  . |+-6 .  .
---------+---------+---------
 6  6 [6]| .  .  . | .  6  .
 6  6  . | .  .  . | .  6  .
 .  .  . | .  .  . | .  .  .
---------+---------+---------
 .  .  . | .  .  . | .  .  .
 6  6  . |[6] . +6 | .  .  .
 .  . +6 |-6  .  . | .  .  .
My chain of thoughts as follow
Case 1:
1) 6 in r2c4
2) 6 in r8c6
3) 6 in r9c3
4) 6 can only be on row 1 in block (1,1) (eliminate 6 in r1c7)
5) 6 in r3c7

Case 2:
1) 6 in r1c6 (or you can start with r2c3 or r9c3 since there are only 2 possibilities on each row for 6s. The result will still be the same)
2a) 6 in r3c7
2b) 6 can only be on column 3 in block (1,1)
3) 6 can only be on row 8 in block (3,1)
4) 6 in r9c4

You would be able to eliminate the same four digits as with the x-wing method and at the same time, fill in the digit 6 in r3c7 upon completion of your application of colouring. Some may argue that hey, after eliminating the four digits, i will be able to see that there are only 1 possible option for 6 in row 3, which is at r3c7. The first advantage of colouring is that it opens up more of the puzzle at the end of your chain of thoughts, as oppose to fixed, defined techniques where u might need to re-examine the puzzle and look for another clue in order to keep you going. I do not plan to go through the comparison with swordfish, turbotfish and skewed swordfish as the concept are the same as the above. But a bit of research and testing will lead you to discover that wherever any of those technique can be applied, colouring can be applied as well.

The second advantage of colouring is that it is a relatively easier technique to apply (imo) as compared to finding a defined pattern. All you need are 2 possibilities of a particular candidate in a row, column or 3x3 block. Start from there and follow the chain.

I'm sure that most, if not all of the sudoku players generate (whether consciously or unconsciously) their own set of algorithm whereby they follow a step-by-step procedure of increasing order of difficulty to solve a puzzle (ie. start looking in puzzle for easiest technique and slowly move up to the more difficult ones). For me, my set of algorithm is simply

i) basic methods (singles, block-row-column elimination, naked pairs/triplets/quads)
ii) solving with 1 candidate involved at a time (ie. colouring)
iii) solving with 2 candidates involved at a time (ie. xy-wing)
iv) solving with 3 candidates involved (ie. xyz-wing)

Many of the hardest puzzles requires only up to ii). Jeff's example in his xyz-wing post which doesn't seem to be able to be solved by simple techniques:
Image
can actually be solved by colouring.

Isolating candidate 4 and apply colouring (or plus-minusing):
Code: Select all
 .  .  . | .  .  . | .  .  .
 .  .  . | 4  .  4 | .  .  .
 .  .  . | .  .  . | .  .  .
---------+---------+---------
 .  4  . | . +4  . | .  .  .
 .  .  . | 4  4  4 | .  . +4
 +4 .  . | .  4  . | .  .  4
---------+---------+---------
 .  4  . | 4  .  4 | .  .  .
 4  .  . | 4  .  . |+4  .  .
 . +4  . | . [4] . |-4  .  .
Case 1: (4 at r8c7)
1) 4 can only be at column 2 in block (3,1) (eliminate 4 from r4c2)
2) 4 at r6c1
3) 4 at r5c9
4) 4 at r4c5
5) 4 at r9c2 (optional to solve, but i've a purpose in including this, will show you why later)

Case 2: (4 at r9c7)

Both cases eliminates 4 from r9c5, leaving only 5 as the possible candidate. Hence, i've only used up to ii) in my algorithm, and this puzzle doesn't actually seem as hard as any other puzzle which requires up to ii) as well.

There is also another trick to colouring, whereby you start case1 with one of the pair of candidate in a unit, finish the chain, and start case2 with a candidate of a different pair of which has NOT been used.
To clarify, here's the same example i used earlier:
Code: Select all
 .  .  . | .  .  . | .  .  .
 .  .  . | 4  .  4 | .  .  .
 .  .  . | .  .  . | .  .  .
---------+---------+---------
 .  4  . | . +4  . | .  .  .
 .  .  . | 4  4  4 | .  . +4
 +4 .  . | .  4  . | .  .  4
---------+---------+---------
 .  4  . | 4  .  4 | .  .  .
 4  .  . | 4  .  . |+4  .  .
 . +4  . | . [4] . |-4  .  .
Case 1 has been optimized.
Case 2 starting from r9c7 does not seem to get you anywhere further.

However, we know for a fact that if r6c1 is not a 4, then r4c2 MUST be 4. Since the 1st chain involves having 4 in r6c1, we can then start Case2 with:

1) 4 in r4c2
2) 4 in r1c8
3) 4 in r9c7

Hence you should be able to see why i finished up the last bit of the first chain in my first attempt. The occurance of 4 in r9c2 in chain 1, together with the occurance of 4 in r4c2 in this new chain, will enable you to eliminate 4 in r7c2.

Another illustration of this similar trick on the same puzzle..
More candidates can actually be reduced in the same example. Considering possible 2s:
Code: Select all
 .  .  . | .  .  . | .  .  .
 2  . +2 |(2) . (2)| .  .  .
 . [2] . | 2  .  2 | .  .  .
---------+---------+---------
 . -2  . | . +2  . | .  .  .
 .  .  . | .  .  . | .  .  .
 +2 .  . | . -2  . | .  .  .
---------+---------+---------
 . [2] . | 2  .  2 | .  .  .
 2  .  2 | 2  .  . |+2  .  .
 . +2  . | .  .  . |-2  .  .

Case 1: (2 in r8c7)
1) 2 can only be on row 7 in block(3,2) (eliminate 2 from r7c2)
2) 2 in r9c2
3) 2 in r6c1
4a) 2 in r2c3 (note: this eliminates 2 from r2c4 and r2c6)
4b) 2 in r4c5

Case 2: (2 in r4c2, since r6c1 has been used by the first chain)
1a) 2 in r6c5
1b) 2 can only be on row 2 in block(1,1) (eliminate 2 from r2c4 and r2c6)
1c) 2 can only be on row 8 in block(3,1) (eliminate 2 from r8c4 and r8c7)
2) 2 in r9c7

Each of both cases eliminates 2 from r3c2 and r7c2. In addition, another two 2s at r8c4 and r8c7 can be eliminated as well if you follow through the entire chain.

Combining the elimination of candidate 2 & 4 in r7c2, you can then fill in the only possible candidate 9 in r7c2.

Limitations of this technique:
a) Like any other techniques, eliminating candidates with colouring sometimes gets your nowhere. One example would be Addlan's puzzle:
Code: Select all
 .  .  2 | .  9  . | 1  .  7
 .  3  8 | 6  .  . | .  .  .
 4  .  . | .  .  . | .  .  .
---------+---------+---------
 .  .  . | .  .  5 | .  .  .
 .  .  9 | .  1  . | 3  .  .
 .  .  . | 4  .  . | .  .  .
---------+---------+---------
 .  .  . | .  .  . | .  .  4
 .  .  . | .  .  7 | 9  2  .
 8  .  6 | .  3  . | 7  .  .

This puzzle is beyond ii) and even seems to be beyond iv), hence of course, beyond me (unless by trial and error:( ) However, i must mention that after technique i) has been exausted, colouring will be able to open up puzzles or reveal more naked/hidden pairs/triplets/quads 90% (modest assumption) of the time.

b) Colouring has its own inelegance occasionally. One particular example (taken from Nick's post:
possible 3s:
Code: Select all
. . . | 3 . . | . 3 .
. . . | . . . | . . .
. . . | . 3 . | . 3 3
------+-------+------
3 . . | . 3 . | . 3 .
3 . . | . . 3 | . . 3
3 . 3 | . 3 . | . . .
------+-------+------
. . 3 | . . 3 | . . .
3 . 3 | 3 . . | . . .
. . . | . . . | . . .


If we start colouring (plus-minusing) by choosing the pair of 3s at column 4, we would end up fine like what wolfgang achieved:
Code: Select all
. . . |-3 . . | .[3].
. . . | . . . | . . .
. . . | .[3]. | . 3+3
------+-------+------
3 . . | . 3 . | . 3 .
3 . . | . .+3 | . . 3
3 . 3 | . 3 . | . . .
------+-------+------
. . 3 | . . 3 | . . .
3 . 3 |+3 . . | . . .
. . . | . . . | . . .
However if we happen to choose the pair of 3s at block(1,2), we would have..
Case 1: (3 in r1c4)
1) 3 in r7c6

Case 2: (3 in r3c5)
1) 3 in r1c8
2) 3 in r5c9
3) huh:?::?: All candidates of 3 in block(2,2) has been eliminated!

In this case, we will meet with inconsistency and hence end up similar with the 'proof by contradiction' technique which people might dislike. However, if it doesn't bother you, this simply means that case2 is invalid and that the candidate of the first digit you chose (3 in r3c5 in this example) for case2 can be eliminated from that cell.

c) Colouring is currently unavailable to pappocom's program and perhaps some other sudoku programs. In the event that u want to use colouring on a sudoku program, you might have to sketch the individual candidates on a paper unless you can visualize the two entire chain in your mind. And for pen-pencil-paper sudoku players, colouring (i use circles and triangles) might be messy if there were long chains.

I am not, in any way, condemning or trying to belittle those who use other defined and established techniques. My post here is to recommend something which is easy to grasp, yet useful for those players who can't be bothered to learn the pattern and tricks of every technique out there. Currently, colouring does not seem popular among sudoku players, which was what driven me to write this.

PS. I just realized how long this post is after previewing again. Sorry for any instances of insanity caused.
Bunnybuck
 
Posts: 15
Joined: 13 June 2005

Postby Jeff » Tue Aug 09, 2005 12:51 pm

This is great stuff. Can it be given a name to distinguish it from other colouring methods; like 'Forcing Colours' or 'Colour Chains'?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Bunnybuck » Tue Aug 09, 2005 4:21 pm

Actually i am pretty content with just the term 'colouring'. However if we should name it, i suppose we have to consider the technique's unique characteristics.

- There are always 2 chains involved
- Key is to locate the intersecting point and common unit (row, column and blocks) of the 2 chains.

How about 'twin-headed snake' or hmm.. this..

i13.photobucket.com/albums/a270/dhtlee/double_dragon.jpg { broken link }

:D:!::D
Joking.. 'Colour chains' sounds fine.
Bunnybuck
 
Posts: 15
Joined: 13 June 2005

Re: About Colouring

Postby Wolfgang » Tue Aug 09, 2005 4:39 pm

Bunnybuck wrote:colouring does cover those techniques and possibly more.

I am rather sure you are right, cause the forcing chains dont make use of box elimination. (I already suggested the name "grade-2 forcing chain" that could use simple techniques like this or pairs to get from one step to the next). But i did not yet see a sample that i could not solve with weak chains either.
There is also another trick to colouring, whereby you start case1 with one of the pair of candidate in a unit, finish the chain, and start case2 with a candidate of a different pair of which has NOT been used.

You must not do this in general, because when from (n in A) follows that (n in B), it does not follow from (n not in A), that (n not in B). I.e. if it is possible that (n not in A) and (n in B), you cannot conclude anything further. So your sample with the 2's also is not correct. Eg it is possible that 2 is in r7c2 (which you eliminated)
Code: Select all
 .  .  . | .  .  . | .  .  .
 2  . +2 |(2) . (2)| .  .  .
 . [2] . | 2  .  2 | .  .  .
---------+---------+---------
 . -2  . | . +2  . | .  .  .
 .  .  . | .  .  . | .  .  .
 +2 .  . | . -2  . | .  .  .
---------+---------+---------
 . [2] . | 2  .  2 | .  .  .
 2  .  2 | 2  .  . |+2  .  .
 . +2  . | .  .  . |-2  .  .

Code: Select all
 .  .  . | .  .  . | .  .  .
 .  .  2 | .  .  . | .  .  .
 .  .  . | .  .  2 | .  .  .
---------+---------+---------
 .  .  . | .  2  . | .  .  .
 .  .  . | .  .  . | .  .  .
  2 .  . | .  .  . | .  .  .
---------+---------+---------
 .  2  . | .  .  . | .  .  .
 .  .  . | 2  .  . | .  .  .
 .  .  . | .  .  . | 2 .  .
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Re: About Colouring

Postby Nick70 » Tue Aug 09, 2005 4:50 pm

Wolfgang wrote:I am rather sure you are right, cause the forcing chains dont make use of box elimination.

Who said they don't?
Nick70
 
Posts: 156
Joined: 16 June 2005

Re: About Colouring

Postby Wolfgang » Tue Aug 09, 2005 5:10 pm

Nick70 wrote:
Wolfgang wrote:I am rather sure you are right, cause the forcing chains dont make use of box elimination.

Who said they don't?

I thought they would be defined about folowing way. When you eg say
r1c1=1->r2c2=3,
then then there must be a direct relationship like {1.3} are the only candidates for r2c2.
Then something like this is also a correct forcing chain?
r1c1=1->r2c2=3, when it is the case because of a swordfish in 5 and multi coloring in 4 ?
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Re: About Colouring

Postby Nick70 » Tue Aug 09, 2005 5:35 pm

Wolfgang wrote:I thought they would be defined about folowing way.

I don't know, I have slight difficulty understanding what you say. Could you define "box elimination" please?
Nick70
 
Posts: 156
Joined: 16 June 2005

Re: About Colouring

Postby Bunnybuck » Tue Aug 09, 2005 6:07 pm

Wolfgang wrote:You must not do this in general, because when from (n in A) follows that (n in B), it does not follow from (n not in A), that (n not in B). I.e. if it is possible that (n not in A) and (n in B), you cannot conclude anything further. So your sample with the 2's also is not correct. Eg it is possible that 2 is in r7c2 (which you eliminated)


Darn, being a math student, i should've realized that earlier. Thanks for the observation Wolfgang. Hope the readers would be able to filter out the incorrect half (ouch!) that i wrote.


** Edit: Upon discovering a logical reasoning to prove that my trick actually works, i'm taking my words back.:)
Last edited by Bunnybuck on Wed Aug 10, 2005 9:00 am, edited 1 time in total.
Bunnybuck
 
Posts: 15
Joined: 13 June 2005

Postby Bunnybuck » Tue Aug 09, 2005 6:15 pm

Code: Select all
 6  6 [6]| .  . -6 | 6  .  .
 .  . -6 |+6  .  . | .  .  .
 .  . [6]| .  .  . |+-6 .  .
---------+---------+---------
 6  6 [6]| .  .  . | .  6  .
 6  6  . | .  .  . | .  6  .
 .  .  . | .  .  . | .  .  .
---------+---------+---------
 .  .  . | .  .  . | .  .  .
 6  6  . |[6] . +6 | .  .  .
 .  . +6 |-6  .  . | .  .  .
My chain of thoughts as follow
Case 1:
1) 6 in r2c4
2) 6 in r8c6
3) 6 in r9c3
4) 6 can only be on row 1 in block (1,1) (eliminate 6 in r1c7)
5) 6 in r3c7


I think what Wolfgang meant as 'box elimination' was the chain process at 4)
Bunnybuck
 
Posts: 15
Joined: 13 June 2005

Postby tso » Wed Aug 10, 2005 12:42 am

I botched this post. This is a correction. Changes in bold.

"Forcing Colors" is to "Nishio" as "Forcing Chains" is to "Proof by Contradiction". This is another way of looking at Nishio in reverse.

Here's the Nishio: If r1c7=6, can the other 6's be placed?

If r1c7=6, then r1c1236<>6.
If r1c6<>6 => r8c6=6 => r8c12<>6 => r9c3=6 => r123c3<>6.

This eliminates all possible placements of 6 in box 1, therefore, our original assumption is false.

Since r1c7<>6, r3c7 MUST be 6.

==================

Which method will be simpler may depend on the specifcs but this Nishio could be done in your head. I needed two copies of Simple Sudoku running at once, one for each line of reasoning. Then of course, I do get a lot of information at the end -- eliminating 4 candidates and placing one 6.
Last edited by tso on Wed Aug 10, 2005 10:19 pm, edited 2 times in total.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Wolfgang » Wed Aug 10, 2005 7:47 am

tso wrote:Here's the Nishio: If r1c7=6, can the other 6's be placed?

If r1c7=6 => r1c1236<>6 and r3c7<>6
If r3c7<>6 => r3c3=6 => r12c3<>6
This eliminates all possible placements of 6 in box 1, therefore, our original assumption is false.

Cant get that. Doesnt it just show, that r1c7=6 => r3c3=6 ?
Ah, maybe you have done it this way:
r1c7=6 => r1c6<>6 => r2c4=6 => r89c4 <> 6 => r8c6=6 =>
r8c12<>6 => r9c3=6 => r123c3 <>6
So forcing chains really can use 'box elimination' with contradicting chains, i was mistaken.
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Re: About Colouring

Postby Wolfgang » Wed Aug 10, 2005 8:51 am

Hm, maybe i was too hasty again. For this (fictive) pattern, can you build a forcing chain to show that r3c9 must be 6?
Code: Select all
 6  6  6 | .  .  . | 6  .  .
 .  .  6 | .  .  . | .  .  .
 .  .  6 | .  .  . | .  .  6
---------+---------+---------
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
---------+---------+---------
 .  .  . | .  .  . | 6 .  .
 6  .  . | .  .  . | 6  6  6
 .  .  6 | .  .  . | 6  .  .
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Re: About Colouring

Postby Nick70 » Wed Aug 10, 2005 9:36 am

Wolfgang wrote:For this (fictive) pattern, can you build a forcing chain to show that r3c9 must be 6?

For this specific pattern it's quite simple.

r8c1=6 => r8c9<>6 => r3c9=6
r9c3=6 => r3c3<>6 => r3c9=6
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby stuartn » Wed Aug 10, 2005 10:12 am

and:

R8C1<>6 =>R1C1=6 => R3C9=6

Stuartn

http://www.brightonandhove.org/sudolinks
Last edited by stuartn on Wed Aug 10, 2005 7:01 am, edited 1 time in total.
stuartn
 
Posts: 211
Joined: 18 June 2005

Re: About Colouring

Postby Wolfgang » Wed Aug 10, 2005 10:55 am

oops, i didnt enter the 6 in the 5 other boxes:
Code: Select all
 6  6  6 | 6  6  6 | 6  .  .
 .  .  6 | 6  6  6 | .  .  .
 .  .  6 | 6  6  6 | .  .  6
---------+---------+---------
 6  6  6 | 6  6  6 | 6  6  6
 6  6  6 | 6  6  6 | 6  6  6
 6  6  6 | 6  6  6 | 6  6  6
---------+---------+---------
 .  .  . | 6  6  6 | 6 .  .
 6  .  . | 6  6  6 | 6  6  6
 .  .  6 | 6  6  6 | 6  .  .
Last edited by Wolfgang on Wed Aug 10, 2005 7:12 am, edited 1 time in total.
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Next

Return to Advanced solving techniques

cron