The New Sudoku Players' Forum

[DoubleDigit]

I don't understand the hint that is given in the below grid. Does anyone know how this hint works?

[TKiel]

It's known as colouring, in Simple Sudoku. Conjugate cells are marked with alternating colors. All the cells of one color share a like condition. Either they are true or they are false, but you don't know which. What you do know is that one of the colours must be true, so any cell outside the chain that intersects (shares a group) with both colours can't be true and can be excluded.

Tracy

[Animator]

The grid in plain text: (question posted as an image. Image is located at another site, nothing stops it from disappearing which would make this thread useless)

Code: Select all

7     6    1   | 3    4  9   | 5     8   2
48    9    5   | 2    1  68  | 3     67  47
248   3    248 | 7    5  68  | 14    16  9
---------------+-------------+---------------
5     14+  9   | 14-  2  7   | 8     3   6
38    2    38  | 9    6  5   | 17    4   17
14-   7    6   | 8    3  14+ | 2     9   5
---------------+-------------+---------------
1246  14-  247 | 146  9  3   | 147x  5   8
9     8    34  | 5    7  14- | 6     2   134+
1346  5    347 | 146  8  2   | 9     17  1347


In this grid the number 1 is coulered.

r4c2 is the oppsite of r6c1.
r4c4 is the opposite of r4c2 (= r6c1)
r6c6 is the opposite of r6c1/r4c4 (= r4c2)
r7c2 is the opposite of r4c2 (= r6c1)
r8c6 is the opposite of r6c6 (= r6c1)
r8c9 is the opposite of r8c6 (= r4c2)

Either all the +'s are true (and all -'s false) are true or all the -'s are true (and all +'s false).

Now r7c7 sees a + in r8c6 and a - in r7c2. Either + or - is true so r7c7 can never be true.

[emm]

Once you have labelled the cells true/false (blue/green) there are 2 rules for making eliminations

- if two cells of the same colour are in the same group - row, column or box - then all cells of that colour are false

- if an uncoloured cell intersects with one of both colours then that cell is false - this applies in your example - the 1 can be eliminated from r7c7

[Animator]

em initially stated that 1 and 4 could be coloured at the same. This was a repsone to that comment.

Actually, another pattern is needed to colour the 4's. (My first guess was that the 4's are coloured but this is not the case).
Row 8 has the number 1 twice and the number 4 three times. r8c9 is the opposite of r8c6 for the number 1 but not for the number 4.

[DoubleDigit]

Ahh! Thanks everyone, it makes sense now!

[emm]

Yes, you're quite right. I was blinded by the beautiful pattern of 1s and 4s! I'll edit my post and hope I haven't confused the OP.

PS : Evidently not!

[ronk]

Once you have labelled the cells true/false (blue/green) there are 2 rules for making eliminations

- if two cells of the same colour are in the same group - row, column or box - then all cells of that colour are false

- if an uncoloured cell intersects with one of both colours then that cell is false

And, perhaps not so obviously, the rules must be applied in that order.

[Animator]

Actually, ronk, that's not true.

The only time you can elimenate something based on the first rule is when you didn't do the second rule properly.

As in, when can you a cell colour +? When the unit has the other colour (-). But if another unit (which is seen by the first cell) already has that colour then the number shouldn't be a candidate, since it sees both a + and a -. You should have removed it because of rule 2. (Which means you have a hidden single somewhere)

[ronk]

Actually, ronk, that's not true.

Yes, I sure didn't think that one through. If a candidate "sees" both conjugate colors, exactly one of which must be true, that candidate can be eliminated. Whether or not one of those colors is known to be false, or might have been known to be false, matters not.

The only time you can elimenate something based on the first rule is when you didn't do the second rule properly.

Actually, Animator, that's not true either. The correct answer is that the rules can be applied in either order ... which is consistent with the application of other techniques, i.e., an arbitrary order does not produce invalid eliminations or placements.

Here is an example from #53 of the top95. There are two +7's in row 9 and the 7 at r7c4 sees both a '+' and a '-' (r9c5 and r7c9).

Code: Select all

 16      2       167     | 48      17      48      | 5       9       3
 8       13      137     | 5       29      29      | 4       6       17
 9       4       5       | 137     6       137     | 12      127     8
-------------------------+-------------------------+---------------------
 145     1589    2       | 14679   3       145679  | 189     145     1469
 145     6       149     | 149     8       1459    | 7       3       2
 7       13589   13489   | 2       159     14569   | 189     145     1469
