FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Starting position for colouring and different solutions Goto page 1, 2  Next          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message kranser Joined: 18 Aug 2005 Posts: 35 : Items Posted: Thu Oct 27, 2005 9:08 am    Post subject: Starting position for colouring and different solutions I've been reading up on colourng and I'm confused about the starting position on the simes.clara example: http://www.simes.clara.co.uk/programs/sudokutechnique12.htm It filters on 1's as follows: Code: .1....... ..1...... ......... 1......1. 111...... 1.......1 ......... ......... ......... And colours as follows (from what I can tell as the colours aren't very distinct): Code: .B....... ..G...... ......... *......1. *GB...... *.......1 ......... ......... ......... Starting from square r1c2, it seems to colour this square Blue, then colour r5c2 Green - at they are opposites, then it colours r2c3 Green (opposite to r1c2) and r5c3 Blue. It says that the squares marked * can have 1 removed as they are in the same unit as cells with either truth state. But what if I started colouring with square r4c1 instead of r1c2? Would I not get this?: Code: .1....... ..1...... ......... B......G. ***...... G.......B ......... ......... ......... Where I can remove the * squares because the block starting at r4c1 has both truth states. This doesn't seem right, as depending on where you start, you could get different solutions! Can anyone help me understand this? Thanks, Kranser. Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Thu Oct 27, 2005 10:00 am    Post subject: Re: Starting position for colouring and different solutions kranser wrote: Can anyone help me understand this? You seem to have a good understanding of colours as your observations are correct. This particular example on simes webpage isn't a good one for the very reason you've stated. The other minor problem with this particular example is the 1's could be excluded using a simpler technique. ps: Please don't think I'm "having a go" at simes otherwise excellent website. Back to top kranser Joined: 18 Aug 2005 Posts: 35 : Items Posted: Thu Oct 27, 2005 10:21 am    Post subject: Ah ok, that makes more sense. Thanks for the reply. So, if the puzzle isn't a good example, what about the technique of removing candicates from a block if the block also contains a True and False candicates.? Is the technique wrong, or does it need additional rules which enable it to always work correctly? Kranser. Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Thu Oct 27, 2005 10:56 am    Post subject: kranser wrote: So, if the puzzle isn't a good example, what about the technique of removing candicates from a block if the block also contains a True and False candicates.? Is the technique wrong, or does it need additional rules which enable it to always work correctly? The more general color rule is if any cell is associated with both conjugates (true and false) then that cell can't be true. Note, as in the example below, the conjugates don't have to be in the same group, but can be chained conjugates: Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Thu Oct 27, 2005 11:14 am    Post subject: kranser wrote: So, if the puzzle isn't a good example, what about the technique of removing candicates from a block if the block also contains a True and False candicates.? Is the technique wrong, or does it need additional rules which enable it to always work correctly? One bad example does not make it a bad technique. When explaining coloring, people tend to leave out the candidates that play no role in the coloring pattern, but leaving them out can alter the pattern in such a way, that an invalid pattern is created. Unlike forcing chains, coloring does not need a single starting point. You just start coloring ALL conjugate pairs. When 2 conjugate pairs share a candidate, you merge their colors to form longer chains. Each chain contains 2 complementing colors. For simple coloring, you only look at the chains themselves. There are 2 conclusions you can draw: 1. When the same color appears more than once in a house, that color is inconsistent and ALL candidates with that color can be eliminated. 2. When 2 complementing colors appear in the same house, all remaining candidates within that house can be eliminated. Ruud Back to top kranser Joined: 18 Aug 2005 Posts: 35 : Items Posted: Thu Oct 27, 2005 11:30 am    Post subject: Re: Starting position for colouring and different solutions angusj wrote: The other minor problem with this particular example is the 1's could be excluded using a simpler technique. Thanks for the information angusj. I now see that the technique is good and understand how it affects rows, columns and houses. So, it the puzzle is ok, will I not have the situation starting in different places produces different solutions? Also does your quote mean that x-Wing and Swordfish must be applied to the puzzle first in order for the colouring techniques to work? Kranser. Back to top kranser Joined: 18 Aug 2005 Posts: 35 : Items Posted: Thu Oct 27, 2005 11:32 am    Post subject: Ruud wrote: One bad example does not make it a bad technique. When explaining coloring, people tend to leave out the candidates that play no role in the coloring pattern, but leaving them out can alter the pattern in such a way, that an invalid pattern is created. Thanks for the explaination Ruud. Does that mean that simple colouring can create invalid patterns, and so I shouldn't use simple colouring, but should use multi (advanced/super/ultra) colouring instead? Kranser. Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Thu Oct 27, 2005 11:35 am    Post subject: Re: Starting position for colouring and different solutions kranser wrote: So, it the puzzle is ok, will I not have the situation starting in different places produces different solutions? There is only one solution if the puzzle is properly constructed but there are many different ways to derive that one solution. kranser wrote: Also does your quote mean that x-Wing and Swordfish must be applied to the puzzle first in order for the colouring techniques to work? No, definitely not. Using these techniques in different orders simply means that incorrect candidates are excluded in a different order. If the techniques are applied correctly you will never exclude a valid candidate. Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Thu Oct 27, 2005 11:45 am    Post subject: kranser: As long as you take ALL candidates into account, you will not encounter any invalid patterns. You can use simple coloring any time. It is a very useful tool. Multicoloring is more powerful, because it also looks at the interactions between chains. It is also more complicated. Angus: You are supporting multicoloring in Simple Sudoku. Does that mean you can now use more than 4 colors? I found it very difficult to do multicoloring with a palette of green/blue/pink/amber. Ruud. Back to top kranser Joined: 18 Aug 2005 Posts: 35 : Items Posted: Thu Oct 27, 2005 11:46 am    Post subject: Re: Starting position for colouring and different solutions angusj wrote: There is only one solution if the puzzle is properly constructed but there are many different ways to derive that one solution. Ok, I understand now! The puzzle was bad which is why the technique didn't work. So, if I implement the technique as described and run ot on valid puzzles, all should work and I won't get multiple solutions! Thanks for your help. Kranser. Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Thu Oct 27, 2005 12:08 pm    Post subject: Ruud wrote: Does that mean you can now use more than 4 colors? No. Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Thu Oct 27, 2005 12:18 pm    Post subject: Here's another link to a summary of "simple" colors: http://www.setbb.com/phpbb/viewtopic.php?p=1562&mforum=sudoku#1562 Back to top Lummox JR Joined: 07 Sep 2005 Posts: 202 : Items Posted: Thu Oct 27, 2005 7:59 pm    Post subject: Note that according to the Simes page, and in many posts I've researched, simple coloring refers to any coloring method that limits itself to one digit; it needn't be limited to one conjugate chain. In more general parlance, simple coloring is single-digit and advanced coloring is multi-digit. I tend to agree more with that terminology because single-chain simple coloring is such a poor cousin of multi-chain simple coloring that it doesn't really deserve a distinction. Back to top rkral Joined: 21 Oct 2005 Posts: 233 : Items Posted: Thu Oct 27, 2005 8:38 pm    Post subject: Ruud wrote: When explaining coloring, people tend to leave out the candidates that play no role in the coloring pattern, but leaving them out can alter the pattern in such a way, that an invalid pattern is created. I think the more correct statement would be that "an incomplete pattern is created." An incomplete coloring pattern should still be valid, and not lead to invalid exclusions. It just might not yield exclusions that the complete pattern would. Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Thu Oct 27, 2005 9:43 pm    Post subject: rkral wrote: I think the more correct statement would be that "an incomplete pattern is created." An incomplete coloring pattern should still be valid, and not lead to invalid exclusions. It just might not yield exclusions that the complete pattern would. That too. The case discussed here is an "incomplete pattern" where, as a result of leaving out some candidates, additional conjugate pairs have been found by kranser. When you color these, you can make more eliminations than with the complete pattern. In this case all candidates from box 4 could be eliminated by coloring, thus creating an "invalid pattern". It works both ways. I think Simes is just testing us. If you can spot the inconsistency, you understood the principles of coloring and passed the test. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Solving sudoku All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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