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 - Thought I had it!
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
byteman

Joined: 07 Nov 2005
Posts: 3
:

Items
PostPosted: Mon Nov 07, 2005 11:40 pm    Post subject: Colors - Thought I had it! Reply with quote

In this puzzle (from the .ss file):

Code:
 *-----------*
 |..8|..6|...|
 |4..|.9.|.7.|
 |...|..2|.51|
 |---+---+---|
 |..2|7..|68.|
 |...|...|...|
 |.65|..8|2..|
 |---+---+---|
 |63.|2..|...|
 |.1.|.6.|..7|
 |...|9..|5..|
 *-----------*

I176
I206
I402
I396
I427
I457
I635
I796
I102
I015
I197
I047
I722
I738
I368
I702
I082
I125
I158
I628
I668
I228
I601
E38009
E38004
E27009
E48004
E43009
E35009
E44009
I539

...the (Colors) "hint" says you can eliminate the "1" in r4c5. I thought it would be r4c6 (where the green and blue intersect). Can someone explain why it's r4c5?

Thanks
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Tue Nov 08, 2005 12:14 am    Post subject: Reply with quote

This is the coloring scheme that my program encountered:

Code:
A . .|a . .|. . .
. . a|. . A|. . .
. . .|. . .|. . 1
-----+-----+-----
a . .|. A .|. . .
. . A|. . *|. C .
. . .|A * .|. c .
-----+-----+-----
. . .|. . .|1 . .
. 1 .|. . .|. . .
. . .|. B b|. . .


As you can see, A appears twice in box 5. It forms an inconsistent chain and all A's can be eliminated, not just r4c5.

About r4c6, it falls victim to a remote pair r4c1 and r2c6 with digits 1 and 3.
Back to top
View user's profile Send private message Visit poster's website
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Tue Nov 08, 2005 2:08 am    Post subject: Re: Colors - Thought I had it! Reply with quote

byteman wrote:
Can someone explain why it's r4c5?


Filtering on 1's:
r4c1 = green, r6c4 = blue. Since r4c5 shares a group with these two conjugate cells it must be a 'false' cell so 1 can be removed as a candidate in that cell.
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Tue Nov 08, 2005 2:32 am    Post subject: Reply with quote

In fact, both eliminations can be done with a single coloring test.

without the remote pair check, this pattern came up with coloring:

Code:
A . .|a . .|. . .
. . a|. . A|. . .
. . .|. . .|. . 1
-----+-----+-----
a . .|. - -|. . .
. . A|. . *|. C .
. . .|A * .|. c .
-----+-----+-----
. . .|. . .|1 . .
. 1 .|. . .|. . .
. . .|. B b|. . .

As you can see, both r4c5 and r4c6 share a group with r4c1 (a) and r6c4 (A)
Back to top
View user's profile Send private message Visit poster's website
kranser

Joined: 18 Aug 2005
Posts: 35
:

Items
PostPosted: Tue Nov 08, 2005 10:07 am    Post subject: Reply with quote

Ruud wrote:
In fact, both eliminations can be done with a single coloring test.

without the remote pair check, this pattern came up with coloring:

Code:
A . .|a . .|. . .
. . a|. . A|. . .
. . .|. . .|. . 1
-----+-----+-----
a . .|. - -|. . .
. . A|. . *|. C .
. . .|A * .|. c .
-----+-----+-----
. . .|. . .|1 . .
. 1 .|. . .|. . .
. . .|. B b|. . .

As you can see, both r4c5 and r4c6 share a group with r4c1 (a) and r6c4 (A)


My solver also produces this result - i.e. it finds that r4c5 is grouped with both A and a, and eliminates 1 from r4c5, which causes the solver not to find that box 5 has 2 A's in it!

Whereas Simple Sudoku solver seems to find the box 5 A's first! But chooses not to eliminate the 1's at this stage, instead it eliminates 1 from r4c6 (seeming to ignore the r4c5 cell) and then finds the 2 A's in box 5.

However, my solver finds the solution without finding the 2 A's in box 5 (the same as Ruud's one does).

It seems that these 2 colouring techniques (1. Cell grouped with A and a; and 2. Group containing 2 of A) are mutually exclusive, if you use one you could destroy your chance to use the other!

So, does it really matter which technique you use?

Kranser.
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Tue Nov 08, 2005 11:24 am    Post subject: Reply with quote

kranser wrote:
So, does it really matter which technique you use?

Very often it doesn't matter - when there are a number of ways to progress a puzzle. However sometimes it does matter in that only one or other technique will work.
Back to top
View user's profile Send private message Visit poster's website
gaby

Joined: 02 Jul 2005
Posts: 120
:

