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   

Simple Sudoku and Colors
Goto page 1, 2, 3, 4  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
bart

Joined: 11 Aug 2005
Posts: 46
:

Items
PostPosted: Thu Aug 11, 2005 9:56 am    Post subject: Simple Sudoku and Colors Reply with quote

Hello

This is the sudoku (Expert) I'm working on:

copy/paste:
Code:

...|3..|87.
.5.|4.8|2..
..2|9..|4..
---+---+---
6..|5..|18.
.2.|.4.|.3.
.87|..1|..4
---+---+---
..9|..4|5..
..5|1.9|.4.
.68|..3|...


...|3..|87.
75.|4.8|2..
8.2|97.|4..
---+---+---
6..|5..|18.
.21|84.|.3.
.87|..1|..4
---+---+---
..9|..4|5..
275|1.9|34.
468|.53|...


{19}   {49}   {46}   {3}    {126}  {256}  {8}    {7}    {156} 
{7}    {5}    {36}   {4}    {16}   {8}    {2}    {169}  {1369}
{8}    {13}   {2}    {9}    {7}    {56}   {4}    {156}  {1356}
{6}    {49}   {34}   {5}    {39}   {27}   {1}    {8}    {27}   
{59}   {2}    {1}    {8}    {4}    {67}   {679}  {3}    {579} 
{359}  {8}    {7}    {26}   {39}   {1}    {69}   {259}  {4}   
{13}   {13}   {9}    {267}  {268}  {4}    {5}    {26}   {2678}
{2}    {7}    {5}    {1}    {68}   {9}    {3}    {4}    {68}   
{4}    {6}    {8}    {27}   {5}    {3}    {79}   {129}  {1279}



from .ss file

Code:

...|3..|87.
.5.|4.8|2..
..2|9..|4..
---+---+---
6..|5..|18.
.2.|.4.|.3.
.87|..1|..4
---+---+---
..9|..4|5..
..5|1.9|.4.
.68|..3|...

I381
I693
I724
I765
I188
I398
I647
I632
E61001
E62011
E01001
E28003
I097
E08009
E58007
E44006
E52016
E31002
E49012
E49006
E31007
I227
E35009


when I let the program solve the next step it deletes the 2 from row 7, col 8
how exactly is that possible?

sometimes when I'm stuck and ask for help the program hightlights more than 1 cell when numbers can be deleted using the colors method. After reading the help-file, I thought only 1 candidate could be deleted

I know I'm not that great with solving sudoku's, but I'd just like to learn

thanks for the help
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Thu Aug 11, 2005 11:00 am    Post subject: Re: Simple Sudoku and Colors Reply with quote

bart wrote:
it deletes the 2 from row 7, col 8 how exactly is that possible?


Filter on 2s and follow the colours I've applied below:
Code:

...|.BG|...
...|...|...
...|...|...
---+---+---
...|..B|..G
...|...|...
...|...|.B.
---+---+---
...|.G.|.*.
...|...|...
...|...|...


Following conjugate cells - either Blue or Green must represent 2, we just don't know which. The cell r7c8 (marked *) is related to both a Blue and a Green marker so it can't be a 2.
Back to top
View user's profile Send private message Visit poster's website
bart

Joined: 11 Aug 2005
Posts: 46
:

Items
PostPosted: Thu Aug 11, 2005 11:36 pm    Post subject: Reply with quote

thanks!!

so easy... Embarassed
Back to top
View user's profile Send private message
bart

Joined: 11 Aug 2005
Posts: 46
:

Items
PostPosted: Fri Aug 12, 2005 2:52 pm    Post subject: Reply with quote

probably another simple solution, I just don't see it

from copy/paste
Code:

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


.58|.76|..2
42.|59.|876
.76|.82|.51
---+---+---
..2|7..|68.
8..|62.|7..
765|..8|2.9
---+---+---
63.|2..|1.8
51.|86.|.27
28.|9..|56.


{139}   {5}     {8}     {134}   {7}     {6}     {349}   {349}   {2}     
{4}     {2}     {13}    {5}     {9}     {13}    {8}     {7}     {6}     
{39}    {7}     {6}     {34}    {8}     {2}     {349}   {5}     {1}     
{13}    {49}    {2}     {7}     {1345}  {3459}  {6}     {8}     {345}   
{8}     {49}    {13}    {6}     {2}     {13459} {7}     {134}   {345}   
{7}     {6}     {5}     {13}    {134}   {8}     {2}     {134}   {9}     
{6}     {3}     {479}   {2}     {45}    {457}   {1}     {49}    {8}     
{5}     {1}     {49}    {8}     {6}     {34}    {349}   {2}     {7}     
{2}     {8}     {47}    {9}     {134}   {1347}  {5}     {6}     {34}   



