| Ocean
| Joined: 29 Aug 2005 | Posts: 15 | : | | Items |
|
Posted: Tue Aug 30, 2005 8:49 pm Post subject: Exploring the relation between coloring and forcing chains |
|
|
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!] |
|