Items
PostPosted: Tue Nov 08, 2005 11:27 am    Post subject: Reply with quote

I get these results, the first colouring pass ends here:

http://vanhegan.net/pictures/state5.png

Code:
1 <- [r4,c6] Coloured cells: [r1,c1]=1a, [r6,c4]=1a, [r1,c4]=1b, [r4,c1]=1b, [r2,c6]=2a, [r5,c3]=2a, [r2,c3]=2b, [r9,c5]=3a, [r9,c6]=3b, [r5,c8]=4a, [r6,c8]=4b. If 1a excludes 2b, the intersection of 1b and 2a prohibits 1 at [r4,c6]


Then this:

http://vanhegan.net/pictures/state6.png

Code:
1 <- [r1,c1] Coloured cells: [r1,c1]=1a, [r6,c4]=1a, [r4,c5]=1a, [r1,c4]=1b, [r4,c1]=1b, [r2,c6]=2a, [r5,c3]=2a, [r2,c3]=2b, [r9,c5]=3a, [r9,c6]=3b, [r5,c8]=4a, [r6,c8]=4b. State 1b is valid, state 1a conflicts in b4
1 <- [r6,c4] Coloured cells: [r1,c1]=1a, [r6,c4]=1a, [r4,c5]=1a, [r1,c4]=1b, [r4,c1]=1b, [r2,c6]=2a, [r5,c3]=2a, [r2,c3]=2b, [r9,c5]=3a, [r9,c6]=3b, [r5,c8]=4a, [r6,c8]=4b. State 1b is valid, state 1a conflicts in b4
1 <- [r4,c5] Coloured cells: [r1,c1]=1a, [r6,c4]=1a, [r4,c5]=1a, [r1,c4]=1b, [r4,c1]=1b, [r2,c6]=2a, [r5,c3]=2a, [r2,c3]=2b, [r9,c5]=3a, [r9,c6]=3b, [r5,c8]=4a, [r6,c8]=4b. State 1b is valid, state 1a conflicts in b4

_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Tue Nov 08, 2005 12:56 pm    Post subject: Reply with quote

gaby
You're still not merging all colors. The 1ab and 2ab colors can be combined in a single chain in this example, because they are linked with conjugate pairs.
Back to top
View user's profile Send private message Visit poster's website
kranser

Joined: 18 Aug 2005
Posts: 35
:

Items
PostPosted: Tue Nov 08, 2005 1:07 pm    Post subject: Reply with quote

angusj wrote:
kranser wrote:
So, does it really matter which technique you use?

Very often it doesn't matter - when there are a number of ways to progress a puzzle. However sometimes it does matter in that only one or other technique will work.


So it is best to try each Colouring elimination technique first before deciding which one is most beneficial? If so, this sounds complex as the solver would have to look a few steps ahead!

Anyone have a method for getting around this? And, just how does the Simple Sudoku program know to skip the elimination on r4c5 in order to obtain the 'more important' elimination of all of the Blue squares once r4c6 has been eliminated and the grid has been recoloured! I can't figure out how it could 'easily' know that!

Kranser.
Back to top
View user's profile Send private message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Tue Nov 08, 2005 8:58 pm    Post subject: Reply with quote

Medusa gives a small 2D (simple coloring) four-node cycle with an invalid weak corner at r4c6:

Code:

1*---------1
|           \
|            \
|             1*
|             .
|             .
1.............X (r4c6)


and, once that is gone,
an incompatible strong chain, as mentioned above, that deletes half its nodes.

Code:

1*-----1
|      |
|      |
|      |
|      |
|      |
1------+---1* (r4c5)
       |  x
       | x
       |x
       1*


(I'm pretty sure 2D Medusa amounts to simple coloring--but I never implemented that (maybe I should) and 3D Medusa includes at least advanced coloring.)
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
byteman

Joined: 07 Nov 2005
Posts: 3
:

Items
PostPosted: Wed Nov 09, 2005 12:25 am    Post subject: Reply with quote

Quote:
Filtering on 1's:
r4c1 = green, r6c4 = blue. Since r4c5 shares a group with these two conjugate cells it must be a 'false' cell so 1 can be removed as a candidate in that cell.


Going back to my original question (and please excuse my ignorance), but I don't see where r4c5 shares a "group" with r4c1 and r6c4???
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Wed Nov 09, 2005 12:42 am    Post subject: Reply with quote

kranser wrote:
And, just how does the Simple Sudoku program know to skip the elimination on r4c5 ...


FWIW, the latest version (4.1s) eliminates candidate 1 from r4c5 before r4c6. And the next coloring will still put two A's in box 5 (and two A's in col 6), eliminating all the A's.
Code:

 A . . | a . . | . . .
 . . a | . . A | . . .
 . . . | . . . | . . 1
 - - - + - - - + - - -
 a . . | . . A | . . .
 . . A | . . * | . E .
 . . . | A d . | . e .
 - - - + - - - + - - -
 . . . | . . . | 1 . .
 . 1 . | . . . | . . .
 . . . | . D d | . . .