from .ss file
Code:

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

E38004
E20007
E38017
E20009
E38019
I402
I635
I396
I176
I796
I206
I427
I457
E58007
E73017
E76027
E60008
E69018
E58001
E59011
I702
I082
I102
I722
I015
I125
I197
I047
I738
I368
I628
I668
I228
I158
E27009
I601
E48004
E35009
E43019
E44029
E32001
I539


it says it can delete the 1's in row1/col1, row2/col6, row4/col5, row5/col3, row6/col4
all these have the color blue (or green, it depends where I start)
does that have something to do with it? if yes, why?

Code:

B..|G..|...
..G|..B|...
...|...|...
---+---+---
G..|.B.|...
..B|..1|.1.
...|B1.|.1.
---+---+---
...|...|...
...|...|...
...|.11|...
Back to top
View user's profile Send private message
bart

Joined: 11 Aug 2005
Posts: 46
:

Items
PostPosted: Fri Aug 12, 2005 3:59 pm    Post subject: Reply with quote

I've had the same problem in a few other puzzles but I think I've found the solution myself this time
is it because there are 2 blue's in the same block? must be
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Fri Aug 12, 2005 10:58 pm    Post subject: Reply with quote

bart wrote:
I've had the same problem in a few other puzzles but I think I've found the solution myself this time
is it because there are 2 blue's in the same block?

Exactly right. (If there are 2 of one colour in a block, what must that colour represent?)
Back to top
View user's profile Send private message Visit poster's website
lennyh

Joined: 29 Aug 2005
Posts: 8
:
Location: Raleigh, NC USA

Items
PostPosted: Mon Aug 29, 2005 1:47 pm    Post subject: Colors Reply with quote

I've been very much enjoying using Angus's lovely Simple Solver, but am confused by 1 aspect of the Colors technique. I believed this may have been explained earlier, but I'm still missing something.

Here goes: One of the rules associated with colors states "Whenever two cells in a conjugate chain have the same color and also share the same group, that color must be the 'false' color ..."

What does it mean to say that color is the 'false' color? Does it mean that the candidate can be removed from the cell with the 'false' color? But there are 2 cells within the group with the 'false' color. From which of these 2 'false' cells can the candidate be removed? Or can it be removed from both?

I expect I'm missing something rather basic here.

Thanks for any help.
Back to top
View user's profile Send private message
bart

Joined: 11 Aug 2005
Posts: 46
:

Items
PostPosted: Mon Aug 29, 2005 2:14 pm    Post subject: Re: Colors Reply with quote

lennyh wrote:
I've been very much enjoying using Angus's lovely Simple Solver, but am confused by 1 aspect of the Colors technique. I believed this may have been explained earlier, but I'm still missing something.

Here goes: One of the rules associated with colors states "Whenever two cells in a conjugate chain have the same color and also share the same group, that color must be the 'false' color ..."

What does it mean to say that color is the 'false' color? Does it mean that the candidate can be removed from the cell with the 'false' color? But there are 2 cells within the group with the 'false' color. From which of these 2 'false' cells can the candidate be removed? Or can it be removed from both?

I expect I'm missing something rather basic here.

Thanks for any help.


either blue or green are "true", when you end up with e.g. 2 greens in a block/row/column, you know the green color can't be true, so all the greens can be removed

take a look at the zip files you can download from the SS page and enable Super Tips, great way to learn new techniques
Back to top
View user's profile Send private message
lennyh

Joined: 29 Aug 2005
Posts: 8
:
Location: Raleigh, NC USA

Items
PostPosted: Mon Aug 29, 2005 3:36 pm    Post subject: Reply with quote

Thanks for the helpful explanation, bart. I believe I understand it now. It never occurred to me that candidates associated with all the "false' color could be removed.

Lenny
Back to top
View user's profile Send private message
lennyh

Joined: 29 Aug 2005
Posts: 8
:
Location: Raleigh, NC USA

Items
PostPosted: Mon Aug 29, 2005 10:21 pm    Post subject: Still confused re colors Reply with quote

