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   

Exploring the relation between coloring and forcing chains

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Ocean

Joined: 29 Aug 2005
Posts: 15
:

Items
PostPosted: Tue Aug 30, 2005 8:49 pm    Post subject: Exploring the relation between coloring and forcing chains Reply with quote

I will try to use two different methods (Coloring and Forcing chain), and show how both methods in this case lead to the same conclusion.



Code:
 *-----------*
 |...|...|28.|
 |..7|...|..9|
 |6..|.9.|..5|
 |---+---+---|
 |.8.|17.|..4|
 |76.|...|...|
 |54.|.86|...|
 |---+---+---|
 |..5|.6.|...|
 |1..|2.7|...|
 |..6|..8|3..|
 *-----------*



The test example is a partly solved puzzle at a crucial point, where the software solver fails to find any next logical step. Can we find it by hand?


Solution:

First: do some initial preparation (using elimination by naked quads and hidden pairs).


1. Forcing Chain method:

These implications are valid:
if (r3c4{78}=8) => r1c4{67}=7 => r1c9{67}=6 => r8c9{68}=8 => r7c1{23489}=8 => r3c3{2348}=8 => r3c4=7. So, r3c4 cannot be 8, and we can set r3c4={7}.

The argument is short and concise, and the chain is easy both to spot and verify once we know it is there. But a bit tricky to find without guidance of some kind.


2. Coloring method:

Color these conjugate chains for fingerprints 6, 7, 8 respectively:
6: r1c4(Black)-r1c9(Yellow)-r8c9(Black)
7: r1c4(Dog)-r3c4(Cat)
8: r8c3(Male)-r7c1(Female)-r2c1(Male)-r3c3(Female)-r3c4(Male)

The three separate conjugate chains are linked as following:
Node r3c4: The fingerprints 78 form a conjugate pair. Meaning we either have 'Cats' or 'Males' but not both, so we either have 'Female Cats' or 'Male Dogs'.
Node r1c4: The fingerprints 67 form a conjugate pair. Meaning we either have 'Black' or 'Dog' but not both, so we have 'Black Cats' or 'Yellow Dogs'.
This combines to either 'Female Black Cats', or 'Male Yellow Dogs'
Edge r8c3(Male)-r8c9(Dog) defines a weak link for fingerprint 8. A weak link means that if one is 'true', the other must be 'false'. In other words, there are 'No Male Dogs', but there has to be 'Female Cats'. In fact the whole 'pet chain' consists of 'Black Female Cats'.
So four of the cells are immediately set:
r1c9(Black)=6
r3c4(Cat)=7
r6c1(Female)=8
r3c3(Female)=8

The Coloring method has more tricky arguments, but it is rather mechanical and seems to reach results quicker. The arguments are not all obvious, so they therefore should be supported by formal proofs before they can be fully trusted. But the final result can in fact also be verified by 'Forcing Chain'.


OK. The crucial step is solved, and the rest is trivial.



[For the sake of reference and credit: This example is actually a 'chewed' variation of "menneske 2155141", number 1 on the 'top 10 list' rating the most difficult in a database with a few million puzzles. The original puzzle is easily solved by similar methods - and maybe somebody already did!]
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
Page 1 of 1

 
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