-------------------------+-------------------------+---------------------
 1256    159     169     | 1679    4       125679  | 3       8       179
 12345   7       1489    | 1389    1259    123589  | 6       124     149
 12346   189     14689   | 136789  1279    1236789 | 129     1247    5


 .   .  +7   | .  -7   .   | .   .   .   
 .   .  -7   | .   .   .   | .   .  +7   
 .   .   .   | 7   .   7   | .  -7   .   
-------------+-------------+-------------
 .   .   .   | 7   .   7   | .   .   .   
 .   .   .   | .   .   .   | 7   .   .   
 7   .   .   | .   .   .   | .   .   .   
-------------+-------------+-------------
 .   .   .   |*7   .   7   | .   .  -7   
 .   7   .   | .   .   .   | .   .   .   
 .   .   .   | 7  +7   7   | .  +7   .   



Ron

[Animator]

In which case rule 2 wasn't applied at all times...

After colouring a cell all intersections should be checked... This did not happen when couloruing r1c5, r7c9, r9c5 or r9c9. (If it did happen then r9c5 or r9c9 didn't have the candiadte 7, which would leave a hidden single in column 5 or box 9)

Update to clarify what I'm saying:

One either had:

Code: Select all

 .   .  +7   | .  -7   .   | .   .   .
 .   .  -7   | .   .   .   | .   .  +7
 .   .   .   | 7   .   7   | .   7   .
-------------+-------------+----------
 .   .   .   | 7   .   7   | .   .   .
 .   .   .   | .   .   .   | 7   .   .
 7   .   .   | .   .   .   | .   .   .
-------------+-------------+----------
 .   .   .   | 7   .   7   | .   .  -7
 .   7   .   | .   .   .   | .   .   .
 .   .   .   | 7  *7   7   | .  +7   .

or

Code: Select all

 .   .  +7   | .  -7   .   | .   .   .
 .   .  -7   | .   .   .   | .   .  +7
 .   .   .   | 7   .   7   | .   7   .
-------------+-------------+----------
 .   .   .   | 7   .   7   | .   .   .
 .   .   .   | .   .   .   | 7   .   .
 7   .   .   | .   .   .   | .   .   .
-------------+-------------+----------
 .   .   .   | 7   .   7   | .   .  -7
 .   7   .   | .   .   .   | .   .   .
 .   .   .   | 7  +7   7   | .  *7   .

If rule 2 is used at all times then rule 1 can never happen.

[ronk]

If rule 2 is used at all times then rule 1 can never happen.

OK, I now see what you're saying. But that approach doesn't translate to a particularly efficient computer algorithm AFAICS. And it's not the implementation method of Angus Johnson's Simple Sudoku, for example.

Ron

[Sabreman64]

Could someone please clarify the differences between 'colours', 'forced chains' and 'bifurcation'? Or are they all the same technique?

[emm]

After colouring a cell all intersections should be checked

Well I don't know so much about 'should' - I prefer to colour all the cells to start with and if I get a Rule 1 then it's a bonus as it means more eliminations in one fell swoop - in this case all 4+ straight off.

Sabreman - colouring and forcing chains are similar in that they are both techniques in which cells are connected.

In forcing chains you are connecting cells that share a candidate, in colouring you track just one candidate and connect conjugate cells - cells in which that number occurs in only two cells in the group.

The Sadman website has a good explanation of colouring and chains. http://www.simes.clara.co.uk/programs/sudokutechniques.htm

Bifurcation just means taking different paths (I think).

[tso]

"Forcing Chains" is its most general sense encompases many types of tactics, including coloring. Any exculsion made by coloring could be restated as a forcing chain -- but most forcing chains are *not* coloring.

A must-read (and bookmark) thread on the subject is here.

Coloring uses "pure bilocation chains". Simple coloring uses pure bilocation chains that are also "x-chains".


Bifurcating is splitting one puzzle into two (trifurcating into three, etc). One simply makes two copies of the grid at a specific position, picks a cell that has two candidates, place one candidate in one grid and the other in the other and tries to solve them both. Often, a nearly intractable puzzle is reduced to triviality -- if the right bifurcation is picked. It's logical method but typically not particularly satisfying. However, if the goal is to find the solution as quickly as possible, as in competition, it will often be faster then cleverer methods.