|
View previous topic :: View next topic |
Author |
Message |
| byteman
| Joined: 07 Nov 2005 | Posts: 3 | : | | Items |
|
Posted: Mon Nov 07, 2005 11:40 pm Post subject: Colors - Thought I had it! |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Tue Nov 08, 2005 12:14 am Post subject: |
|
|
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 |
|
|
| angusj Site Admin
| Joined: 18 Jun 2005 | Posts: 406 | : | | Items |
|
Posted: Tue Nov 08, 2005 2:08 am Post subject: Re: Colors - Thought I had it! |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Tue Nov 08, 2005 2:32 am Post subject: |
|
|
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 |
|
|
| kranser
| Joined: 18 Aug 2005 | Posts: 35 | : | | Items |
|
Posted: Tue Nov 08, 2005 10:07 am Post subject: |
|
|
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 |
|
|
| angusj Site Admin
| Joined: 18 Jun 2005 | Posts: 406 | : | | Items |
|
Posted: Tue Nov 08, 2005 11:24 am Post subject: |
|
|
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 |
|
|
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Tue Nov 08, 2005 11:27 am Post subject: |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Tue Nov 08, 2005 12:56 pm Post subject: |
|
|
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 |
|
|
| kranser
| Joined: 18 Aug 2005 | Posts: 35 | : | | Items |
|
Posted: Tue Nov 08, 2005 1:07 pm Post subject: |
|
|
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 |
|
|
| Bob Hanson
| Joined: 05 Oct 2005 | Posts: 187 | : | Location: St. Olaf College | Items |
|
Posted: Tue Nov 08, 2005 8:58 pm Post subject: |
|
|
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 |
|
|
| byteman
| Joined: 07 Nov 2005 | Posts: 3 | : | | Items |
|
Posted: Wed Nov 09, 2005 12:25 am Post subject: |
|
|
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 |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Wed Nov 09, 2005 12:42 am Post subject: |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Wed Nov 09, 2005 1:15 am Post subject: |
|
|
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 |
|
|
| kranser
| Joined: 18 Aug 2005 | Posts: 35 | : | | Items |
|
Posted: Wed Nov 09, 2005 10:14 am Post subject: |
|
|
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
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 |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Wed Nov 09, 2005 12:17 pm Post subject: |
|
|
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 |
|
|
|
|
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
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|