byteman wrote:
but I don't see where r4c5 shares a "group" with r4c1 and r6c4


Every cell (square) is a member of three groups. As some look at it, every cell has 20 "buddies", 8 in its row, 8 in its column, and 4 more in its box (that weren't already counted as part of the row and column).

For this coloring rule, and put in "buddy" terms, if a cell with candidate x has at least one buddy with one of the two conjugate pair colors ... aka complementary colors ... and also has at least one buddy with the other color, then candidate x can be eliminated from the cell.

For the example the cell being considered is r4c5. By row r4c1 (green), and by box r6c4 (blue) are both buddies. We have both complementary colors .... so r4c5#1 can be eliminated.


Last edited by rkral on Wed Nov 09, 2005 3:44 am; edited 5 times in total
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed Nov 09, 2005 1:15 am    Post subject: Reply with quote

byteman wrote:
Going back to my original question (and please excuse my ignorance), but I don't see where r4c5 shares a "group" with r4c1 and r6c4???


Let's review this picture:

Code:
A . .|a . .|. . .
. . a|. . A|. . .
. . .|. . .|. . 1
-----+-----+-----
a . .|. - -|. . .
. . A|. . *|. C .
. . .|A * .|. c .
-----+-----+-----
. . .|. . .|1 . .
. 1 .|. . .|. . .
. . .|. B b|. . .

Coloring highlights conjugate pairs. When A = 1, a cannot be 1, so A and a exclude each other.
There is an a in R4C1, sharing a row with R5C5 and R5C6.
There is an A in R6C4, sharing a box with R5C5 and R5C6.

"group" is the common name for row, column or box (anything that can only contain 9 different digits) see Gaby's list


Since either A or a contains digit 1, R5C5 and R5C6 would be eliminated in both situations.

Ruud.
Back to top
View user's profile Send private message Visit poster's website
kranser

Joined: 18 Aug 2005
Posts: 35
:

Items
PostPosted: Wed Nov 09, 2005 10:14 am    Post subject: Reply with quote

rkral wrote:
kranser wrote:
And, just how does the Simple Sudoku program know to skip the elimination on r4c5 ...


FWIW, the latest version (4.1s) eliminates candidate 1 from r4c5 before r4c6. And the next coloring will still put two A's in box 5 (and two A's in col 6), eliminating all the A's.


Ah, ok, that explains it! I'm using version 3.8m - so didn't have the latest fixes. I guess Simple Sudoku gives a higher priority Colouring Rule 2 (Elimination of a colour if two or more of that colour occur in a group), than to rule 1 (Elimination of the cell's candicate if it is grouped with cells of both colours), as r2c6 could be eliminated based on rule 1, which would also break the puzzle open; however it is quicker and more effictive to find the eliminations based on rule 2!
And it also shows that Simple Sudoku opts to recolour the grid after a colouring rule 1 elimination - which sounds like a good idea to me Smile

If all agree, maybe we can add this to the colouring technique definition, as the technique seems to be non-standard and incomplete without rules determining which colouring rules take priority and when to recolour the grid, etc... What do you think, do we need to add these requirements to the colouring definition?

Kranser.
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Wed Nov 09, 2005 12:17 pm    Post subject: Reply with quote

kranser wrote:
I'm using version 3.8m - so didn't have the latest fixes.

I wouldn't call changing the sequence of valid eliminations a "fix".

kranser wrote:
I guess Simple Sudoku gives a higher priority Colouring Rule 2 (Elimination of a colour if two or more of that colour occur in a group), than to rule 1 (Elimination of the cell's candicate if it is grouped with cells of both colours), as r2c6 could be eliminated based on rule 1, which would also break the puzzle open; however it is quicker and more effictive to find the eliminations based on rule 2!

You've correctly identified the sequence in which the rules are applied, but question your identification as to which is rule 1 and which is rule2.

kranser wrote:
And it also shows that Simple Sudoku opts to recolour the grid after a colouring rule 1 elimination - which sounds like a good idea to me

I may have mislead you by saying "the next coloring", but you're also jumping to a conclusion. There is no "opting to recolour" per se. For the next hint after the elimination of r4c5#1, Simple Sudoku first tries the simplest techniques. None yield eliminations until the "coloring rule 2" technique.
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
Goto page 1, 2  Next
Page 1 of 2

 
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