I thought I understood "Colors", but it's clear that I don't. I tried multicolors001.ss w/ Simple Sudoku and unfortunately am still confused.

At one point the puzzle candidates look like this -- filtering on 7

*** *** ***
*** *7* *7*
*** 77* 7**

**7 *** 77*
*** 7** *7*
**7 *7* ***

*** *** ***
*** *** ***
*** *** ***

Simple Solver hints that "MultiColors" is used to exclude candidates from
r3c4, r4c3, r5c8, and r6c6. And it appears to utilize 2 different chains to do this. After some study of this example, I'm a bit chagrined to admit that I don't understand colors at all. I'm not completely clear on how the chains are established, nor on the rules for excluding. Can someone clarify?

Thanks.
Back to top
View user's profile Send private message
bart

Joined: 11 Aug 2005
Posts: 46
:

Items
PostPosted: Mon Aug 29, 2005 10:29 pm    Post subject: Reply with quote

multicoloring is lot harder to understand

Quote:
This technique is known as "simple colouring." There is also "multicolouring" or "supercolouring", a technique that makes deductions by combining the implications from conjugates of all candidates for all cells. This technique is beyond the ability of most, if not all, human solvers.

source: http://www.simes.clara.co.uk/programs/sudoku.htm


but, if somebody cares enough to explain it all, be my guest Smile
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Mon Aug 29, 2005 11:14 pm    Post subject: Reply with quote

bart wrote:
if somebody cares enough to explain it all, be my guest Smile


Here's the layout at the critical step in multicolors1.ss :


2 separate conjugate chains* following candidate 7s are colored blue-green and pink-amber. You'll note in the image above that the blue cells in one chain share a group with both a pink and an amber cell in the other chain (box2 has a blue & a pink cell; col 8 has a blue & an amber cell). Because pink and amber are conjugate colors, one of them must be the true state. Therefore, blue can't be true because it is in a group with another cell which must be true. All blues are false so candidate 7s can be excluded from blue cells.

*Conjugate chains:
Firstly, conjugate pairs are 2 cells sharing the same group that are also the only possible locations for a specific candidate. (eg If candidate 7 in column 3 is only present in r4c3 and r6c3 then those two cells form a conjugate pair of cells.)
Conjugate chains are made up of two or more conjugate pairs, where each conjugate pair shares a cell with another conjugate pair.
The point of conjugate chains is that each cell around the chain must alternate between a true state (where the candidate is that cell's value) and a false state. Because we don't (yet) know which are the alternate true cells around this chain we simply color cells in alternating colors, one color representing true and the other false.
Back to top
View user's profile Send private message Visit poster's website
bart

Joined: 11 Aug 2005
Posts: 46
:

Items
PostPosted: Mon Aug 29, 2005 11:26 pm    Post subject: Reply with quote

aah, now I understand
thanks

but this must be a more simple form of multicoloring?
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Tue Aug 30, 2005 12:36 am    Post subject: Reply with quote

bart wrote:
but this must be a more simple form of multicoloring?

It depends on what you call multicoloring.

My own classification of coloring techniques consists of:
Simple colors: coloring one conjugate chain on a single candidate
Multi-colors: coloring more than one conjugate chain on a single candidate
Advanced (or super) colors: coloring more than one conjugate chain on more than one candidate.
Back to top
View user's profile Send private message Visit poster's website
lennyh

Joined: 29 Aug 2005
Posts: 8
:
Location: Raleigh, NC USA

Items
PostPosted: Tue Aug 30, 2005 1:49 am    Post subject: Coloring Reply with quote

aj, thank you for the helpful explanation. Let me, if I may, ask a follow-up:

Consider your write-up, "Solving with Colors". In this write-up you describe 2 rules. The first (call it rule 1) begins "Whenever two cells in a conjugate chain have the same color..."

The second (rule 2) begins "Also, whenever a candidate outside the chain...".

Would you suggest that your helpful explanation in todays posting regarding multicolors001.ss is an example or particular case of either rule 1 or rule 2, or would you rather suggest that it is a separate rule -- perhaps specific to the multi-color consideration?

I'm trying to make it easier for someone like myself who is subject to brain pain when trying to understand the core logic behind a technique and would rather just apply a possibly more straight-forward rule.

Thanks for your consideration.

Lenny
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, 3, 4  Next
Page 1 of 4

 
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